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

二、解题思路

1. 分析规律：观察每一轮灯泡的状态变化，可以发现，一个灯泡的状态变化次数取决于它的编号有多少个不同的因数。例如，编号为6的灯泡，在第1轮、第2轮、第3轮和第6轮会被切换，因为6有4个因数（1, 2, 3, 6）。如果一个灯泡的编号有奇数个因数，那么它最终会是亮着的；如果有偶数个因数，那么它最终会是关闭的。

2. 数学规律：一个数的因数通常是成对出现的，除了完全平方数。例如，4的因数有1、2、4，其中2出现了两次。因此，一个数如果是一个完全平方数，那么它就有奇数个因数。

3. 结论：经过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)，表示算法使用了固定数量的额外空间。

五、总结知识点

1. 类定义（Class Definition）:代码中定义了一个名为 Solution 的类，这是面向对象编程的基础。

2. 方法定义（Method Definition）:在 Solution 类中定义了一个公共方法 bulbSwitch，它接受一个整数参数 n 并返回一个整数，这是函数式编程的一个特点。

3. 变量声明与初始化（Variable Declaration and Initialization）:使用 int count = 0; 声明并初始化了一个整型变量 count，用于计数。

4. 循环结构（Loop Structure）:使用了一个 for 循环，这是控制流语句的一种，用于重复执行代码块。

5. 算术运算（Arithmetic Operations）:在循环条件中使用了乘法运算符 * 来计算 i 的平方，并与 n 进行比较。

6. 逻辑运算（Logical Operations）:循环条件 i * i <= n 使用了小于等于 (<=) 的逻辑运算符来确定循环的继续条件。

7. 增量运算（Increment Operation）:在 for 循环的末尾，使用 i++ 对变量 i 进行自增操作，这是常见的编程技巧。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。