1. LeetCode 470题核心知识点解析

这道题在LeetCode题库中编号为470，属于中等难度题目。题目要求实现一个随机数生成器，能够以特定概率分布生成数字。这类问题在实际编程面试中经常出现，考察的是对概率分布和随机数生成的理解。

1.1 题目要求分析

题目给定一个已知的随机数生成器rand7()，要求基于它实现rand10()。rand7()生成1到7的整数，每个数字概率相等；rand10()则需要生成1到10的整数，同样要求每个数字概率相等。

核心难点在于：

1. 如何用较小范围的随机数生成器实现更大范围的随机数
2. 如何保证生成结果的均匀分布
3. 如何优化调用次数，减少rand7()的调用

1.2 数学基础与解题思路

解决这类问题需要理解两个关键数学概念：

1. 独立事件概率：多次调用rand7()的结果是相互独立的
2. 均匀分布：需要确保最终结果的每个数字出现概率相同

常见思路是：

• 将多个rand7()的结果组合成一个更大的数
• 通过拒绝采样(rejection sampling)来保证均匀性
• 优化组合方式以减少拒绝概率

2. 标准解法实现与优化

2.1 基础解法实现

最直观的解法是：

1. 调用两次rand7()，得到两个独立随机数a和b
2. 计算组合数：(a-1)*7 + b，范围是1-49
3. 如果结果在1-40之间，则返回结果%10+1
4. 否则拒绝并重试

def rand10(): while True: a = rand7() b = rand7() num = (a-1)*7 + b if num <= 40: return num % 10 + 1

这种方法的期望调用次数是2*(49/40)=2.45次rand7()。

2.2 优化解法

可以进一步优化拒绝采样的效率：

1. 第一次组合1-49，拒绝41-49
2. 对拒绝的9个数，再调用一次rand7()得到1-63
3. 接受1-60，拒绝61-63
4. 对拒绝的3个数，再调用一次rand7()得到1-21
5. 接受1-20，拒绝21

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

这种优化方法将期望调用次数降低到约2.2123次rand7()。

3. 数学原理深入解析

3.1 均匀性证明

关键在于证明每个数字1-10的概率确实是1/10。以基础解法为例：

1. 第一次组合产生1-49，每个数概率1/49
2. 我们接受1-40，共40个数
3. 每个被接受的数映射到1-10的概率是(1/49)*(49/40)=1/40
4. 每个最终数字对应4个被接受的数(如1对应1,11,21,31)
5. 因此每个最终数字概率是4*(1/40)=1/10

3.2 期望调用次数计算

对于基础解法：

• 每次尝试需要2次rand7()调用
• 成功概率是40/49
• 期望尝试次数是1/(40/49)=49/40
• 因此期望总调用次数是2*(49/40)=2.45

对于优化解法：

• 第一阶段：概率40/49，调用2次
• 第二阶段：概率9/49*60/63=60/343，调用3次
• 第三阶段：概率9/493/6320/21=20/3087，调用4次
• 期望调用次数=2*(40/49)+3*(60/343)+4*(20/3087)+...≈2.2123

4. 常见问题与调试技巧

4.1 为什么不能直接用rand7()*10/7？

这种看似简单的方法会产生不均匀分布：

• rand7()产生1-7
• 乘以10/7得到约1.428到10
• 取整后某些数字会出现更多次
• 例如：1.428-2.142→2 2.142-2.856→3 但2的范围是0.714，3的范围是0.714，而5的范围可能是1.428
• 导致某些数字概率是其他数字的两倍

4.2 如何验证实现的正确性？

可以通过统计测试验证：

1. 运行rand10()大量次数(如100万次)
2. 统计每个数字出现的次数
3. 计算卡方检验统计量
4. 检查p-value是否足够大(>0.05)

from collections import Counter import math def test_rand10(): counts = Counter(rand10() for _ in range(1000000)) expected = 100000 chi2 = sum((v - expected)**2 / expected for v in counts.values()) print(f"Chi-square statistic: {chi2}") print(f"Counts: {sorted(counts.items())}")

4.3 其他变种问题

这类问题有多种变体，常见的包括：

1. 用rand5()实现rand7()
2. 用randN()实现randM()（一般情况）
3. 非均匀分布的随机数生成
4. 带权重的随机数选择

5. 实际应用与扩展思考

5.1 在实际工程中的应用

这种随机数生成技术在实际中有广泛应用：

1. 游戏开发：需要特定概率分布的随机事件
2. 抽样调查：从非均匀分布中获取均匀样本
3. 负载均衡：在分布式系统中均匀分配任务
4. A/B测试：均匀分配用户到不同实验组

5.2 性能优化思路

进一步优化的方向包括：

1. 使用位运算代替乘法和取模
2. 预计算并缓存部分随机数
3. 使用更高效的拒绝策略
4. 并行生成多个随机数

5.3 类似题目推荐

为了巩固这类问题的解法，推荐练习：

1. LeetCode 528. 按权重随机选择
2. LeetCode 478. 在圆内随机生成点
3. LeetCode 497. 非重叠矩形中的随机点
4. LeetCode 519. 随机翻转矩阵

6. 个人刷题经验分享

在解决这类随机数问题时，我总结了几个关键点：

1. 先明确均匀分布的要求，这是最容易出错的地方
2. 从简单情况入手，比如先用rand5()实现rand7()
3. 画概率分布图有助于理解组合方式
4. 一定要写测试验证均匀性
5. 优化时先保证正确性，再考虑效率

一个常见的误区是试图通过简单的算术运算直接缩放随机数范围，这几乎总会破坏均匀性。拒绝采样虽然看起来效率不高，但能保证严格的均匀分布。

对于面试场景，建议：

1. 先解释基本思路和数学原理
2. 实现基础解法并分析复杂度
3. 讨论优化方向
4. 考虑边界情况和测试方法

这种系统性的思考方式能展现全面的问题解决能力。