企业官网建设流程全解析

刷题刷到随机数这块，LeetCode 470 基本是绕不开的一道题。题目很短，一句话：给你一个能等概率生成 1 到 7 的 rand7()，要求只基于它实现 rand10()，让输出 1 到 10 也等概率。很多人第一眼觉得应该很简单，写出来的代码却经不起推敲。我最早刷这道题的时候也想当然地写过(rand7() + rand7()) % 10 + 1这种写法，被测试数据教育了之后才老老实实去查为什么。后来在面试里也遇到过几次这道题的变体，比如用 rand5() 生成 rand7()，本质上都和拒绝采样有关。所以这篇文章我把自己从错误到正确、从基础到优化的完整思路写出来，顺便把常见误区和证明方法也整理清楚，希望能帮你一次吃透这道经典概率题。

1. 题目到底在考什么：为什么不能简单硬凑

1.1 单次调用的信息量不够

先从最底层想这个问题。rand7()的输出只有 7 种可能，而目标rand10()需要 10 种可能。一次rand7()无论如何也没法直接变出 10 种等概率结果，因为 7 不是 10 的倍数。这句话看着像废话，但很多人写错代码，就是因为忽略了这一点。

有人会想：那我把rand7()的结果乘一个系数不就行了？比如rand7() * 10 // 7。问题是，乘法缩放只能放大数值区间，不能改变每个值出现的概率，更没法凭空多出几种等概率的结果来。rand7()的结果 1 到 7 本来就是等概率的，经过线性变换后还是 7 个等概率的值，不可能均匀覆盖 1 到 10 这 10 个整数。

所以核心思路只能是：多次调用rand7()，用它们的组合结果来构造一个更大的、仍然是等概率的样本空间，然后从这个大空间里提取目标结果。这里的组合方式必须保证每个组合出现的概率完全相等，否则后面全是白搭。

1.2 组合二维坐标：把 1 到 49 当成一副等概率卡牌

常见的组合方式是调用两次rand7()。假设第一次叫a，第二次叫b，那么(a, b)一共有 7×7=49 种组合，而且每种组合出现的概率都是 1/49。看起来很简单，但怎么把 49 种等概率组合映射成 10 种等概率结果？

一个很自然的做法是构造一个公式：

num = (a - 1) * 7 + b

这个num的取值范围是 1 到 49。你可以把它理解成：把a当作“高位”，b当作“低位”，用 7 进制的方式拼成一个整数。具体来说，当a=1时，num取 1 到 7；当a=2时，num取 8 到 14；依此类推，每一个从 1 到 49 的整数都恰好对应一个唯一的(a, b)组合。

这和“骰子掷出点数组合”是一个道理。49 种组合等概率，等于你有 49 张编号 1 到 49 的卡牌，随便抽一张。现在目标是从 1 到 49 这 49 个等概率的数字中，得到均匀的 1 到 10。有人说那我直接对 10 取模不就行了？num % 10 + 1看起来能覆盖 1 到 10，但注意 49 和 10 不是倍数关系，取模之后不同余数对应的原始数字个数不一样，结果一定不均匀。这一点后面会专门讲。

既然 49 不能被 10 整除，那就必须丢掉一部分结果。丢掉谁、怎么丢，就引出了拒绝采样的核心思想。

2. 基础解法：两次 Rand7() 加拒绝采样

2.1 Python3 代码与逐行解释

最简单的解法是这样：

def rand10(): while True: num = (rand7() - 1) * 7 + rand7() # 均匀生成 1..49 if num <= 40: return (num - 1) % 10 + 1

逐行解释一下：

1. (rand7() - 1) * 7 + rand7()生成 1 到 49 的均匀整数。为什么均匀？因为每个(a, b)组合概率相同，而num和组合是一一对应的。
2. 判断num <= 40。为什么取 40？因为 40 是 10 的倍数，1 到 40 可以均匀地分成 10 组，每组 4 个数字。数字 1 到 10 各出现 4 次。
3. (num - 1) % 10 + 1把 1 到 40 均匀映射到 1 到 10。比如num为 1、11、21、31 时都返回 1，num为 2、12、22、32 时都返回 2，依此类推。
4. 如果num落在 41 到 49 之间，说明抽到了“无效卡牌”，直接重新循环，再试一次。

这个算法核心就是拒绝采样。我可以打个比方：你手里有一副 49 张的公平牌组，只有抽到前 40 张才算数，抽到后 9 张就洗牌重抽。重抽不会破坏公平性，因为每一次抽取都是独立且等概率的，抽中“有效区域”的条件概率在每一轮完全相同，所以最终返回的每个结果仍然是均匀的。

2.2 期望调用次数的计算

写题的时候，经常会被问到“这个算法平均要调用多少次 rand7()”。这也是面试官喜欢追问的点。

我们每次循环调用 2 次rand7()，成功概率是 40/49。于是从循环次数来看，期望循环次数是成功概率的倒数：

期望循环次数 = 1 / (40/49) = 49/40

所以期望调用rand7()的次数就是：

期望调用次数 = 2 × 49/40 = 49/20 = 2.45

也就是说，平均每生成一个 1 到 10 的结果，大约要调用 2.45 次rand7()。这个数字不是每次固定的，但如果你跑一百万次测试，统计出来的平均值会非常接近 2.45。

基础解法最大的优点是简单、容易解释清楚。只要能说清楚“为什么要拒绝 41 到 49”，这个解法在面试里已经算合格了。但我自己刷题的时候总觉得那 9 个被丢掉的结果有点可惜，毕竟它们本身也是等概率的，于是又去研究了优化方案。

3. 优化解法：三段式拒绝采样

3.1 拒绝掉的 9 种结果其实还能用

基础解法丢掉 41 到 49 这 9 个数字，但如果换个角度想：当num落在 41 到 49 之间时，num - 40得到的是 1 到 9，这其实是一个均匀的rand9()。丢掉它，等于把一个现成的rand9()扔了。

那能不能把这个rand9()再和一次新的rand7()结合，生成更大范围的均匀数字？当然可以。rand9()和rand7()组合，一共是 9×7=63 种等概率结果。63 比 10 大多了，至少能取 60 个，也就是 10 的倍数，然后保留 3 个继续利用。

再看，如果第二轮也失败，num - 60得到的是 1 到 3，这又是一个均匀的rand3()。rand3()和rand7()组合，一共是 3×7=21 种等概率结果，取前 20 个正好又是 10 的倍数，只剩 1 个无效结果需要重来。

这就是三段式拒绝采样的思路：每一层失败后不直接重来，而是把失败分支的“残余均匀性”榨干，一直用到实在榨不出来为止。

3.2 Python3 优化代码

代码如下：

def rand10(): while True: a = rand7() b = rand7() num = (a - 1) * 7 + b # 1..49 if num <= 40: return (num - 1) % 10 + 1 a = num - 40 # 1..9，等价于 rand9() b = rand7() num = (a - 1) * 7 + b # 1..63 if num <= 60: return (num - 1) % 10 + 1 a = num - 60 # 1..3，等价于 rand3() b = rand7() num = (a - 1) * 7 + b # 1..21 if num <= 20: return (num - 1) % 10 + 1

这段代码里，每一层的num都是均匀的，关键在于a的取值始终是连续等概率的：

• 第一层若失败，num是 41 到 49 均匀，a = num - 40就是 1 到 9 均匀。
• 第二层a有 9 种可能，b有 7 种可能，组合出来的num = (a-1)*7 + b覆盖 1 到 63，每个数恰好出现一次，均匀。
• 第二层若失败，num只可能是 61、62、63，对应的a = num - 60是 1、2、3，均匀。
• 第三层a有 3 种可能，b有 7 种可能，组合出来 1 到 21 均匀，取前 20 个映射，最后一个失败后重新开始整个循环。

整个过程的核心就是：组合生成均匀整数，截取“10 的整数倍”部分，剩余部分再组合、再截取。

3.3 期望调用次数：从 2.45 次降到 2.1933 次

优化版到底优化了多少？我们需要算一下期望调用次数。设总期望调用次数为 E，从第一层开始看：

• 第一层要调用 2 次rand7()。成功概率 40/49，失败概率 9/49。
• 如果失败，进入第二层，这时要额外调用 1 次rand7()。第二层成功概率 60/63=20/21，失败概率 3/63=1/21。
• 如果第二层也失败，进入第三层，额外调用 1 次rand7()。第三层成功概率 20/21，失败概率 1/21。
• 如果第三层也失败，就回到第一层重新来，期望仍然是 E。

于是可以列出递推方程：

E = 2 + (9/49) × [1 + (1/21) × (1 + (1/21) × E)]

解得：

E = 329/150 ≈ 2.1933

对比基础版的 2.45，优化版平均每次能省大约 0.26 次调用，大概 10% 的收益。这个优化在 LeetCode 的测试用例上不会有明显感觉，毕竟单次调用本身很快；但如果你在做随机采样类的高频场景，比如跑蒙特卡洛模拟、随机抽样生成，这个差别就会被放大。

注意：优化版代码更长，面试时一定要先讲清楚“每一层为什么是均匀的”，再写代码。如果代码写出来了但解释不清楚均匀性，面试官很可能会认为你是背的答案。

4. 常见错误写法与均匀性证明

4.1 两个典型错误写法的反例

很多人第一反应是(rand7() + rand7()) % 10 + 1，这个写法看起来像模像样，但均匀性一验证就崩。

关键问题是：两个rand7()的和并不是均匀分布。设s = a + b，取值范围是 2 到 14。不同和值对应的组合数完全不同：

也就是说，和为 8 的组合有 7 种，和为 2 的组合只有 1 种。对这样的和值取模再 +1，不同输出值背后的组合数也必然不一样，怎么可能均匀？

另一个常见错误是(rand7() * rand7()) % 10 + 1。乘法分布同样不是均匀的。比如乘积为 1 的情况只有(1,1)一种，乘积为 2 的情况有(1,2)和(2,1)两种，乘积为 4 的情况有(1,4)、(4,1)、(2,2)三种。取模之后，每个余数对应的组合数也不相等。遇到这类写法，最简单的验证办法是写个循环跑几十万次，统计每个结果的频率，一眼就能看出不均匀。

这里我额外强调一点：均匀性的本质是“每个输出值对应的原始组合数相同”。只要这一点不满足，不管代码多简单、多直观，它都是错的。

4.2 如何严格证明输出是均匀的

面试里被问到“怎么证明你的解法是均匀的”，不要只说“显然均匀”。给出一个严谨一点的说法。

以基础版为例。在返回结果之前，程序实际上只会在1..49中截取1..40部分。num的 40 个值里，每一个值出现的概率都是 1/49。映射时，1 到 10 每个目标值对应 4 个不同num。所以条件在“本轮回合并成功返回”的情况下，返回任意目标值 k 的概率都是 4/40=1/10。

然后要处理“可能经过多轮才成功”的情况。每一轮的成功概率和条件分布完全一样，失败的轮次只是重试，不影响最终分布。所以整体来看，返回任意目标值 k 的概率仍然等于 1/10。

优化版的证明也同理。第一层返回时是从1..40均匀截取；第二层返回时是从1..60均匀截取；第三层返回时是从1..20均匀截取。每一层中，任意目标值 k 对应的原始数字个数分别是 4、6、2，而各自的总有效数字个数分别是 40、60、20，条件概率都等于 1/10。各层之间互斥，最终无条件概率自然也是 1/10。

4.3 扩展：任意 RandM() 构造 RandN() 的通用框架

这类题目不只是考rand7()到rand10()，稍微变形就成了一道新题，但底层框架是通用的。

• 如果 M ≥ N，直接用拒绝采样：先生成randM()，取randM() ≤ N * (M // N)的部分映射到 1 到 N，超出就重试。
• 如果 M < N，先组合多次randM()，构造一个更大的均匀整数空间，使得M^k ≥ N。比如rand5()构造rand7()，可以调用两次rand5()得到 25 种等概率结果，取其中 21 个映射到 1 到 7，剩下 4 个重试。
• 如果空间非常大，还可以像优化版那样把“剩余部分”递归利用，减少重试次数。

这里面有个有趣的延伸视角：从信息论看，rand7()每次携带约 log2(7) ≈ 2.807 bit 信息量，而rand10()需要 log2(10) ≈ 3.322 bit，所以理论上平均至少需要约 1.18 次rand7()才能生成一次rand10()。基础解法 2.45 次离理论下界还很远，三段式优化 2.19 次已经进步了一些，但依然不是最优。算法界有更复杂的方法能逼近理论下界，只是面试和实际工程里很少需要那么极限的优化。

5. 面试实战与刷题体会

5.1 面试场上怎么答最加分

实际面试时，我不太建议一上来就甩优化代码。更稳的节奏是：

第一步，先说思路。明确要构造等概率的大空间，再说“因为 49 不是 10 的倍数，所以要拒绝采样”。这句话能直接点出重点。

第二步，给基础版代码。一边写一边解释(rand7()-1)*7 + rand7()为什么均匀，以及为什么取 40。这个阶段如果能顺口说出期望调用次数49/20 ≈ 2.45，基本就能让面试官满意。

第三步，如果面试官追问“能优化吗”，再给出三段式版本。这时一定要先讲“拒绝掉的 9 个数并不是废料，它们组成了一个均匀的 rand9()”，把递推方程写出来、算出 2.1933 的期望。这属于明显的加分项。

我自己当时在面试里碰到过类似题，面试官其实不一定期待你写出优化版，他更想确认你有没有真正理解均匀性和拒绝采样的原理。所以我建议优先保证基础版说得无懈可击，再谈优化。

5.2 一些个人习惯

写这道题的时候，有几个习惯我建议直接养成。

第一，写完算法题先验证分布。不要只盯着正确性，还要随机跑一大轮统计频率。我用过的简单办法就是collections.Counter(rand10() for _ in range(100000))，看一眼每个数字的计数是否接近 10000。如果某个数字明显偏多或偏少，多半是映射逻辑出了问题。

第二，代码里不要硬编码魔法数字，至少要写清楚每个数字的含义。比如 40 是7*7 - 9，60 是9*7 - 3，21 是3*7。写注释的时候把“为什么 40、60、20”标注清楚，回头再看代码时不容易懵。

第三，这类题目的核心其实是“把两个独立均匀样本组合成一个更大的均匀样本”。一旦掌握了这个套路，遇到rand3()生成rand5()、rand5()生成rand7()之类的变体，都可以直接套框架，而不是靠背答案。

最后再说一个小技巧：如果面试官要求“不允许无限循环”，可以在代码里设置最大重试次数，比如循环 100 次后强制返回一个兜底结果。虽然理论上有极小概率走到兜底，但在工程上能避免极端情况下的死循环。当然，LeetCode 原题没有这个限制，直接while True就行。