Leetcode 470: Implement Rand10() Using Rand7()

题目描述

给定生成随机数1到7的函数rand7，请写一个生成随机数1到10的函数rand10。

不要使用系统函数：Math.random()

例子

例子1

输入： 1
输出：[7]

例子2

输入： 2
输出：[8, 4]

例子3

输入： 3
输出：[8, 1, 10]

注意

• rand7提前已定义好
• 每个测试用例有个参数：n，rand10调用的次数。

解题思路

这个题目相信好多人都听说过，以前校招面试常用算法题之一，不知道现在还考这个么。

rand7: 1, 2, 3, 4, 5, 6,7
rand7 - 1: 0, 1, 2, 3, 4, 5, 6
(rand7 - 1) * 7: 0, 7, 14,..., 42
(rand7 - 1) * 7 + (rand7 - 1): 0, 1, 2, 3, ..., 48

我们截取0, 1, 2, 3, …, 39，把后面的数的概率平分到前面的数上，再模10加1，这样就可以产生1到10的随机数了。
上面的过程可以概括为扩充->插空->截取。

解题代码

class Solution extends SolBase {
    public int rand10() {
        int num = 0;
        do{
            num = (rand7() - 1) * 7 + (rand7() - 1);
        }while (num >= 40);
        
        return num % 10 + 1;
    }
}