470. rand7实现rand10
给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。
你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。
每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。
示例 1: 输入: 1 输出: [2]
示例 2: 输入: 2 输出: [2,8]
示例 3: 输入: 3 输出: [3,8,10]
提示: 1 <= n <= 10⁵
进阶: rand7()调用次数的 期望值 是多少 ? 你能否尽量少调用 rand7() ?
解题思路
- 首先，调用两次 rand7()，分别得到两个随机数 a 和 b。
- 将这两个随机数转换成一个二维坐标 (a, b)，这个坐标落在一个 7x7 的网格中。
- 将这个 7x7 的网格映射到一个 10x10 的网格中，并将超出 10x10 网格的部分舍弃。
- 如果映射后的坐标落在 10x10 网格内，则将其转换为 [1,10] 范围内的随机数。
- 否则，重复步骤 1-4，直到生成一个有效的随机数。
func rand10() int {
for {
a, b := rand7(), rand7()
index := (a-1)*7 + b
if index <= 40 {
return index%10 + 1
}
}
}