LeetCode 319中等数学
灯泡开关 图解题解
这道题到底在问什么
初始有 n 盏灯全部关着。第 1 轮打开所有灯；第 2 轮把第 2、4、6… 盏（2 的倍数）切换一次；第 i 轮把第 i 的倍数那些灯各切换一次；一直做到第 n 轮。返回最后亮着的灯泡数。
- 输入
- n = 9
- 输出
- 3（最后第 1、4、9 盏亮着）
最优解：一步一步想明白
- 3核心：切换次数 = 约数个数；只有完全平方数的约数个数是奇数，所以最后亮的就是平方数位置，共 ⌊√n⌋ 盏。
- 4开始之前：9 盏灯全部是关着的，格子里写 0 表示灭、1 表示亮。
- 5第 1 轮，要切换的是 1 的倍数：第 1、2、3、4、5、6、7、8、9 盏灯（绿色标出）。切换就是亮↔灭翻一下。
- 6翻转后：第 1、2、3、4、5、6、7、8、9 盏灯各自亮灭互换了一次，现在亮着 9 盏。
- 7第 2 轮，要切换的是 2 的倍数：第 2、4、6、8 盏灯（绿色标出）。切换就是亮↔灭翻一下。
- 8翻转后：第 2、4、6、8 盏灯各自亮灭互换了一次，现在亮着 5 盏。
- 9第 3 轮，要切换的是 3 的倍数：第 3、6、9 盏灯（绿色标出）。切换就是亮↔灭翻一下。
- 10翻转后：第 3、6、9 盏灯各自亮灭互换了一次，现在亮着 4 盏。
- 11第 4 轮，要切换的是 4 的倍数：第 4、8 盏灯（绿色标出）。切换就是亮↔灭翻一下。
- 12翻转后：第 4、8 盏灯各自亮灭互换了一次，现在亮着 6 盏。
- 13第 5 轮，要切换的是 5 的倍数：第 5 盏灯（绿色标出）。切换就是亮↔灭翻一下。
- 14翻转后：第 5 盏灯各自亮灭互换了一次，现在亮着 5 盏。
- 15第 6 轮，要切换的是 6 的倍数：第 6 盏灯（绿色标出）。切换就是亮↔灭翻一下。
- 16翻转后：第 6 盏灯各自亮灭互换了一次，现在亮着 4 盏。
- 17第 7 轮，要切换的是 7 的倍数：第 7 盏灯（绿色标出）。切换就是亮↔灭翻一下。
- 18翻转后：第 7 盏灯各自亮灭互换了一次，现在亮着 3 盏。
- 19第 8 轮，要切换的是 8 的倍数：第 8 盏灯（绿色标出）。切换就是亮↔灭翻一下。
- 20翻转后：第 8 盏灯各自亮灭互换了一次，现在亮着 2 盏。
- 21第 9 轮，要切换的是 9 的倍数：第 9 盏灯（绿色标出）。切换就是亮↔灭翻一下。
- 22翻转后：第 9 盏灯各自亮灭互换了一次，现在亮着 3 盏。
- 239 轮结束，最后亮的是第 1、4、9 盏，恰好是 1²、2²、3²。它们的约数个数是奇数，所以被切了奇数次还亮着，共 3 盏 = ⌊√9⌋。
⚠️ 容易写错的地方
✗ 错：老老实实 n×n 模拟每一轮切换
✓ 对：用结论 ⌊√n⌋ 直接算
n 很大时（如 10^9）模拟会超时；数学结论是 O(1)
✗ 错：以为答案是亮灯位置之和或别的
✓ 对：答案是平方数的「个数」
题目要的是最后亮着的灯泡数量，不是位置或编号
✗ 错：用 (int)sqrt(n) 时不防浮点误差
✓ 对：必要时用 isqrt 或校正 ±1
浮点开方对某些大平方数可能差 1，整数平方根更稳
完整代码（Python / C++ / Java）
Python
import math
def bulbSwitch(n):
# 最后亮着的灯 = 1..n 里完全平方数的个数
return int(math.isqrt(n))C++
int bulbSwitch(int n){
// 答案 = floor(sqrt(n)) = 平方数个数
return (int)sqrt((double)n);
}Java
public int bulbSwitch(int n) {
// 答案 = floor(sqrt(n)) = 平方数个数
return (int) Math.sqrt(n);
}复杂度
时间
O(1)
直接对 n 开平方取整，不用真的模拟每一轮
空间
O(1)
只返回一个整数，不开任何数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 灯泡开关 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么切换次数等于约数个数？+
第 b 盏灯在第 k 轮被切换，当且仅当 k 整除 b。所以它被切换的次数就是 b 的约数个数，每个约数 k 贡献一次切换。
为什么只有完全平方数的约数个数是奇数？+
约数总是成对出现 d 和 b/d。当 d ≠ b/d 时成对、贡献偶数个；只有 b 是完全平方数时存在 d = √b = b/d 这一个落单的约数，使总数变成奇数。
n 很大（如 10^9）还能这么做吗？+
能，而且更必须。模拟是 O(n) 甚至更糟会超时；⌊√n⌋ 是 O(1)，对 10^9 也瞬间出结果，注意用整数平方根避免浮点误差。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 灯泡开关 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。