Article / 文章
LeetCode 第319题：灯泡开关
初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。第二轮，你将会每两个灯泡关闭一个。 第三轮，你每三个灯泡就切换一个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换一个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。 找出并返回 n 轮后有多少个亮着的灯泡。
📖 文章摘要
本文详细解析LeetCode第319题“灯泡开关”，这是一道数学思维的问题。文章提供了基于完全平方数的解法，包含C#、Python、C++三种语言实现，配有详细的数学分析和性能对比。适合想要提升数学思维能力的程序员。
核心知识点： 数学、完全平方数、因数分解
难度等级： 中等
推荐人群： 具有基础数学知识，想要提升数学思维能力的程序员
题目描述
初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。第二轮，你将会每两个灯泡关闭一个。
第三轮，你每三个灯泡就切换一个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换一个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。
找出并返回 n 轮后有多少个亮着的灯泡。
示例
示例 1：
输入：n = 3
输出：1
解释：
初始状态: [关闭, 关闭, 关闭]
第一轮后: [开启, 开启, 开启]
第二轮后: [开启, 关闭, 开启]
第三轮后: [开启, 关闭, 关闭]
示例 2：
输入：n = 0
输出：0示例 3：
输入：n = 1
输出：1提示
- 0 <= n <= 10^9
解题思路
方法：数学分析
这道题的关键在于理解每个灯泡的状态变化规律。
关键点：
- 第i个灯泡的状态取决于它的因数个数
- 如果因数个数为奇数，最终状态为开启
- 只有完全平方数的因数个数为奇数
- 因此，答案就是不超过n的完全平方数的个数
具体步骤：
- 对于第i个灯泡，它会在第j轮改变状态，其中j是i的因数
- 如果i的因数个数为奇数，最终灯泡为开启状态
- 只有完全平方数的因数个数为奇数（因为其他数的因数都是成对出现）
- 因此，答案就是floor(sqrt(n))
时间复杂度：O(1) 空间复杂度：O(1)
图解思路
因数分析表
| 数字 | 因数 | 因数个数 | 最终状态 |
|---|---|---|---|
| 1 | 1 | 1 | 开启 |
| 2 | 1,2 | 2 | 关闭 |
| 3 | 1,3 | 2 | 关闭 |
| 4 | 1,2,4 | 3 | 开启 |
| 5 | 1,5 | 2 | 关闭 |
| 6 | 1,2,3,6 | 4 | 关闭 |
| 9 | 1,3,9 | 3 | 开启 |
完全平方数分析表
| n | 完全平方数 | 数量 | 说明 |
|---|---|---|---|
| 1 | 1 | 1 | √1 = 1 |
| 4 | 1,4 | 2 | √4 = 2 |
| 9 | 1,4,9 | 3 | √9 = 3 |
| 16 | 1,4,9,16 | 4 | √16 = 4 |
代码实现
C# 实现
public class Solution {
public int BulbSwitch(int n) {
return (int)Math.Sqrt(n);
}
}Python 实现
class Solution:
def bulbSwitch(self, n: int) -> int:
return int(n ** 0.5)C++ 实现
class Solution {
public:
int bulbSwitch(int n) {
return sqrt(n);
}
};执行结果
C# 实现
- 执行用时：20 ms
- 内存消耗：26.4 MB
Python 实现
- 执行用时：32 ms
- 内存消耗：15.0 MB
C++ 实现
- 执行用时：0 ms
- 内存消耗：5.9 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 20 ms | 26.4 MB | 实现简洁 |
| Python | 32 ms | 15.0 MB | 代码最简洁 |
| C++ | 0 ms | 5.9 MB | 性能最优 |
代码亮点
- 🎯 巧妙运用数学原理简化问题
- 💡 将复杂的模拟问题转化为简单计算
- 🔍 利用完全平方数的特性
- 🎨 代码极其简洁优雅
常见错误分析
- 🚫 尝试模拟整个过程（会超时）
- 🚫 没有理解因数个数与完全平方数的关系
- 🚫 整数溢出问题处理不当
- 🚫 对边界情况考虑不周
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 数学解法 | O(1) | O(1) | 效率最高，代码简洁 | 需要数学推导 |
| 模拟法 | O(n^2) | O(n) | 直观易懂 | 效率极低 |
相关题目
- LeetCode 672. 灯泡开关 Ⅱ - 中等
- LeetCode 1375. 灯泡开关 III - 中等
- LeetCode 1529. 灯泡开关 IV - 中等
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第319题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！