LeetCode470随机函数返回等概率的值

问题描述：

  1. 给定一个随机函数f，等概率返回1~5中的一个数字，
    这是唯一可以是使用的随机机制，如何实现等概率
    返回1~7中的一个数字。
  2. 给定一个随机函数f，等概率返回a~b中的一个字母，
    这是唯一可以是使用的随机机制，如何实现等概率
    返回a~d中的一个数字。

这种做法一般考虑用二进制的方法，等概率的返回0和1。

如有一个等概率返回12345的函数f

f’:如果是1和2返回0，4或5返回1，如果是3重新调用f’。

用0和1拼出一个数这样就可以实现等概率。

只有两个二进制位，可以等概率返回0到3。00、01、10、11

三个二进制位，可以等概率返回0到7。000，001，010，011，100，101，110，111

Leetcode:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution extends SolBase {
    public int rand10() {
        int ans = 0;
        do {
            ans = (rand01() << 3) + (rand01() << 2) + (rand01() << 1) + rand01();
//        } while (ans == 15 || ans == 14 || ans == 13 || ans == 12 || ans == 11 || ans == 10);
        } while (ans > 9);
        return ans + 1;
    }


    public int rand01() {
        int ans = 0;
        do {
            ans = rand7();
        } while (ans == 4);
        return ans < 4 ? 0 : 1;
    }
 }

通用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class RandomBox {

    //13 - 17
    // 13+ [0,4]
    public int random() {
        return min + (int) (Math.random() * (max - min + 1));
    }

    public int rand01(int min, int max) {
        int size = max - min + 1;
        // size是奇数还是偶数
        boolean odd = (size & 1) != 0;
        int mid = size / 2;
        int ans = 0;
        do {
            ans = random() - min;
        } while (odd && ans == mid);
        return ans < mid ? 0 : 1;
    }

    public int rand(int min, int max, int from, int to) {
        if (from == to) {
            return from;
        }
        // 3-9
        // 0-6
        int range = to - from;
        int num = 1;
        //求0-range需要几个2进制位
        while ((1 << num) - 1 < range) {
            num++;
        }

        int ans = 0;
        do {
            ans = 0;
            for (int i = 0; i < num; i++) {
                ans |= (rand01(min, max) << i);
            }
        } while (ans > range);
        return ans + from;
    }

}

再一题：

给一个随机函数f，以p概率返回0，以1-p概率返回1

这是唯一可以用的随机机制，如何实现等概率返回0和1

思路：

如果连续两次返回00或11 重新选取，如果返回01取为0，如果返回10取为1

1
2
3
4
5
6
7
8
9
10
11
public int f() {
			return Math.random() < 0.92 ? 0 : 1;
}

public int g() {
    int first = 0;
    do {
        first = f();
    } while (first == f());
    return first;
 }