Implement Rand10() Using Rand7() (M)
题目
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:
Input: 1
Output: [7]
Example 2:
Input: 2
Output: [8,4]
Example 3:
Input: 3
Output: [8,1,10]
Note:
rand7is predefined.- Each testcase has one argument:
n, the number of times thatrand10is called.
Follow up:
- What is the expected value for the number of calls to
rand7()function? - Could you minimize the number of calls to
rand7()?
题意
使用能够随机生成整数1-7的函数rand7()，来写一个新的函数rand10()，使其能够随机生成整数1-10。
思路
- (rand7()-1) 生成整数 0-6
- ((rand7()-1)times7) 生成整数 [0, 7, 14, ..., 42]
- ((rand7()-1)times7+rand7()) 生成整数 1-49，即得到 rand49()
- 利用拒绝采样来得到 1-40 范围内的随机整数num：通过rand49()得到一个数，如果大于40，则重新运行rand49()，否则赋值给num
- (num % 10+1) 得到 1-10 范围内的整数
代码实现
Java
/**
* The rand7() API is already defined in the parent class SolBase. public int
* rand7();
*
* @return a random integer in the range 1 to 7
*/
class Solution extends SolBase {
public int rand10() {
int num = (rand7() - 1) * 7 + rand7();
return num <= 40 ? num % 10 + 1 : rand10();
}
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
