灯泡开关这道题我在过去三年整理的笔试真题里碰到过不下十次。它最常见的形态是 LeetCode 319 原题但很多公司会把它换个马甲继续考把灯泡换成教室里的灯、走廊里的门、棋盘上的格子。不管外壳怎么变核心问题都指向同一个数学结论——一个编号的灯泡最终亮不亮取决于这个编号被翻了多少次也就是它有多少个因数。下面这篇文章就从原题描述、数学推导、代码实现到面试官的连环追问把这题彻底拆开。适合正在准备笔试和面试的开发者也适合想拿它当数论入门题练手的人。我会把踩过的坑和笔试现场真正能用上的写法都写出来尽量让你看完之后不仅能 AC还能在面试官追问时把原理讲得滴水不漏。1. 先搞清楚题目在考什么1.1 原题描述LeetCode 319 的原文翻译过来是初始时有 n 个灯泡处于关闭状态。第一轮你打开所有灯泡第二轮每两个灯泡切换一次开关第三轮每三个灯泡切换一次开关第 i 轮每 i 个灯泡切换一次开关。第 n 轮结束之后返回亮着的灯泡数量。注意这里的“切换开关”不是“关闭”而是取反亮变灭、灭变亮。第一轮动了所有编号为 1 的倍数的灯泡也就是全部灯泡所以第一轮结束所有灯都会亮。第二轮动编号为 2、4、6……的灯泡它们又从亮变灭。这种描述方式经常被中文题解误写成“第二轮每两个关闭一个”虽然在小规模例子上不影响最终答案但严格来说会误导推导过程。很多面试官会在原题之前加一段实际场景比如“走廊里有 n 盏灯管理员每天按规律去拉开关”本质就是一回事。识别出题目外壳背后的“倍数翻转”模型比背诵答案更重要。1.2 三个高频外壳同一个模型换三个场景就变成了三道题。场景题目外壳考点灯泡LeetCode 319 Bulb Switcher因数个数奇偶性门经典 100 门问题平方数结论灯/棋盘笔试中的“切换开关”变体状态取反思维100 门问题更经典100 扇门一开始关着第 1 个学生把所有门打开第 2 个学生把编号是 2 的倍数的门全部切换一次第 3 个学生把编号是 3 的倍数的门全部切换一次……最后哪些门是开的。答案是 1、4、9、16……也就是 100 以内所有完全平方数共 10 扇。这题的年龄比大多数笔试题目都大但每一次出现都能刷掉一批只背结论、不推导的人。1.3 从笔试角度拆解考点这道题能成为笔试常客是因为它有鲜明的层次感。基础差的人只能写暴力模拟聪明一点的能发现平方数规律真正稳的人能把原理讲清楚还能应付各种变体。笔试里它主要考四件事一是数学归纳能力能不能从状态变化中抽出“翻转次数”这个不变量二是因数性质能不能想到因数成对出现、平方数例外三是复杂度意识n 的范围通常给到 10^9模拟必然超时四是表达能力即使写出了sqrt(n)面试官也一定会追问“为什么是这个答案”答不上来就等于没做。2. 核心数学原理翻转次数和因数个数是同一件事2.1 单盏灯的状态变化先看一盏编号为 k 的灯。它总共会被翻转几次第 i 轮会碰它当且仅当 i 是 k 的因数。所以 k 号灯在整个过程中的翻转次数恰好等于 k 的正因数个数。举个例子。编号 6 的因数有 1、2、3、6 共 4 个它会被翻转 4 次。由于初始状态是“灭”两次翻转会回到“灭”四次翻转依然是“灭”。编号 9 的因数有 1、3、9 共 3 个翻转 3 次从“灭”变“亮”。所以判断标准不是“被翻过几次”而是“被翻的次数是奇数还是偶数”。偶数次回到初始状态奇数次改变初始状态。这里最核心的思维转折是把“每一轮动了哪些灯”翻译成“每一盏灯被哪些轮动过”。前者是全局视角后者是单灯视角。笔试中一大半人卡住就是因为一直盯着全局过程没有切换到这个单灯视角。2.2 因数为什么成对出现任何一个正整数 k因数都是成对出现的。如果 a 是 k 的因数那么 k/a 也一定是 k 的因数。比如 6 的因数 1 和 6 成对、2 和 3 成对。成对意味着个数是偶数。但有一种特殊情况当 k 是完全平方数时中间那个因数会和它自己配对。比如 9 的因数 3k/a 9/3 3a 和 k/a 是同一个数没法形成两个不同的因数。于是因数总数变成了奇数。用生活类比就是平时都是一人一个座位成对坐完全平方数会多出一个“单人座”所以总数是奇数。这就是整道题的题眼。亮着的灯 编号有奇数个因数的灯 完全平方数。2.3 答案就是向下取整开方1 到 n 之间有多少个完全平方数完全平方数可以写成 1²、2²、3²……一直到 k²。只要 k² 不超过 n编号就是有效的。所以 k 最大能取到 floor(sqrt(n))答案就是 floor(sqrt(n))。拿 n 10 手算一遍验证1 到 10 里的完全平方数是 1、4、9共 3 个。按这个结论最终应该有 3 盏灯亮。如果写暴力模拟程序跑一遍结果确实就是 3。我建议你笔试前亲手把 n 4、n 5、n 10 三个小样例的正向切换过程画一遍比看十遍题解都有用。2.4 一个容易踩的认知误区有人会把这个结论推广错以为“第 t 轮结束后亮灯数等于 sqrt(t)”。这是错的。第 t 轮结束时每盏灯只被“小于等于 t 的因数”翻过不是被所有因数翻过。比如 n 10第 1 轮结束10 盏灯全亮而 floor(sqrt(1)) 1差的不是一点半点。只有在完整的 n 轮过程结束时每盏灯才可能被它的全部因数遍历到平方数结论才成立。这个误区在面试追问时特别常见。面试官的典型问法是“如果我把过程停在第 k 轮亮灯数是多少”你如果直接套 sqrt就会翻车。停下来观察每一盏灯的具体翻转次数才是正解。3. 代码实现三种层次的写法3.1 验证级实现暴力模拟笔试现场如果一时没推出来先写暴力模拟拿小样例的答案是非常合理的保底策略。它不是最终答案但能帮你在草稿纸上找到规律。def bulb_switch_brutal(n: int) - int: # 0 表示灭1 表示亮 bulbs [0] * (n 1) for i in range(1, n 1): for j in range(i, n 1, i): bulbs[j] 1 - bulbs[j] return sum(bulbs)这个写法的时间复杂度是 O(n log n)因为总操作次数约等于 n 乘以调和级数也就是 n * (1 1/2 ... 1/n) ≈ n log n。当 n 只有几百或者几千时完全没问题。LeetCode 官方给的 n 上限是 10^9这个写法必然超时所以它只能用来验证结论。3.2 笔试级实现不用浮点开方很多人一上来就写return int(sqrt(n))在小数据上没问题但浮点数开方在极端边界下可能返回 31622.99999 而不是 31623直接截断就会差 1。笔试环境下我最推荐的写法是手写整数二分开方稳定、不需要调库、还能向面试官展示基本功。def isqrt_floor(x: int) - int: # 在 [0, x] 中找最大的 k满足 k*k x lo, hi 0, x 1 # [lo, hi) 左闭右开 while lo 1 hi: mid (lo hi) // 2 if mid * mid x: lo mid else: hi mid return lo def bulb_switch(n: int) - int: return isqrt_floor(n)这里用左闭右开的二分写法是为了避免死循环。左闭右开区间保证每次循环区间长度都在缩小不会出现 lo 和 hi 相邻时 mid 等于 lo 导致无限循环的问题。对于 n 10^9二分大概只需要 30 次迭代完全够快。如果你不想写二分也有一个 O(sqrt(n)) 的朴素写法从 1 开始枚举 k直到 k*k 大于 n数一下有几个。这个写法在 n 10^9 时大约要跑 31623 次笔试绝对能过只是不够优雅。3.3 一行公式与语言细节在线笔试通常允许使用标准库Python 3.8 以上可以直接用math.isqrt它返回的是整数向下取整开方没有浮点精度问题。import math def bulb_switch_short(n: int) - int: return math.isqrt(n)C 里写成return (int)sqrt(n);在小数据没问题但如果题目数据范围扩大到 10^18double 的精度就会出问题。稳妥的写法是先算再微调int bulbSwitch(int n) { int ans (int)sqrt((double)n); while ((long long)(ans 1) * (ans 1) n) ans; while ((long long)ans * ans n) ans--; return ans; }Java 类似用(int) Math.sqrt(n)之后再上下微调一下。这个“先开方再校正”的思路本身就是面试中的一个亮点说明你清楚浮点数的边界问题。三种实现的取舍我简单总结一下实现时间复杂度空间复杂度适用场景暴力模拟O(n log n)O(n)小规模验证整数二分开方O(log n)O(1)笔试稳妥答案math.isqrtO(1) 内实现O(1)允许调库时的首选4. 面试官最爱追问的五个变体4.1 变体一初始全亮如果 n 个灯泡一开始全部是亮的其他规则不变最终答案是什么标准结论里最终亮着的是平方数编号。初始全亮相当于把标准结论取反平方数编号被翻奇数倍从亮变灭非平方数被翻偶数倍保持亮。所以答案变成 n - floor(sqrt(n))。这个变体几乎没有任何额外计算量但能立刻检验你到底是理解了过程还是背下了答案。面试官通常会在你说出sqrt(n)后马上补一句“那如果初始都是亮的呢”。4.2 变体二只问第 k 盏灯不给 n只给一个编号 k问这盏灯最终是亮还是灭。这个问题等价于判断 k 是不是完全平方数。因为单盏灯的状态只取决于翻转次数奇偶性。这里要注意浮点精度判断Python 里推荐这么写import math def single_bulb(k: int) - bool: r math.isqrt(k) return r * r k如果 k 是平方数返回 True 表示亮否则灭。笔试里出现这种单点问题时很多人会下意识再跑一遍完整模拟其实完全没必要。4.3 变体三给定初始状态数组如果初始状态不是全灭而是一个长度为 n 的数组init其中 1 表示亮、0 表示灭问最终状态数组。标准过程中第 k 号灯会被翻转“因数个数次”完全平方数的翻转次数是奇数非平方数是偶数。加上初始状态后每个位置只需做一次异或import math def final_state(init: list[int]) - list[int]: n len(init) res [0] * n for i in range(1, n 1): r math.isqrt(i) is_square (r * r i) res[i - 1] init[i - 1] ^ (1 if is_square else 0) return res这个 O(n) 的复杂度已经是理论最优因为你要读入整个数组。构造这类变体时面试官想考的是“位运算思维”和“状态叠加”的理解。4.4 变体四每轮只翻转前 i 个灯泡这是我最喜欢的一道变体因为它和原题用同一个模型但结论完全不同。规则改成第 i 轮只翻转编号 1 到 i 的灯泡其他灯泡不动。问最终亮灯数。第 k 号灯会被哪些轮碰到只有编号 i ≥ k 的轮次才会翻到它也就是第 k、k1、……、n 轮一共 n - k 1 次。最终状态由 n - k 1 的奇偶性决定。当 n 是偶数时k 为偶数的灯会亮当 n 是奇数时k 为奇数的灯会亮。综合起来答案就是 ceil(n/2)代码只有一行def variant_first_i(n: int) - int: return (n 1) // 2这个变体特别适合用来检验“单灯视角”有没有建立起来。很多人看到题目变化就慌但其实翻转次数还是那一个思维模型。4.5 变体五三开关一灯泡的逻辑推理题除了算法题这块还常以纯逻辑题出现你站在房间外面前有三个开关分别控制另一个房间的一盏灯。你只能进入灯的房间一次如何确定哪个开关控制灯标准答案是先打开 A 开关等几分钟让它通电发热然后关掉 A再打开 B 开关立刻进入房间。进去后如果灯亮就是 B 控制的如果灯灭但灯泡是热的说明刚才 A 开过是 A 控制的如果灯灭且灯泡是冷的就是 C 控制的。这道题和算法题看似无关其实内核相通光用“开关状态”做二值编码不够还得引入“温度”这个额外维度。对应到程序里就是状态不是只有 0/1还可以引入时间、历史、累积效应。面试官用这题考的是信息编码能力和跳出惯性思维的能力。与此类似的还有 LeetCode 672 Bulb Switcher II 和 LeetCode 1375 Bulb Switcher III一个考有限操作次数下的状态种类规律一个考前缀亮灯条件判断都属于这个“开关家族”。刷完原题后顺手刷这两题性价比非常高。5. 笔试实战常见错误与排查技巧5.1 错误速查表我把实际笔试里见到的典型错误整理成一张表答题前扫一眼能省很多时间。错误类型具体表现避免方式审题错误把“翻转 i 的倍数”看成“翻转前 i 个”先读清每一轮作用范围浮点精度int(sqrt(n)) 在边缘少 1用整数二分或 math.isqrt边界遗漏n0 时返回 1特判 n0返回 0类型截断C 里 (int)sqrt(大数) 精度不足long long 校验并上下微调复杂度失控n10^9 还跑暴力模拟先看数据范围再定算法解释不清只背“答案是 sqrt n”讲不出因数准备一句话推导5.2 手写整数开方的通用模板如果不允许用任何内置开方函数二分模板是你最可靠的武器。我习惯写成左闭右开循环条件用lo 1 hi这样不会死循环也不容易出现 mid 重复。def isqrt_floor(x: int) - int: lo, hi 0, x 1 while lo 1 hi: mid (lo hi) // 2 if mid x // mid: # 避免 mid*mid 溢出 lo mid else: hi mid return lo这里用x // mid代替mid * mid是为了防止大数乘法溢出Python 里无所谓但如果切到 C这是必须养成的习惯。笔试写代码时多考虑一步溢出面试官对你的印象分会有明显提升。5.3 笔试注释和草稿纸的得分技巧在线笔试的编辑器通常允许写注释我建议把数学推导直接写进注释里。比如# 第 k 个灯泡被翻转的次数 k 的因数个数 # 因数成对出现完全平方数有奇数个因数 # 所以亮灯数 完全平方数的个数 floor(sqrt(n))这不是废话而是给阅卷系统背后的面试官看的。很多公司在笔试后会调出代码回看有推导注释的代码和只有一行return sqrt(n)的代码评价完全不同。草稿纸上的习惯也很重要。遇到没见过的题先花三分钟手算 n1 到 5 的状态演化。比如 n5第一轮全亮第二轮 2、4 灭第三轮 3 灭第四轮 4 亮第五轮 5 灭最终亮的是 1 和 4答案 2正好等于 floor(sqrt(5))。这个“先小规模找规律”的习惯能帮你解决一半以上的笔试初读题。5.4 笔试现场的时间分配经验这道题如果出现在笔试里定位通常是“中等难度送分题”。我见过的最优策略是先花两分钟写暴力模拟拿小样例验规律再花三分钟写出数学结论和最终代码最后留两分钟准备解释。总计七分钟内解决比较理想。如果卡住了也不要和它死磕。先跳到后面的题回头再看时往往一眼就能看到平方数规律。考试状态下的“灵光一现”很多时候只是因为切换了脑区。6. 一道题吃透一类题刷题路径建议6.1 先做 100 门问题建立直觉如果你想彻底掌握这类题我建议从 100 门问题入手而不是直接从 LeetCode 319 开始。门的场景比灯泡更直观你可以用表格把前几个学生的操作一行行写出来观察哪些门被翻了奇数次。这个直观经验建立起来后再看到灯泡版本就能瞬间完成映射。6.2 三小时专题练习安排给准备笔试的朋友一个可执行的训练计划总耗时大约三个小时第 1 个小时手推 100 门问题并用暴力模拟验证到 n100然后做 LeetCode 319 原题要求自己不看题解写出整型二分版本。第 1.5 小时做变体一、变体二、变体四每一个都要求写出代码和一句推导。第 2.5 小时做 LeetCode 672 和 1375体会“开关家族”的不同考点。最后半小时整理一页“因数奇偶性”笔记包括一句话原理、三种实现、四个变体。这套组合练下来比零散刷十几道题更有体系感。笔试遇到同类型题目时你能很快定位到“这是因数奇偶性模型”。6.3 我的个人心得刷了这么多笔试题我对这种“模拟数学”类题目的体会是千万不要背公式。公式只值一行代码的分数推导过程才值面试官心里的那层肯定。你只需要记住一句核心话术“第 k 盏灯被翻转的次数等于 k 的因数个数因数都是成对出现的只有完全平方数中间那个因数和自身配对导致奇数个因数所以亮灯数等于 n 以内完全平方数的个数也就是 floor(sqrt(n))。”这句话背下来不难难的是真的想明白。想明白之后面试官把题目改成什么样你都有底气现场推导。另外一个容易被忽略的点是题目往往只问“数量”但面试官可能继续问“请输出亮灯编号”。这时候要在心里立刻切换成“遍历 1 到 n判断每个编号是不是完全平方数”的思路时间复杂度从 O(1) 变成 O(n)但这是必要的代价。提前有这个预期就不会在追问时慌了神。最后分享一个我自己的小习惯每刷到这类数学题我都会在笔记里单独建一页“因数奇偶性”专题把灯泡开关、百门问题、开关灯矩阵题放在一起。笔试前翻这一页花不了五分钟但命中率真的很可观。准备笔试的这段时间不要把每一道题当成孤岛试着把它们串成一张网你会在考场上发现很多“新题”其实都是老朋友换了身衣服。