LeetCode题练习与总结：灯泡开关--319
一、题目描述
初始时有 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进行自增操作，这是常见的编程技巧。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。