题目

给定方法 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() ?

思路

//方法是，把等概率产生数的空间扩大
//使得该空间大于要产生新的数的范围，然后
//找到最接近这个空间的一个值k，使得k%新数==0
//也就是说使得k是这个要新生成数的倍数。

//对于本例子来讲，就是把等概率产生数的空间扩大至0-48
//然后取最接近48且为10的倍数的一个值k，这个值是40
//然后每次产生一个新值，若该值小于40，那么对该值mod10
//也就是说新空间中的0，10，20，30代表10；1，11，21，31
//代表1；2，12，22，32代表2；以此类推。

解法

/**
 * The rand7() API is already defined in the parent class SolBase.
 * public int rand7();
 * @return a random integer in the range 1 to 7
 */
// 都是把等概率空间扩大，然后从大的等概率空间中取小范围的数。

// 只不过第一种速度较慢。因为多余空间较多，而第二种较快，因为多余空间较少。


class Solution extends SolBase {
    
    //方法是，把等概率产生数的空间扩大
    //使得该空间大于要产生新的数的范围，然后
    //找到最接近这个空间的一个值k，使得k%新数==0
    //也就是说使得k是这个要新生成数的倍数。
    
    //对于本例子来讲，就是把等概率产生数的空间扩大至0-48
    //然后取最接近48且为10的倍数的一个值k，这个值是40
    //然后每次产生一个新值，若该值小于40，那么对该值mod10
    //也就是说新空间中的0，10，20，30代表10；1，11，21，31
    //代表1；2，12，22，32代表2；以此类推。
    
    public int rand10() {
        while(true){
        int num = (rand7()-1)*7 + rand7()-1;
        if(num < 40)return num%10+1;
        }
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现