1. 问题引入从一盏灯到一百盏灯的逻辑迷宫“100盏灯问题”是技术面试中一个非常经典的逻辑与编程结合题。我第一次遇到它是在多年前的一次后端开发岗面试中面试官没有问任何框架细节而是抛出了这个问题。当时心里咯噔一下觉得这像是脑筋急转弯但静下心来分析后才发现它完美地考察了候选人的问题拆解能力、逻辑思维以及将数学洞察转化为代码实现的基本功。这道题之所以经久不衰是因为它用了一个极其简单的场景包装了关于因数、奇偶性和完全平方数等多个核心概念无论你是用Java、Python还是前端JavaScript都能用它来检验思维清晰度。简单描述一下场景一个房间里有编号为1到100的100盏灯初始状态全部是关闭的。门外有编号为1到100的100个人。第一个人1号进入房间把所有编号是1的倍数的灯的开关按一次即按遍所有100盏灯。接着第二个人2号进入房间把所有编号是2的倍数的灯的开关按一次。以此类推直到第100个人100号进入房间把所有编号是100的倍数的灯实际上只有第100盏灯本身的开关按一次。问题来了当这100个人都按完开关离开房间后请问最终有哪些灯是亮着的别急着写循环。我们得先抛开代码用逻辑和数学的眼光把这个问题看透。这道题表面上考的是模拟实际上考的是你能否发现规律避免写出时间复杂度为O(N²)的暴力解法。理解其本质无论是应对面试还是锻炼自己的算法思维都大有裨益。2. 核心思路拆解拨开迷雾寻找开关的数学本质要解决这个问题最笨的办法就是模拟用一个长度为100的布尔数组表示灯的状态然后写两层循环外层遍历1到100的人内层遍历当前人需要操作的灯进行状态取反。这个方法直观但效率不是最优而且没有体现出你对问题的深度理解。我们需要深入一步一盏灯的最终状态亮或灭由什么决定答案是它被按动开关的次数。如果被按了奇数次则状态与初始相反亮如果被按了偶数次则状态与初始相同灭。初始全部是灭的所以最终亮着的灯就是那些被按了奇数次的灯。那么关键问题转化为对于编号为n的灯它会被哪些人按到根据规则第k个人会按所有编号是k的倍数的灯。因此灯n会被按到当且仅当k是n的因数即k能整除n。所以灯n被按的次数就等于它的正因数的个数。于是问题的终极形态出现了在1到100中找出所有正因数个数为奇数的整数。因为只有这些灯被按了奇数次最终才会亮着。那么什么样的数其正因数个数是奇数呢这就是整个问题的画龙点睛之笔。我们可以列举一下数字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奇数。观察一下亮的灯号1, 4, 9... 这看起来像是平方数序列。没错完全平方数的正因数个数是奇数而非完全平方数的正因数个数是偶数。2.1 为什么完全平方数的因数个数是奇数这是数论中的一个基本性质。对于任意一个正整数n其因数总是成对出现的比如d和n/d。只有当d等于n/d时这一对因数才会“坍缩”成一个。而d n/d意味着d² n即n是一个完全平方数。此时这个因数d即sqrt(n)被单独计算了一次导致总因数个数由偶数变成了奇数。举个例子数字12非平方数因数对为 (1,12), (2,6), (3,4)。共3对6个因数偶数。数字16平方数因数对为 (1,16), (2,8), (4,4)。这里(4,4)是同一个数所以因数为1,2,4,8,16。共5个因数奇数。因此我们得到了最优雅的结论最终亮着的灯其编号是完全平方数。注意这个结论是解决问题的核心钥匙。在面试中如果你能直接推导出这一点并清晰地解释出来无疑会大大加分。它展示了你的逻辑推理能力和数学直觉。3. 从数学结论到代码实现有了“完全平方数”这个结论代码就变得异常简单。我们不需要模拟100个人的操作过程只需要找出1到100之间的所有完全平方数即可。3.1 多种语言实现方案这里给出几种常见面试语言的实现并分析其优劣。Python实现最简洁:def find_lights_math(n100): 基于数学规律的解法 lights_on [] i 1 while i * i n: lights_on.append(i * i) i 1 return lights_on print(find_lights_math()) # 输出: [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]这种解法的时间复杂度是O(sqrt(N))空间复杂度是O(k)k为完全平方数的个数。这是最优解。Java实现:import java.util.ArrayList; import java.util.List; public class HundredLights { public static ListInteger findLightsMath(int n) { ListInteger result new ArrayList(); for (int i 1; i * i n; i) { result.add(i * i); } return result; } public static void main(String[] args) { System.out.println(findLightsMath(100)); // 输出: [1, 4, 9, 16, 25, 36, 49, 64, 81, 100] } }JavaScript/TypeScript实现 (前端视角):function findLightsMath(n: number 100): number[] { const lightsOn: number[] []; for (let i 1; i * i n; i) { lightsOn.push(i * i); } return lightsOn; } console.log(findLightsMath()); // [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]3.2 作为对比的模拟解法虽然数学解法最优但面试官有时会要求你写出模拟过程以考察你的基本编码能力。这里也给出模拟解法并分析其陷阱。Python模拟解法:def find_lights_simulate(n100): 模拟开关过程的解法 # 初始化灯的状态False表示灭True表示亮 lights [False] * (n 1) # 索引从0开始我们使用1-100所以长度设为n1 for person in range(1, n 1): for light in range(person, n 1, person): # 从person开始步长为person lights[light] not lights[light] # 取反操作 # 收集亮着的灯 lights_on [i for i in range(1, n 1) if lights[i]] return lights_on print(find_lights_simulate())模拟解法的时间复杂度是O(N * (N/1 N/2 ... N/N))这近似于O(N log N)调和级数比O(N²)稍好但远不如O(sqrt(N))的数学解法。空间复杂度为O(N)。实操心得在面试中即使你一眼看出了数学规律也最好先和面试官沟通你的思路。你可以说“我观察到这个问题可以转化为求因数的奇偶性问题进而发现只有完全平方数满足条件。如果需要我也可以先写出模拟过程的代码。” 这样既展示了你的洞察力也体现了你扎实的编码基本功。4. 问题变形与深度考察点一个优秀的面试官不会只满足于标准答案。围绕“100盏灯”可以衍生出许多考察点这些才是区分普通候选人和优秀候选人的关键。4.1 变形一初始状态为全亮如果初始状态100盏灯全是亮的经过同样的100个人按开关后哪些灯是灭的解析逻辑完全不变。被按奇数次数的灯状态会改变从亮变灭。被按偶数次的灯状态不变保持亮。所以灭的灯仍然是编号为完全平方数的灯。结论不变但理解要透彻奇数次操作改变状态偶数次操作抵消。4.2 变形二第i个人按所有编号为i的倍数的灯但只按一次无论之前状态这个描述其实和原题一样。但有些候选人会纠结“只按一次”的表述其实它强调的是每个人的操作是独立的、一次的不是来回拨动。核心规则没变。4.3 变形三如果灯的数量是N人的数量是M (N ! M)这是更一般的推广。例如有150盏灯1-150但只有100个人1-100。问最后哪些灯亮解析此时对于编号大于100的灯它不会被编号大于它自身的人操作。但规律依然存在灯n亮当且仅当它在1到min(n, M)这个范围内拥有奇数个因数。更准确地说是拥有奇数个不超过M的因数。如果M n则退化为原问题看n是否为完全平方数。如果M n则需要找出n在1到M范围内的因数个数是否为奇数。这稍微复杂一些可能需要遍历判断或者寻找新的数学规律。4.4 变形四求第k盏灯被按了多少次这直接回到了我们的核心分析求数k的正因数个数。你可以写一个函数来计算。def count_factors(k): count 0 i 1 while i * i k: # 只需遍历到平方根 if k % i 0: count 1 # i是一个因数 if i ! k // i: # 避免重复计算平方根 count 1 # k//i是另一个因数 i 1 return count print(count_factors(12)) # 输出 6 print(count_factors(16)) # 输出 5这个函数的时间复杂度是O(sqrt(k))。4.5 考察点如何测试你的代码面试官可能会问“你会如何测试这个函数” 这是一个考察工程思维的好问题。边界测试N0, N1, N2。特别是N1时应该输出[1]。小规模验证手动模拟N10的情况与程序输出对比。比如N10完全平方数有1,4,9。可以手动推导验证。大规模验证用模拟法虽然慢但正确性容易理解的结果去验证数学解法快的结果确保两者在N较大时如N10000仍然一致。性能测试对数学解法输入一个很大的N如10^12看其速度。对模拟解法输入稍大的N如10^5感受其性能差异。5. 在面试中如何展现思考过程遇到这类问题不要急于编码。优秀的面试表现在于清晰的沟通和循序渐进的思考。澄清问题首先复述问题以确保理解正确。“您说的是100盏灯初始关闭100个人按倍数开关最后问亮灯的对吗有没有其他边界条件”提出暴力解法先给出最直观的想法。“最直接的方法是模拟用一个数组记录状态两层循环进行状态翻转。”分析复杂度指出暴力解法的问题。“模拟解法的时间复杂度大概是O(N log N)或O(N²)空间复杂度O(N)。对于N100没问题但如果N很大效率不高。”寻找规律这是关键一步。“我们深入一步一盏灯的状态取决于它被操作的次数。操作次数等于它的编号的因数个数。所以问题变成找因数个数是奇数的数。”数学洞察给出核心结论。“我想到因数是成对出现的。只有当这个数是完全平方数时它的平方根因数会单独出现导致总因数个数为奇数。所以亮着的灯就是1到100之间的所有完全平方数。”给出优化解基于结论写出高效代码。“所以我们只需要遍历1到10因为10²100输出每个数的平方即可。时间复杂度是O(sqrt(N))。”代码实现写出简洁、健壮的代码。注意处理输入参数、边界和返回值。讨论变形与测试主动提出可能的变种问题和测试方法展现思维的全面性。6. 从问题到工程思维的延伸这道题不仅仅是一道面试题它蕴含的思维模式在软件开发中随处可见。优化意识从模拟到数学解的跨越体现了对算法进行“降维打击”的优化思想。在工程中面对一个耗时的批处理任务我们是否也能找到类似的内在规律将O(N²)的复杂度优化到O(N)甚至O(log N)例如某些统计问题可以通过前缀和、差分数组来优化。问题转化能力将“灯亮灭”转化为“操作次数”再转化为“因数个数”最后转化为“完全平方数判断”。这种将业务问题抽象为数学模型的能力是解决复杂系统设计的关键。比如设计一个缓存淘汰策略LRU其本质是维护一个有序结构设计一个分布式ID生成器可能利用了类似雪花算法的位运算思想。测试与验证我们提到用慢速但正确的模拟法去验证快速但复杂的数学解法。这对应着工程中的“双写验证”或“影子测试”策略。在新旧系统迁移、算法替换时用旧逻辑的结果来验证新逻辑是保证稳定性的有效手段。边界思维考虑N0N1的情况。这对应着编程中的防御性编程和边界条件检查。一个健壮的函数必须能处理各种边缘输入。7. 常见“坑点”与面试失误实录根据我担任面试官和与同行交流的经验很多候选人在这个问题上会踩一些坑。数组下标从0开始导致的Off-by-one错误这是最常见的错误。在模拟法中灯编号是1到100但数组索引通常是0到99。如果不做映射直接操作lights[person]会漏掉第1盏灯或导致数组越界。正确的做法是分配长度为101的数组忽略下标0或者使用下标减1的映射。# 错误示范 lights [False] * 100 for person in range(100): # person从0到99 for light in range(person, 100, person1): # 逻辑混乱 ... # 正确示范使用长度N1忽略索引0 lights [False] * (101) # 索引0-100 for person in range(1, 101): for light in range(person, 101, person): lights[light] not lights[light]误解题意认为第i个人只按第i盏灯这是没有仔细读题。题目明确是“编号为i的倍数的灯”是倍数不是等于。一定要和面试官确认清楚。只给出答案没有推导过程直接回答“1,4,9...100”然后结束。面试官想知道的是你的思维路径而不是背诵答案。即使你知道结论也要一步步推导出来。无法证明“完全平方数因数个数为奇数”这是核心难点。如果被问到“为什么”支支吾吾说不出来会很扣分。务必理解并能够清晰阐述“因数成对出现平方数因数对重合”这个逻辑。代码冗长缺乏封装把所有的逻辑都写在main函数里。更好的做法是写一个接收参数N的函数提高代码的可读性和可测试性。忽视扩展性讨论当面试官问“如果N很大怎么办”时只回答“数学解法很快”。可以进一步讨论如果N大到10^15你的解法是否依然有效数学解法依然有效因为只需要循环到sqrt(N)大约10^7.5次迭代在现代计算机上可行。这展示了你的 scalability 思考。8. 不同技术岗位的侧重点这道题虽然通用但不同岗位的面试官关注点可能不同。后端/算法岗最关注数学规律的推导、时间/空间复杂度分析、变种问题的解决思路。可能会深入问及因数个数计算的更优算法如利用质因数分解公式。前端岗除了逻辑可能关注代码的清晰度、函数封装以及能否用前端方式演示这个过程例如用HTML/CSS/JS动态展示100个灯泡的开关过程。这考察将逻辑转化为可视化交互的能力。测试岗可能会非常关注测试用例的设计。如何设计测试用例来覆盖边界情况、错误情况如何验证结果的正确性这正好对应了我们前面讲的测试策略。嵌入式/硬件相关岗可能会引申到位操作。灯的开关状态可以用一个二进制位来表示100盏灯可以用100个bit如两个64位整数来存储。按开关操作可以用**异或(XOR)**运算来高效模拟。这考察了位运算和空间优化能力。// 简化的C语言思路用位域或整数数组 unsigned long long lights_low 0; // 表示1-64号灯 unsigned long long lights_high 0; // 表示65-100号灯实际用不到所有位 // 第k个人操作将所有k的倍数的bit取反。这需要一些位运算技巧。无论面对哪个岗位理解问题本质、清晰沟通、写出健壮代码这些都是共通的加分项。这道“100盏灯”就像一块试金石能照出一个程序员的基础思维是扎实还是浮夸。下次面试再遇到它希望你能从容地拨动逻辑的开关让思路清晰亮起。