leetcode#470-Implement Rand10()

470. Implement Rand10() Using Rand7()

解题思路

方法：拒绝采样
已知Rand7()生成[1，7]的随机数的概率为1/7，如果取到7，我们拒绝再重新进行采样，即我们放弃取到7的所有结果，这种情况下，我们就得到了Rand6()。
同理，我们拒绝取到6，7的采样，则得到Rand5()。

• 在Rand6()中，有1/2为奇数，1/2为偶数，则以此概率为基准，取first=0或5。
• 而Rand5()则取到[1,5]概率为1/5，取second=Rand5()。
• Rand10()=first+second。

代码（c++）

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

class Solution {
public:

    int rand6() {
        int r;
        while(1){
            r = rand7();
            if(r <= 6) return r;
        }
    }

    int rand5() {
        int r;
        while(1){
            r = rand7();
            if(r <= 5) return r;
        }
    }

    int rand10() {
        int r1 = rand6(), r2 = rand5();
        if(r1 & 1) return r2;
        else return r2+5;
    }
};