LeetCode470 用 Rand7() 实现 Rand10()

链接: https://leetcode-cn.com/problems/pacific-atlantic-water-flow/

题意

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数,试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

解法

是一道很神奇的题目,用一个随机数生成器实现另一个随机数生成器。
就这道题而言,可以先获得一个随机数2生成器,再获得一个随机数5生成器
这个的获得比较容易,只要随机出来的结果在范围内即可
然后 1 / 2 * 1 / 5 = 1 / 10

一个通用的解法是,用小数生成大数的生成器可以用下式来进行生成

其中,rand_N() 可以等概率的生成[1, N]范围的随机数
通过上式,就得到了等概率的生成[1, X * Y]范围的随机数,即实现了 rand_XY()

因此本题中,用rand7通过上式得到rand49,再通过拒绝采样,去掉超过40的数
再取模就可以得到rand10

代码

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7
class Solution {
public:
int rand10() {
int res = 0;
int a = 10, b = 10;
while(a > 2) {
a = rand7();
}
while (b > 5) {
b = rand7();
}
return a & 1 ? b : b + 5;
}
};

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:
int rand10() {
while (true) {
int temp = (rand7() - 1) * 7 + rand7();
if (temp <= 40) {
return (temp - 1) % 10 + 1;
}
}
}
};