Leetcode Random

Leetcode刷题笔记- random.

（1）rand3() -> rand7()

给定一个可以等概率生成1-3的rand3()函数生成器，求解可以随机等概率生成1-7的rand7()函数生成器。

使用多个 rand3()，保证产生的值域是大于后者的，然后再产生的值域上进行裁剪取尾。

	3	6	9
1	4	7	10
2	5	8	11
3	6	9	12

转成这种样子：

	3	6	9
1	1	4	7
2	2	5	8
3	3	6	9

从以上的两个例子中，这种随机数的套路应该是掌握了吧。如果是 randx() 那么这个生成式子就是 randx() + randx() *x

这个乘数必须是 x ，要不然就重复生成了一个数字，那么最后就没有办法达到等概率，至于最后的减去的数字则是根据实际情况选择。一定要生成连续不重复的数字，这样才能是等概率的。

减去的数字保证了取余能够整除的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


def rand3_to_rand7():
    value =0

    for i in range(1,4):
        for j in range(1, 4):
            value =i + j*3 -3
            if value >7:
                return
    return value% 7

（2）rand2() -> rand5()

Given rand2(), you should get rand5()

如果只是使用两个 rand2() 那么只能得到四种可能性，不足以生成 rand5() ，所以要使用3 个rand2() ，这个时候得到了 8种可能性，减去3 种，那么就OK 了。( 从这个例题中可以得到是使用多个 randx() 的倍数是 x)

1
2
3
4
5


int rand7() {
     int x = rand2() * 4 + rand2() * 2 + rand2();
     if (x == 7) return rand7(); // restart
     else return x;
}

（3）470. Implement Rand10() Using Rand7()

基本的思路：首先构造生成器randN，N 是10的倍数，这样 randN % 10 就可以得到结果。更加具体的操作步骤：

rand7 可以得到 [1, 7]的等概率的数字
(rand7() -1) *7 + (rand7() -1) 可以得到[0, 48] 的数字
如果产生了大于等于40大的数字，那么重复上一步操作，直到产生小于40的数字
将上一步骤中产生的结构 mod 10 +1 ，然后等概率随机产生了 [1, 10]的数字

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


// 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() {
        return rand40() % 10 +1;
    }
    int rand49(){
        return (rand7() -1) * 7 + (rand7() -1);
    }  
    int rand40(){
        int r =rand49();
        while(r >= 40)
        {
            r =rand49();
        }
        return r;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


# The rand7() API is already defined for you.
# def rand7():
# @return a random integer in the range 1 to 7
class Solution:
    # 首先是 rand49() 然后是 rand40() 最后是 rand10()
    def rand10(self):
        return self.rand40() %10 +1
    
    def rand40(self):
        t =self.rand49()
        while t >= 40:
            t =self.rand49()
        return t
    
    def rand49(self):
        return (rand7()-1) *7 + rand7() -1 # 这个是两次random， 不能简单的说把两者给合并起来

（4）一个返回[0, 1] 浮点数的随机函数 random() ，请利用该函数，完成一个从52 张扑克牌中不放回抽取 3张牌的函数，要求每张牌被抽取的概率一致。

这个暂时没有很好的思路。。。。。

文章目录