leetcode-470 Implement Rand10() Using Rand7()

470. Implement Rand10() Using Rand7()

Given a function rand7 which generates a uniform random integer in the range 1 to 7, write a function rand10 which generates a uniform random integer in the range 1 to 10.

Do NOT use system’s Math.random().

Example 1:

1
2
Input: 1
Output: [7]

Example 2:

Input: 2
Output: [8,4]

Example 3:

1
2
Input: 3
Output: [8,1,10]

Note:

  1. rand7 is predefined.
  2. Each testcase has one argument: n, the number of times that rand10 is called.

Follow up:

  1. What is the expected value for the number of calls to rand7() function?
  2. Could you minimize the number of calls to rand7()?

Analyse

使用rand7模拟出rand10

用多的模拟少的很简单，比如如果是要rand10模拟rand7，把rand10中结果超过7的去掉，再调用一次rand10，直到结果<=7即可

第一种办法，把1-10分成两部分，这样就可以用rand7来模拟，总共需要>=2次rand7

第一次rand7，用来区分生成1-5还是6-10，如果rand7的返回值 > 4，生成6-10，< 4，生成1-5
第二次rand7，模拟rand5，要生成6-10则结果+5

1
2
1 2 3 4 5 6 7
1 2 3 4 5 6 7 8 9 10
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
int leftOrRight() {
    int tmp = rand7();
    if (tmp < 4)
    {
        return 0;
    }
    else if (tmp > 4)
    {
        return 1;
    }
    else
    {
        return leftOrRight();
    }
}

int getSmall5() {
    int tmp = rand7();
    if (tmp <= 5)
    {
        return tmp;
    }
    else
    {
        return getSmall5();
    }
}

int rand10() {
    int lr = leftOrRight();
    if (lr == 0)
    {
        return getSmall5();
    }
    else
    {
        return getSmall5() + 5;
    }
}

这种方法性能很差，为了拿到符合要求的数字甚至使用了两次递归

1
2
3
Runtime: 288 ms, faster than 7.28% of C++ online submissions for Implement Rand10() Using Rand7().

Memory Usage: 9.7 MB, less than 80.00% of C++ online submissions for Implement Rand10() Using Rand7().

第二种办法，来自leetcode，用两次rand7，建立一个二维坐标与1-10的映射，

1
2
3
4
5
6
7
8
9
   1  2  3  4  5  6  7
  --------------------
1| 1  2  3  4  5  6  7
2| 8  9  10 1  2  3  4
3| 5  6  7  8  9  10 1
4| 2  3  4  5  6  7  8
5| 9  10 1  2  3  4  5
6| 6  7  8  9  10 *  *
7| *  *  *  *  *  *  *
1
2
3
4
5
6
7
8
9
10
11
12
13
int rand10()
{
    int row, col, index = 0;
    do
    {
        col = rand7();
        row = rand7();
        index = col + (row - 1) * 7;
    }
    while (index > 40);

    return 1 + index % 10;
}
1
2
3
4
5
6
7
8
9
int rand10() {
    int index = rand7() + (rand7() - 1) * 7;
    while (index > 40)
    {
        index = rand7() + (rand7() - 1) * 7;
    }

    return 1 + index % 10;
}