一、题目描述
给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。
你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。
每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。
示例 1:
输入: 1 输出: [2]
示例 2:
输入: 2 输出: [2,8]
示例 3:
输入: 3 输出: [3,8,10]
提示:
1 <= n <= 10^5
二、解题思路
- 使用两次
rand7()调用来生成一个更大的均匀分布的整数范围。具体来说，将第一次调用的结果乘以 7，然后加上第二次调用的结果，这样我们可以得到一个 [1, 49] 范围内的整数。 - 由于我们需要的是 [1, 10] 范围内的整数，我们可以将 [1, 40] 范围内的整数映射到 [1, 10]，然后对 [41, 49] 范围内的整数进行重新采样。
- 使用取模运算和加法将 [1, 40] 范围内的整数映射到 [1, 10]。
三、具体代码
class Solution extends SolBase {
public int rand10() {
int result;
int num;
do {
// 生成一个 [1, 49] 范围内的均匀随机整数
num = (rand7() - 1) * 7 + rand7();
// 如果生成的数在 [41, 49] 范围内，则重新生成
} while (num > 40);
// 取模运算得到 [1, 10] 范围内的整数
result = num % 10 + 1;
return result;
}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
- 在
rand10()方法中，我们有一个 do-while 循环，这个循环会持续执行直到生成的num在 [1, 40] 范围内。 - 每次循环都会调用两次
rand7()方法。 rand7()方法返回一个 [1, 7] 范围内的随机数，因此(rand7() - 1) * 7 + rand7()会生成一个 [1, 49] 范围内的随机数。- 在 [1, 49] 范围内，有 40 个数是有效的（即 [1, 40]），而 9 个数是无效的（即 [41, 49]）。
- 因此，期望的循环次数是
1 / (40/49)，因为每次循环有40/49的概率生成一个有效的数。 - 由于
rand7()是常数时间操作，循环的期望时间复杂度为O(1)。
2. 空间复杂度
- 在
rand10()方法中，我们只声明了两个整型变量result和num。 - 这些变量占用的空间不随输入大小而变化，因此空间复杂度为
O(1)。
五、总结知识点
-
类继承：
class Solution extends SolBase：这行代码表明Solution类继承了SolBase类。继承是面向对象编程中的一个基本概念，允许子类继承父类的属性和方法。 -
方法重写：
public int rand10()：这是Solution类中的一个方法，它重写了父类SolBase中的rand7()方法，用于生成一个 [1, 10] 范围内的随机整数。 -
随机数生成：
rand7()：假设这是一个父类SolBase中定义的方法，用于生成一个 [1, 7] 范围内的随机整数。随机数生成是编程中常见的需求，用于模拟不确定性和概率性事件。 -
循环控制：
do { ... } while (num > 40);：这是一个 do-while 循环，它至少执行一次循环体，然后根据条件判断是否继续执行。这里用于确保生成的随机数在 [1, 40] 范围内。 -
算术运算：
(rand7() - 1) * 7 + rand7()：这行代码通过算术运算将两个 [1, 7] 范围内的随机数转换为一个 [1, 49] 范围内的随机数。这涉及到基本的算术运算，如减法、乘法和加法。 -
取模运算：
num % 10：取模运算符%用于计算一个数除以另一个数的余数。在这里，它用于将 [1, 40] 范围内的数映射到 [0, 9] 范围，然后通过加 1 将结果转换为 [1, 10] 范围。 -
变量声明和赋值：
int result;和int num;：声明了两个整型变量result和num，用于存储计算结果和中间计算值。 -
方法返回值：
return result;：这行代码用于从rand10()方法中返回计算得到的随机数。 -
条件判断：
while (num > 40);：这是一个条件判断，用于检查生成的随机数是否超出了我们需要的范围，如果是，则继续循环。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
标签：10,49,--,Rand10,40,rand7,num,Rand7,范围 From： https://blog.csdn.net/weixin_62860386/article/details/144479103