(rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范围的随机数

470. 用 Rand7() 实现 Rand10() - 力扣（LeetCode） (opens new window)

class Solution extends SolBase {
    public int rand10() {
        while (true) {
            // 1-49
            int num = (rand7() - 1) * 7 + rand7();
            if (num <= 40) 
                return num % 10 + 1;

            // 复用41-49 → 生成1-63
            int a = num - 40; 
             // 1-63
            num = (a - 1) * 7 + rand7();
            if (num <= 60) 
                return num % 10 + 1;

            // 复用61-63 → 生成1-21
            a = num - 60; 
            // 1-21
            num = (a - 1) * 7 + rand7(); 
            if (num <= 20) 
                return num % 10 + 1;
        }
        
    }
}

69. x 的平方根 - 力扣（LeetCode） (opens new window)

暴力求解法 为避免 i*i 溢出，用 i <= x / i 代替乘法判断

class Solution {
    public int mySqrt(int x) {
        if (x == 0 || x == 1) return x;
        for (int i = 1; i <= x; i++) {
            if (i <= x / i && (i + 1) > x / (i + 1)) {
                return i;
            }
        }
        return -1;
    }
}

二分法

class Solution {
    public int mySqrt(int x) {
        if (x == 0 || x == 1) return x;
        int left = 1, right = x, ans = 0;
        while (left <= right) {
            int mid = left + (right - left) / 2; // 防溢出
            if (mid <= x / mid) {
                //每次发现更大的合法 mid 时更新 ans，最终保证返回最大值
                ans = mid;
                // ans = mid 并向右搜索（尝试更大值）
                left = mid + 1;
            } else {
                //向左搜索（排除过大值）
                right = mid - 1;
            }
        }
        return ans;
    }
}

牛顿迭代法（数值逼近）

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        double guess = x; // 初始猜测值
        while (true) {
            double next = (guess + x / guess) / 2;
             if ((int) guess == (int) next) break; // 整数部分稳定
             guess = next;
        }
        return (int) guess;
    }
}