0470：用 Rand7() 实现 Rand10()（★）

力扣第 470 题

题目

给定方法 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 <= 105

进阶:

• rand7()调用次数的 期望值 是多少 ?
• 你能否尽量少调用 rand7() ?

分析

典型的拒绝抽样

• 调用两次 rand7，等价于 rand49
• 然后 1 到 40 对 10 取模即可等价于 rand10
• 如果大于 40，就重新抽样

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def rand10(self):
        """
        :rtype: int
        """
        while True:
            a,b = rand7(),rand7()
            res = (a-1)*7+b
            if res <= 40:
                return res%10+1

169 ms