1、前言

2、思路

这个题比较有用，我们可以以这个题来引出概率相关的题。

假设有一个不均匀的硬币，出现 0、1 的 概率分别为 0.6、0.4，那么怎么使它出现的概率变得均匀呢？我们可以做一个表格发现，两个抛硬币时，发现 [0,1] 和 [1,0] 的概率相同。

那么我们可以连续抛两次硬币，如果得到 [0,1]，返回 0；如果得到 [1,0]，返回 1；如果两次结果相同，则重新抛。
代码如下：

public class Coin {

    public static int coin(){
        return Math.random() * 10 > 4 ? 1 : 0;
    }

    public static int fairCoin(){
        while (true){
            int a = coin();
            if(a != coin()){
                return a;
            }
        }
    }

    public static void main(String[] args) {
        double total = 1000000;
        int zero = 0, one = 0;

        for(int i = 0; i < total; i++){
            if(fairCoin() == 0){
                zero++;
            }else {
                one++;
            }
        }

        System.out.println(zero / total);
        System.out.println(one / total);
    }
}

假设有一个均匀的硬币，正反概率都是0.5，想出现0的概率为 1/4，1的概率为 3/4 呢？很简单，两次为 0 则返回0，其余情况返回1。其他的概率依次类推。

但是如果 0 为 0.3，1为0.7呢？

我们都知道，每抛一次硬币，都会生成二进制中的一位。如果抛4次硬币，会生成 [0, 2^4 - 1] 个数。就算我们去掉[10, 15] 范围的数，剩下的 [0, 9] 也是等概率的（抛 k 次硬币，生成 [0, 2^k - 1] 范围的数）。
我们可以调用 coin()，如果数在 0 ～ 2 之间，就返回0；3 ～ 9 之间就返回 1；否则就继续循环。

public int fairCoin2() {
    while (true) {
        int x = 0;
        for (int i = 0; i < 4; i++) {
            x = (x << 1) + coin();
        }
        if (x <= 2) return 0;
        if (x <= 9) return 1;
    }
}

那么上面的问题到底如何解决呢？
使用 (rand7() - 1) * 7 + (rand7() - 1)，我们可以把 rand7 看作是7进制的，前面的二进制都是 x * 2，那么这里就是 x * 7，而且需要2次，即 k = 2，使用上面的 for 循环就是： (rand7() - 1) * 7 + (rand7() - 1)

3、代码

class Solution extends SolBase {
    public int rand10() {
        while(true){
            int a = (rand7() - 1) * 7 + (rand7() - 1);
            if(a >= 1 && a <= 10){
                return a;
            }
        }
    }
}