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;
}