Cinte's Leetcode Record
0%

470. 用 Rand7() 实现 Rand10()

Posted on Edited on In Disqus:
Symbols count in article: 928 Reading time ≈ 1 mins.

470. 用 Rand7() 实现 Rand10()

在拒绝采样中，如果生成的随机数满足要求，那么就返回该随机数，否则会不断生成，直到生成一个满足要求的随机数为止。

[@mzz](https://leetcode-cn.com/u/coderookie-71/)

1
第一份代码当成模拟 7 进制好理解些，把 rand7() 的值减 1 ，就成了 [0, 6]，模拟两位的 7 进制数，取 [0, 39] 范围内的值，对 10 取余后加一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 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() {
        int col, row, ret;
        do{
            col = rand7() - 1;
            row = rand7() - 1;
            ret = col * 7 + row;
        }while(ret >= 40);
        
        return ret % 10 + 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
// 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() {
        int col, row, ret;
        while(true)
        {
            col = rand7();
            row = rand7();
            ret = (col - 1) + (row - 1) * 7;
            if(ret < 40)
                return ret % 10 + 1;
            col = ret - 39;
            row = rand7();
            ret = (col - 1) + (row - 1) * 7;
            if(ret < 60)
                return ret % 10 + 1;
            col = ret - 59;
            row = rand7();
            ret = (col - 1) + (row - 1) * 7;
            if(ret < 20)
                return ret % 10 + 1;
        }
    }
};