動機
這三小
Problem
Given the API rand7()
that generates a uniform random integer in the range [1, 7]
, write a function rand10()
that generates a uniform random integer in the range [1, 10]
. You can only call the API rand7()
, and you shouldn't call any other API. Please do not use a language's built-in random API.
Each test case will have one internal argument n
, the number of times that your implemented function rand10()
will be called while testing. Note that this is not an argument passed to rand10()
.
Follow up:
- What is the expected value for the number of calls to
rand7()
function? - Could you minimize the number of calls to
rand7()
?
Example 1:
Input: n = 1Output: [2]
Example 2:
Input: n = 2Output: [2,8]
Example 3:
Input: n = 3Output: [3,8,10]
Constraints:
1 <= n <= 105
Sol
為了讓機率平均,所以把1~49的組合對到1~10
但後面9個會多,所以要把後面9個擋掉
class Solution:
def rand10(self):
def get():
i,j = rand7(), rand7()
cnt = (i-1)*7+j
ret = cnt%10
return [ret if ret != 0 else 10, cnt < 41]
ret, good = get()
while not good:
ret, good = get()
return ret
另一個是看奇偶
int rand10(void)
{
int a, b;
do a = rand7(); while (a == 7);
do b = rand7(); while (b > 5);
return a & 1 ? b : b + 5;
}