LeetCode 319. 灯泡开关
题目描述
题意分析
灯泡编号为
1到n，初始全部关闭。第d轮切换所有编号为d的倍数的灯，经过n轮后，求仍然亮着的灯泡数量。每次切换都会把状态反转，因此一盏灯最终是否亮，只取决于它被切换的总次数是奇数还是偶数，不需要保存每一轮的状态。
解法：数学规律
核心思路
[!blue]
固定编号为
i的灯，只有轮次d能整除i时，它才会被切换。i的所有正约数都不超过i，也就不会超过总轮数n，所以切换次数恰好等于i的正约数数量。约数可以按
d与i / d配对。若i不是完全平方数，每一对都是两个不同的约数，约数总数为偶数；若i是完全平方数，只有平方根这一对的两个值相同，应当只算一次，其余约数仍然成对，总数就变成奇数。初始关闭的灯经过奇数次切换后亮，因此最终亮着的恰好是编号为正完全平方数的灯。满足
k * k <= n的正整数k有多少个，亮灯就有多少盏，答案为平方根向下取整。
解题步骤
- 将某盏灯的切换次数转换为它的正约数数量。
- 根据约数配对，得到“最终亮灯当且仅当编号是完全平方数”。
- 返回
sqrt(n)向下取整。n非负，转换为整数的截断方向正好是向下取整；n = 0时自然返回0。
代码实现
class Solution {
// 非完全平方数的因子成对出现，切换偶数次后会熄灭。
public int bulbSwitch(int n) {
return (int) Math.sqrt(n);
}
}
import "math"
func bulbSwitch(n int) int {
// 非完全平方数的因子成对出现，切换偶数次后会熄灭。
return int(math.Sqrt(float64(n)))
}
复杂度分析
- 时间复杂度：$O(1)$，固定数值范围内一次开方取整。
- 空间复杂度：$O(1)$，不保存灯的状态。
关键点总结
[!green]
- 从逐轮观察所有灯，转为单独统计一个编号会在哪些轮次被切换。
- 非平方数的约数全部成对，平方数只有平方根这一项没有另一个不同的配对。
- 不必枚举平方数，满足平方不超过
n的正整数数量直接等于平方根的整数部分。
易错点总结
[!yellow]
- 灯初始是关闭状态，因此奇数次切换后亮，偶数次后仍关闭。
- 灯的编号从
1开始，不能把0也当作一盏编号为平方数的灯。- 需要的是向下取整，不能四舍五入；超过
n的下一个平方数不对应任何现有灯泡。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 367. 有效的完全平方数 | 简单 | 只有完全平方数的因子个数为奇数，因此本题亮灯数量等于不超过n的完全平方数个数。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！