LeetCode 319中等数学
灯泡开关 图解题解
这道题到底在问什么
初始时有 n 个灯泡处于关闭状态。第一轮，你打开所有灯泡；第二轮，每两个灯泡切换一次开关；第三轮，每三个灯泡切换一次开关；第 i 轮，每 i 个灯泡切换一次开关。第 n 轮，只切换最后一个灯泡。请返回 n 轮后有多少个亮着的灯泡。
- 输入
- n = 3
- 输出
- 1
- 解释
- 三轮后只有第 1 个灯泡亮着。
- 输入
- n = 0
- 输出
- 0
最优解：一步一步想明白
- 3所以第 k 盏灯被切换的次数，正好等于 k 的因子个数。
- 4最后亮着的灯，正是编号为完全平方数的灯：1、4、9、16...
- 5bulbs = [off] * 10为了看规律，只演示 n=10。真正代码不会模拟这些轮次。
- 6toggle multiples of 1第 1 轮打开所有灯泡。
- 7toggle multiples of 2能被 2 整除的灯，说明 2 是它的因子，所以这些灯多切换一次。
- 8toggle multiples of 3灯 6 被第 1、2、3 轮都碰过，后面第 6 轮还会再碰一次，总共偶数次，最后会灭。
- 9toggle multiples of 4灯 4 的因子是 1、2、4，一共 3 个。因为 2×2 配成自己，所以灯 4 最后会亮。
- 10after all rounds继续完成第 5 到第 10 轮后，只剩 1、4、9 亮着，它们都是不超过 10 的完全平方数。
- 116 的因子：1,2,3,6高亮灯 6：它会在第 1、2、3、6 轮被切换，共 4 次。偶数次切换后回到关闭。
- 129 的因子：1,3,9高亮灯 9：它会在第 1、3、9 轮被切换，共 3 次。3×3 的平方根只算一个因子，所以最后亮着。
- 13return int(n ** 0.5)亮着的编号 1、4、9 正好是 1²、2²、3²。不超过 n 的完全平方数有 ⌊√n⌋ 个，所以代码返回 int(n ** 0.5)。
- 16这题的关键不是模拟，而是把“第几轮会切换”翻译成“编号有哪些因子”。
⚠️ 容易写错的地方
✗ 错：真的模拟 n 轮
✓ 对：直接数完全平方数
n 大时模拟会超时，数学规律才是本题核心。
✗ 错：把偶数编号都当成灭、奇数编号都当成亮
✓ 对：只看是否为完全平方数
9 是奇数且亮，3 是奇数但灭。关键是因子个数。
✗ 错：返回 round(sqrt(n))
✓ 对：返回 floor(sqrt(n))
只统计不超过 n 的平方数，必须向下取整。
✗ 错：n=0 返回 1
✓ 对：n=0 返回 0
没有灯泡，也没有正完全平方数。
完整代码（Python）
Python
class Solution:
def bulbSwitch(self, n):
return int(n ** 0.5)复杂度
时间复杂度
O(1)
只做一次平方根计算。
空间复杂度
O(1)
不需要模拟灯泡数组。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 灯泡开关 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「数学」，换最直接的暴力解会差在哪？+
数学抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。