一、题目描述
初始时有 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开始,计算每个数的平方,直到平方数大于n
for (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
进行自增操作,这是常见的编程技巧。
以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。
标签:319,--,复杂度,平方,灯泡,因数,循环,关闭,LeetCode From: https://blog.csdn.net/weixin_62860386/article/details/142992313