题目

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. Input: 1
  2. Output: [7]

Example 2:

  1. Input: 2
  2. Output: [8,4]

Example 3:

  1. Input: 3
  2. 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()?

题意

使用能够随机生成整数1-7的函数rand7()，来写一个新的函数rand10()，使其能够随机生成整数1-10。

思路

  1. 0470. Implement Rand10() Using Rand7() (M) - 图1 生成整数 0-6
  2. 0470. Implement Rand10() Using Rand7() (M) - 图2 生成整数 [0, 7, 14, …, 42]
  3. 0470. Implement Rand10() Using Rand7() (M) - 图3 生成整数 1-49，即得到 rand49()
  4. 利用拒绝采样来得到 1-40 范围内的随机整数num：通过rand49()得到一个数，如果大于40，则重新运行rand49()，否则赋值给num
  5. 0470. Implement Rand10() Using Rand7() (M) - 图4 得到 1-10 范围内的整数

代码实现

Java

  1. /**
  2.  * The rand7() API is already defined in the parent class SolBase. public int
  3.  * rand7();
  4.  * 
  5.  * @return a random integer in the range 1 to 7
  6.  */
  7. class Solution extends SolBase {
  8.     public int rand10() {
  9.         int num = (rand7() - 1) * 7 + rand7();
  10.         return num <= 40 ? num % 10 + 1 : rand10();
  11.     }
  12. }