目录

• L7 整数反转
• L9 回文数（未写）
• 用Rand7()实现Rand10()（!!!!!字节腾讯常考）
• JS44 数字序列中某一位的数字（未写）
• JS62 圆圈中最后剩下的数字（未写）

L7 整数反转

class Solution {
public:
    int reverse(int x) {
        int boundry = INT_MAX / 10;
        int result = 0;
        while(x!=0){
            // 每次取个位
            int tmp = x % 10;
            // 对之前的正数结果进行边界处理
            if(result > boundry || (result==boundry && tmp > 7)){
                return 0;
            }
            // 对之前的负数结果进行边界处理
            if(result < -boundry || (result==-boundry && tmp < -8)){
                return 0;
            }
            result = result*10 + tmp;
            x /= 10;
        }
        return result;
    }
};

L9 回文数（未写）

用Rand7()实现Rand10()（!!!!!字节腾讯常考）

参考

思路：把等概率空间扩大，然后从大的等概率空间中取小范围的数。

规律1：两个小空间随机函数生成一个大空间随机函数

• 已知 rand_N() 可以等概率的生成[1, N]范围的随机数

• 那么：rand_XY() = (rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范围的随机数
  即实现了 rand_XY()

规律2：一个倍数大空间随机函数生成另一个小空间随机函数

• 已知 N = a * M（a为大于1的整数）

• 那么：rand_M = rand_N() % 10 + 1

规律3：一个小空间随机函数生成另一个大空间随机函数

• 已知 N < M，通过 rand_N 生成 rand_M

• 先通过 规律1 将等概率空间扩大：rand_NN = (rand_N() - 1) × N + rand_N()

• 再通过 拒绝采样+规律2 从大等概率空间中取小范围的数：拒绝采样将rand_NN改造成rand_aM，从而rand_M = (rand_aM() - 1) × aM + rand_aM()

• 详细版

class Solution {
public:
/*
已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，
试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。
不要使用系统的 Math.random() 方法。
*/
    int rand10() {
        while(true){
            int a = rand7();
            int b = rand7();
            int num = (a - 1) * 7 + b;  // rand_49
            if(num <= 40) return num % 10 + 1;  // 拒绝采样

            a = num - 40;  // rand_9
            b = rand7();
            num = (a - 1) * 7 + b; // rand_63
            if(num <= 60) return num % 10 + 1;  // 拒绝采样

            a = (num - 60);  // rand_3
            b = rand7();
            num = (a - 1) * 7 + b; // rand_21
            if(num <= 20) return num % 10 + 1;  // 拒绝采样
        }
    }
};

• 精简版

class Solution {
public:
    int rand10() {
        while(true){
            int num = (rand7() - 1) * 7 + rand7();  // rand_49
            // 如果在40以内，那就直接返回
            if(num <= 40) return num % 10 + 1;  // 拒绝采样

            // 说明刚才生成的在41-49之间，利用随机数再操作一遍
            num = (num - 40 - 1) * 7 + rand7(); // rand_63
            if(num <= 60) return num % 10 + 1;  // 拒绝采样

            // 说明刚才生成的在61-63之间，利用随机数再操作一遍
            num = (num - 60 - 1) * 7 + rand7(); // rand_21
            if(num <= 20) return num % 10 + 1;  // 拒绝采样
        }
    }
};

JS44 数字序列中某一位的数字（未写）

JS62 圆圈中最后剩下的数字（未写）