这道题我印象深刻。上个月帮人模拟笔试一道灯泡开关对面哥们看完题目嘴角扬起心想这是什么送分题直接两层循环模拟翻转。结果看到参数范围那个瞬间笑容凝固了——n是十的九次方量级。我当场就笑了这道题名字起得真客气看着是人畜无害的模拟实际是来收编只会写模拟的人的。灯泡开关是一道非常典型的笔试筛选器它想考察的不是你会不会写循环而是你有没有意识到有些问题表面上在考编码实际上在考数学直觉。这道题在LeetCode上是319题在各大厂笔试里也反复出现披着模拟的外衣考数论。今天这篇就把它的来龙去脉掰开揉碎讲清楚看完你不仅在笔试里能秒杀这题还能顺手看懂它的一整串变形题。1. 一道看起来能暴力实际想让你放弃暴力的题1.1 题目在说什么以n10手算一次先把题目定个型。假设有n个灯泡编号从1到n初始全部关闭。接下来进行n轮操作第i轮翻转所有编号为i的倍数的灯泡。翻转的意思就是开着变关关着变开。问你第n轮操作结束后有多少个灯泡是亮着的。听起来很简单对吧我习惯遇到这种题先手算一个小规模样例比如n10把每一轮的翻转结果列出来这样比空想直观得多。灯泡编号被哪些轮次翻转翻转次数最终状态111亮21, 22灭31, 32灭41, 2, 43亮51, 52灭61, 2, 3, 64灭71, 72灭81, 2, 4, 84灭91, 3, 93亮101, 2, 5, 104灭n10的时候结果是3个灯泡亮着亮灯编号是1、4、9。到这一步规律其实已经呼之欲出了——亮着的灯泡编号全是完全平方数11²42²93²。但注意这只是n10的观察结果还不能当作定论。做笔试题最忌讳的就是看到三个点就总结规律你得先明白这规律是怎么来的才能确定它在大数据范围下依然成立。1.2 为什么说这道题阴如果说最终规律是平方数是终点那这道题的恶意就藏在起点。如果n给的是10⁹你老老实实写个模拟外层循环跑n次内层循环平均也得跑n/2次总操作量是十万亿级别跑完怕是笔试都结束了。所以这道题真正想干的事是逼你停下来想灯泡的翻转次数到底取决于什么一旦开始想这个问题你就会被引导到约数个数的方向上。这也是为什么我反复强调笔试里遇到看起来能做但数据范围非常离谱的题第一反应不应该是优化循环而是重新审视问题本身。2. 暴力模拟法写得出来不一定跑得完2.1 朴素的翻转实现不管怎么说暴力模拟是理解这道题的第一步。代码写起来很直接用一个布尔数组记录灯泡状态第i轮把所有下标为i的倍数的元素取反。int bulbSwitch(int n) { vectorchar bulbs(n 1, 0); // 0表示灭1表示亮 for (int i 1; i n; i) { for (int j i; j n; j i) { bulbs[j] ^ 1; } } int ans 0; for (int i 1; i n; i) { if (bulbs[i]) ans; } return ans; }这里我用vectorchar而不是vectorbool因为vectorbool在C里是个特化容器内部按位存储虽然省内存但行为有时不符合常规预期面试笔试中没必要踩这个坑。内层循环的起始位置是j i而不是j 1理由很简单编号小于i的灯泡不可能是i的倍数从i开始遍历能省掉一半无意义的判断。这个实现的正确性毋庸置疑但它到底有多慢你计算一下总的翻转次数第1轮翻转n次第2轮翻转n/2次第3轮翻转n/3次……总次数是n/1 n/2 n/3 ... n/n n * (1 1/2 1/3 ... 1/n)括号里的调和级数收敛速度很慢近似等于ln(n)再加上欧拉常数γ约0.577。所以总的操作量大约是n ln n。2.2 暴力与公式的分水岭在哪里用具体数字感受一下n总翻转次数估算暴力可行性10⁴约9万次轻松10⁵约120万次轻松10⁶约1380万次勉强可以10⁷约1.6亿次开始吃力10⁸约18亿次基本超时10⁹约200亿次彻底没戏笔试里这题敢把n开到10⁹就是在明明白白告诉你别模拟了去寻找O(1)的解法。但暴力代码也不是白写的它最大的价值在于当你在笔试现场拿不准公式的时候可以用暴力跑n100以内的数据来验证你的猜想。这是后话后面我会专门讲这个技巧。3. 破题的关键一步翻转次数就是约数个数3.1 把轮次翻译成整除关系现在来干正事。我们单独盯着某一个灯泡比如编号为k的灯泡它什么时候会被翻转第i轮会翻转所有编号为i的倍数的灯泡也就是说灯泡k在第i轮被翻转当且仅当k是i的倍数换个说法就是i能整除k。这句话反过来读更顺k的每一个约数i都会对应一次翻转。所以结论很简单也很关键灯泡k在整个过程中的翻转次数恰好等于k的正约数个数。数论里通常记作d(k)或τ(k)。为什么说这个转化是破题点因为原本的问题是二维的你有n个轮次n个灯泡看起来像一张n×n的表格。但换个角度后每个灯泡的状态只取决于它自己的一个一维属性——约数个数。维度直接降下来了复杂度分析的目标也从模拟所有轮次变成了分析约数个数的性质。3.2 约数的成对出现与唯一的落单者有了翻转次数 约数个数这个翻译题目就变成了哪些数k它的约数个数是奇数初始状态灯泡是灭的翻转一次变亮翻转两次变灭翻转三次变亮……所以翻转奇数次最终就是亮的。问题进一步收敛为什么样的数有奇数个约数答案藏在约数的配对规律里。随便取一个数比如12它的约数是1、2、3、4、6、12。你会发现这些约数可以两两配对(1, 12)、(2, 6)、(3, 4)每一对的乘积都是12。只要d不等于k/d约数d就总能找到另一个约数和它配对成对出现的约数贡献了偶数个名额。那什么时候配对会失败当d k/d的时候也就是k d²的时候。这个时候d和自己配了对这个落单的约数不会被消耗掉约数个数就比偶数多了一个变奇数。我到这一步通常会给学生打个比方约数配对就像舞会入场券每个约数都该找个人组队但完全平方数的中间那个约数比较特殊它只能自己抱着自己跳于是队伍数量多了个单数。这个单数的一支队伍决定了灯泡最终是亮的。4. 为什么只有完全平方数是特例数论视角补一刀4.1 用标准分解式看约数个数的奇偶性约数成对出现这个解释已经很直观了但笔试里万一遇到追问面试官可能会想听更严谨的数论表达。这里补一刀整数k可以写成标准分解式k p1^a1 * p2^a2 * p3^a3 * ... * pm^am其中p1、p2……是互不相同的质数a1、a2……是对应的指数。约数个数的计算公式是d(k) (a1 1) * (a2 1) * (a3 1) * ... * (am 1)这个公式的来历不复杂k的任意一个约数它的每个质因子的指数只能从0到ai之间取所以每个质因子有ai1种选择乘法原理相乘即可。现在要让d(k)是奇数。奇数乘以奇数才是奇数只要任何一个因子是偶数乘积就是偶数。所以每个括号(ai 1)都必须是奇数。这意味着每个ai都必须是偶数。每个指数都是偶数这样的数是什么正是完全平方数。这个角度实际上给前面的配对论提供了代数证明也能让你在面试时显得更专业。但如果你觉得记公式麻烦成对配对那个思路已经完全够用了笔试不是写论文能自圆其说就行。4.2 答案公式亮着的灯编号是一串平方数把前面的结论串起来灯泡k翻转次数 约数个数d(k)d(k)为奇数当且仅当k是完全平方数初始熄灭翻转奇数次后点亮所以最终亮着的灯泡其编号一定是1²、2²、3²……这些完全平方数中不超过n的那些。答案是这些编号的个数也就是满足i²≤n的最大整数i即⌊√n⌋。用数学语言写就是ans floor(sqrt(n))回到n10的例子⌊√10⌋ 3亮灯编号是1、4、9完全吻合之前手算的结果。到这儿题目从一个n×n的模拟问题变成了一行求平方根的问题复杂度从O(n log n)直接降到了O(1)或者O(log n)。5. 五个语言写完这题的O(1)解法以及防精度坑5.1 各语言实现对照表公式已经出来了代码就没什么技术含量了。关键是各语言在求整数平方根时的微小差异容易在笔试环境里出问题。C#include cmath class Solution { public: int bulbSwitch(int n) { return (int)sqrt(n); } };Javaclass Solution { public int bulbSwitch(int n) { return (int)Math.sqrt(n); } }Pythonimport math class Solution: def bulbSwitch(self, n: int) - int: return math.isqrt(n)Goimport math func bulbSwitch(n int) int { return int(math.Sqrt(float64(n))) }JavaScriptvar bulbSwitch function(n) { return Math.floor(Math.sqrt(n)); };5.2 浮点开方可能踩的坑与二分替代法上面这些写法里C、Java、Go、JavaScript走的都是浮点开方再转整型的路子。大多数情况下没问题但做笔试的人应该养成一个习惯凡是涉及浮点转整数都要问自己一句精度够不够稳。浮点开方的风险在于某些完全平方数比如25开方后理论结果是5.0但浮点运算底层算出来的可能是4.999999999999取整就成4了。这种问题在数据量大的时候不是会不会发生而是什么时候发生。我个人的处理习惯是加一个回验花不了几行代码但能把精度坑彻底填平int bulbSwitch(int n) { int q (int)sqrt(n); // 如果下一位的平方也不超过n说明浮点结果偏小了 if ((long long)(q 1) * (q 1) n) q; return q; }注意这里转long long的原因当q接近46340的时候q²会逼近int类型的上限2.1×10⁹直接乘会溢出。笔试环境里这种隐蔽的溢出错比算法想不出来还要冤。如果你对浮点完全不放心还可以用整数二分来求平方根复杂度O(log n)对n10⁹来说也就三十次循环完全可以在毫秒级跑完int bulbSwitch(int n) { long long l 0, r n, ans 0; while (l r) { long long mid l (r - l) / 2; if (mid * mid n) { ans mid; l mid 1; } else { r mid - 1; } } return (int)ans; }二分法的优势是不依赖浮点环境纯整数运算没有精度问题笔试时如果时间紧张、不敢赌sqrt的精度直接上这个版本最省心。Python的话就没这些纠结math.isqrt内部就是纯整数的平方根算法专门为这种场景设计的性能好而且绝对精确。5.3 用暴力脚本验证公式写代码最怕的就是公式背错了但是自己不知道。我有一套固定的验证方法写一个暴力版本再写一个公式版本然后在小范围内对拍。保证公式正确性的同时也能加深自己对题目的理解。import math def brute(n): bulbs [False] * (n 1) for i in range(1, n 1): for j in range(i, n 1, i): bulbs[j] not bulbs[j] return sum(bulbs) def fast(n): return math.isqrt(n) for n in range(1, 1000): if brute(n) ! fast(n): print(mismatch at, n) break else: print(all ok)这段脚本我在笔试复习时跑过很多次输出all ok的那一刻你对这个公式的信心会变得非常足。这个暴力公式对拍的习惯不只是这道题适用几乎所有需要找规律的笔试题都能用。笔试环境如果允许本地写代码这就是你的私人纠错器。6. 笔试现场才需要懂的延申这题的亲戚们6.1 变体一输出亮灯编号而不是数量有些笔试不会问亮灯有多少个而是让你列出所有亮着的灯泡编号。这个更简单因为亮灯编号就是1²、2²、3²……一直乘到超过n为止vectorlong long getOnBulbs(int n) { vectorlong long ans; for (long long i 1; i * i n; i) { ans.push_back(i * i); } return ans; }注意循环变量用long long因为i*i在i达到46341时就会超出int范围。这个变体的考点其实已经从数学转向了你有没有处理溢出的意识。6.2 变体二名字相同、解法不同的灯泡开关IILeetCode上还有一道题叫灯泡开关II名字看起来和这道题是双胞胎实际上完全是另一路货色。那道题里有四个功能不同的开关按钮可以按m次问最后能得到多少种不同的灯泡状态组合。解法和约数没关系需要分析按钮操作之间的等价关系用状态压缩枚举可能的状态。笔试时如果看到灯泡开关后面带罗马数字建议先别急着套平方数结论把题目完整读一遍再说。这种同名不同解的题目其实也是出题人故意埋的坑想考你有没有认真审题。我见过不止一个人看到灯泡两个字就开始写sqrt结果整道题跑偏。6.3 变体三关灯游戏与异或方程组还有一个相关的经典问题叫Lights Out中文常翻译成关灯游戏或灭灯游戏。面板是一个m×n的格子矩阵点一个格子会翻转自己和上下左右五个格子的状态要求把所有灯熄灭。这类问题的思路和这道题完全不同不再考约数而是考线性代数里的异或消元每个格子的点击次数要么是0要么是1最后列一个异或方程组解出来即可。把这个亲戚列出来是想说明一个道理灯泡开关这系列的题目核心都在翻转奇偶性上落点却各不相同。有的落在约数、有的落在状态组合、有的落在方程组。笔试准备时背结论不如练思维遇到翻转类题目先想清楚这个翻转受什么影响、影响能不能用数学结构表达就成功了一大半。笔试策略上我自己总结了一条实战经验看到n的取值范围大到离谱同时题面上出现倍数、整除、约数、轮次这类词汇先别着急开循环停下来手算几个小样例观察输出序列的规律再回头想为什么。这个习惯在灯泡开关上帮我省了至少十分钟那十分钟足够把整张卷子的其他题目再检查一遍。如果你在考场上实在推不出公式也有一个保底策略先提交一版暴力解保证小数据范围内的分数到手再利用剩余时间思考优化。很多OJ是按数据范围分档给分的暴力能拿一部分分公式解能拿满分别让完美主义害得你连保底分都没拿到。灯泡开关这道题表面考的是灯泡和开关实际考的是你敢不敢在能写和能过之间选择后者。刷题刷多了你会发现真正拉开差距的往往不是coding的熟练度而是遇到反常数据范围时那种停下来想的定力。希望这篇把规律讲透、把坑填平的再读版能让你下次在笔试里遇见它时多一分从容少一分慌张。