做设计网站的工作怎么样,图表设计网站,网站永久空间,wordpress 相关文章 tag一、题目描述
初始时有 n 个灯泡处于关闭状态。第一轮#xff0c;你将会打开所有灯泡。接下来的第二轮#xff0c;你将会每两个灯泡关闭第二个。
第三轮#xff0c;你每三个灯泡就切换第三个灯泡的开关#xff08;即#xff0c;打开变关闭#xff0c;关闭变打开#x…一、题目描述
初始时有 n 个灯泡处于关闭状态。第一轮你将会打开所有灯泡。接下来的第二轮你将会每两个灯泡关闭第二个。
第三轮你每三个灯泡就切换第三个灯泡的开关即打开变关闭关闭变打开。第 i 轮你每 i 个灯泡就切换第 i 个灯泡的开关。直到第 n 轮你只需要切换最后一个灯泡的开关。
找出并返回 n 轮后有多少个亮着的灯泡。 示例 1 输入n 3
输出1
解释
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 你应该返回 1因为只有一个灯泡还亮着。示例 2
输入n 0
输出0示例 3
输入n 1
输出1提示
0 n 10^9
二、解题思路 分析规律观察每一轮灯泡的状态变化可以发现一个灯泡的状态变化次数取决于它的编号有多少个不同的因数。例如编号为6的灯泡在第1轮、第2轮、第3轮和第6轮会被切换因为6有4个因数1, 2, 3, 6。如果一个灯泡的编号有奇数个因数那么它最终会是亮着的如果有偶数个因数那么它最终会是关闭的。 数学规律一个数的因数通常是成对出现的除了完全平方数。例如4的因数有1、2、4其中2出现了两次。因此一个数如果是一个完全平方数那么它就有奇数个因数。 结论经过n轮后亮着的灯泡数量等于不大于n的完全平方数的数量。
基于以上思路我们可以直接计算不大于n的完全平方数的数量即计算从1到n的每个数判断它是否是完全平方数。
三、具体代码
class Solution {public int bulbSwitch(int n) {// 初始化亮着的灯泡数量int count 0;// 从1开始计算每个数的平方直到平方数大于nfor (int i 1; i * i n; i) {count;}return count;}
}四、时间复杂度和空间复杂度
1. 时间复杂度
该算法中我们有一个循环循环的条件是 i * i n。这意味着循环将执行直到 i 的平方大于 n。换句话说循环将执行大约 sqrt(n) 次因为 i 的值将从 1 增长到 sqrt(n)。
因此该算法的时间复杂度是 O(√n)。
2. 空间复杂度
该算法中我们使用了一个整型变量 count 来计数亮着的灯泡数量以及一个整型变量 i 作为循环的迭代器。这两个变量都是常数空间不随输入 n 的大小而变化。
因此算法的空间复杂度是 O(1)表示算法使用了固定数量的额外空间。
五、总结知识点 类定义Class Definition:代码中定义了一个名为 Solution 的类这是面向对象编程的基础。 方法定义Method Definition:在 Solution 类中定义了一个公共方法 bulbSwitch它接受一个整数参数 n 并返回一个整数这是函数式编程的一个特点。 变量声明与初始化Variable Declaration and Initialization:使用 int count 0; 声明并初始化了一个整型变量 count用于计数。 循环结构Loop Structure:使用了一个 for 循环这是控制流语句的一种用于重复执行代码块。 算术运算Arithmetic Operations:在循环条件中使用了乘法运算符 * 来计算 i 的平方并与 n 进行比较。 逻辑运算Logical Operations:循环条件 i * i n 使用了小于等于 () 的逻辑运算符来确定循环的继续条件。 增量运算Increment Operation:在 for 循环的末尾使用 i 对变量 i 进行自增操作这是常见的编程技巧。
以上就是解决这个问题的详细步骤希望能够为各位提供启发和帮助。
