每日一题:470.用Rand7()实现Rand10()

题目:已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数,试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

不要使用系统的 Math.random() 方法。

示例 1:

输入: 1
输出: [7]
示例 2:

输入: 2
输出: [8,4]
示例 3:

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


提示:rand7 已定义。
传入参数: n 表示 rand10 的调用次数。

思路:

(这题刚一看什么鬼,再一看有点思路,再深入要每个数出现概率相同,又不会了,最后看了评论区一个大佬写的,这思路给跪了。生而为人为何他们如此优秀,感叹一下,继续向大佬学习,继续刷题,加油!!!)

要想将随机数扩展到1~10,调用两次rand7,进行累加是必须的,只是得对数数进行筛选。因为最后要求概率相同。

这里令a = rand7()   b = rand7()   让a取值范围为[1,6],然后奇偶数各一半,概率1/2, 让b取值为[1,5],到这里也许会好奇这是干嘛,怎么变成1~10?

因为这里让a为偶数时,最后输出b+0,即1~5 每个数概率为 1/2 * 1/5 = 1/10

a为奇数时,最后输出b+5,即6~10 每个数的概率为 1/2 * 1/5 = 1/10

结果: 1 2 3 4 5 6 7 8 9 10
a,b a=偶数,b=1 a=偶数,b=2 a=偶数,b=3 a=偶数,b=4 a=偶数,b=5 a=奇数,b=1 a=奇数,b=2 a=奇数,b=3 a=奇数,b=4 a=奇数,b=5
概率 1/2 * 1/5 = 1/10 1/2 * 1/5 = 1/10 1/2 * 1/5 = 1/10 1/2 * 1/5 = 1/10 1/2 * 1/5 = 1/10 1/2 * 1/5 = 1/10 1/2 * 1/5 = 1/10 1/2 * 1/5 = 1/10 1/2 * 1/5 = 1/10 1/2 * 1/5 = 1/10

代码:

// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:
    int rand10() {
        int a = rand7();
        int b = rand7();
        while(a==7){
            a=rand7();
        }
        while(b>5){
            b=rand7();
        }
        return (a&1?0:5)+b;

    }
};

上一篇:[LeetCode] #101 对称二叉树


下一篇:分别求1~100所有偶数的和几奇数的和;