the leetcode link

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 <= 105

随机择日

一个名为卢迪的宅男，他相信着，八月是循环的高发期，且时常有”/remake”自己的想法。

于是，他计划在2022年8月的随机一天，去坐公交车，为了遇见车途中可能发生的时空循环。

image.png

看日历，很巧妙，2022年的8月的1号刚好是从周一开始。

一周有7天，而本题又很巧有Random7()的功能。

虽然卢迪不会做题，但他想了一个方法，利用Random7()，实现了等概率随机选择哪一天上公交！

这小伙子怎么做呢？

只见他眼疾手快，啪一下，直接写一行代码 return rand7()，

竟然把Ramdom7()作为输出结果。。。。。。真无语了

第一次提交，输出结果是几，他就选择周几，记为a
第二次提交，输出结果是几，他就选择日历上的第几行，记为b

补充说明，8月1号所在行是第1行，9月5号所在行是第6行。

当然，这样抽选的范围是从8月1号到9月18号，为49天。

抽到每一天的概率都是(1/7)*(1/7)，也相当实现Random49()。

但这不是他想要的结果，他只会在8月份中选择一天。

如果抽到9月份，他拒绝采样，重复第一次和二次的提交过程，重新择日。

有了拒绝采样步骤，就能实现Random31()，这才是他想要的结果。

他的随机过程：
a=5，b=5，很不巧，8月没有这一天。拒绝采样，重新再来；
a=2，b=7，很不巧，8月没有这一天。拒绝采样，重新再来；
a=2，b=4，成功随机定位到23号出伏日；

Q：已知a和b，如何用公式计算出几号日期？

利用简单的分页公式：index = (pageNum - 1) * size + currentPageIndex
页号是从1开始，把一周看作一页，得到： 几号日期 = (b-1) 7 + a
例如：23号 = (4-1) 7 + 2

用分页思想，也可以得到一条随机数公式：

randAB = (randB-1) * A + randA

比如上述例子，通过两个Random7()推出Random49()

rand49  = (rand7-1) * 7 + rand7

关于拒绝采样范围过大的问题

卢迪突然接到父母指示，8月10号后不能出家门。

他只能计划在8月1号到8月10号中随机选择一天，意味着要实现Random10()。

他按照之前的方法操作，由于拒绝采样的范围过大，他总是抽取到8月10号以后的日子。

时间已过去很久，依然没抽中前10天，运气过背，他快抽麻了……

于是，他想办法优化：

抽中第 1，11，21，31的位置就是1号出发
抽中第 2，12，22，32的位置就是2号出发
抽中第 3，13，23，33的位置就是3号出发
......
抽中第10，20，30，40的位置就是10号出发

这样，采样范围由10就变成40，他马上抽中结果了。

这就是取余数的思路

几号日期 = index %10 + 1

先决定取样范围：应为N的倍数，再用模N+1方式得到结果

while(index>40){
    index = rand7()+(rand7()-1)*7;
}
return index%10+1;

本题代码

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