LeetCode 319. 灯泡开关

2026-03-06 HGNULB 约 8 分钟

文章信息 8 个分类 2 个标签

分类

题目描述

✅ 319. 灯泡开关

题意分析

有 $n$ 盏灯，编号 1 到 $n$，初始全灭。做 $n$ 轮操作：第 1 轮打开所有灯；第 2 轮把编号是 2 的倍数的灯反转；第 3 轮把编号是 3 的倍数的灯反转；一直到第 $n$ 轮只反转第 $n$ 盏。问最后有多少盏灯是亮的。

要什么：亮灯的数量，不需要知道具体是哪几盏。这一点很重要，它允许我们只做计数而不必还原状态。

约束透露的信号：$n$ 最大到 $2 \times 10^9$ 级别，连开一个长度为 $n$ 的布尔数组都不可能，更别说 $O(n^2)$ 地逐轮反转。一个连 $O(n)$ 都不被允许的数据规模，几乎就是在明说「答案有闭式解」——必须把整个模拟过程压缩成一个可以直接算出来的表达式。所以这道题的全部工作在纸上，不在键盘上。

另一个关键观察点藏在操作的定义里：第 $i$ 盏灯只有在第 $d$ 轮且 $d$ 能整除 $i$ 时才被碰一次。也就是说，每盏灯被反转的次数完全由它编号的约数个数决定，与其他灯毫无关系。灯与灯之间没有耦合，可以逐盏独立判定。

边界：$n = 0$ 时没有灯，答案 0；$n = 1$ 时只有一盏灯，第 1 轮被打开后再没有第二轮，答案 1；$n = 3$ 时答案仍是 1，因为 2 和 3 都被反转了两次。

解法：数学规律

核心思路

暴力做法是老老实实开一个长度 $n+1$ 的布尔数组，外层枚举轮次 $d$ 从 1 到 $n$，内层以步长 $d$ 跳着反转。这是调和级数求和 $n/1 + n/2 + \dots + n/n \approx n \ln n$，时间约 $O(n \log n)$、空间 $O(n)$。在 $n$ 达到十亿级时，空间先爆，时间也远远超时。瓶颈很明确：我们逐个模拟了每一次反转，而题目只要最终亮灯的总数。

顺着「灯与灯互不影响」这条线索，把问题降到单盏灯：第 $i$ 盏灯初始是灭的，被反转了 $d(i)$ 次（$d(i)$ 表示 $i$ 的正约数个数）。灭 → 亮 → 灭 → 亮 …… 所以：
\[\text{第 } i \text{ 盏灯最终亮} \iff d(i) \text{ 是奇数}\]
现在的问题变成：1 到 $n$ 中有多少个数的约数个数是奇数？

关键观察在这里：约数天然是成对出现的。若 $a \mid i$，则 $i / a$ 也是 $i$ 的约数，$(a,\ i/a)$ 构成一对。把所有约数这样两两配对，个数应当是偶数——除非某一对里的两个数重合，即 $a = i / a$，也就是 $i = a^2$。于是：
\[d(i) \text{ 是奇数} \iff i \text{ 是完全平方数}\]
至此题目彻底变形：求 1 到 $n$ 中完全平方数的个数。完全平方数就是 $1^2, 2^2, 3^2, \dots$，满足 $a^2 \le n$ 的正整数 $a$ 的个数即为答案，也就是
\[\text{answer} = \lfloor \sqrt{n} \rfloor\]
整个推导链条是：反转次数 = 约数个数 → 约数成对配对 → 只有完全平方数落单 → 计数变成开方取整。最终代码只有一行，但这一行背后是三步等价变换。

解题步骤

把「第 $i$ 盏灯的最终状态」翻译成「$i$ 的约数个数的奇偶性」。为什么可以这样翻译：第 $d$ 轮只碰编号为 $d$ 倍数的灯，所以第 $i$ 盏灯被碰的轮次集合恰好是 $i$ 的全体正约数；灯从灭出发，被碰奇数次才亮。

把「约数个数为奇数」判定为「$i$ 是完全平方数」。为什么：约数 $a$ 与 $i/a$ 一一配对，配对把约数集合划分成若干个大小为 2 的组，唯一可能出现大小为 1 的组是 $a = i/a$ 的情形，此时 $i = a^2$。因此非完全平方数的约数个数必为偶数，完全平方数必为奇数。

把「统计 1..n 中的完全平方数」化为 $\lfloor \sqrt{n} \rfloor$。为什么：完全平方数与它的算术平方根一一对应，$a^2 \le n$ 等价于 $a \le \sqrt{n}$，而 $a$ 取正整数，个数就是 $\lfloor \sqrt{n} \rfloor$。

直接返回 (int) Math.sqrt(n)。为什么可以放心取整：Java 的 Math.sqrt 遵循 IEEE 754 正确舍入，对 int 范围内的 $n$（最大约 $2.1 \times 10^9$，远小于 $2^{53}$）结果误差不会跨越整数边界；$n = 0$ 时得 0，与「没有灯」一致，无需特判。

以 具体用例 n = 10 走一遍，先按定义手工模拟一遍确认结论。

逐轮反转 10 盏灯，从左到右依次是第 1 到第 10 盏，1 表示亮、0 表示灭，初始为 0000000000：
第 1 轮反转 1..10 的全部倍数即所有灯，得到 1111111111。
第 2 轮反转 2、4、6、8、10，得到 1010101010。
第 3 轮反转 3、6、9，得到 1000111000。
第 4 轮反转 4、8，得到 1001111100。
第 5 轮反转 5、10，得到 1001011101。
第 6 轮反转 6，得到 1001001101。
第 7 轮反转 7，得到 1001000101。
第 8 轮反转 8，得到 1001000001。
第 9 轮反转 9，得到 1001000011。
第 10 轮反转 10，得到 1001000010。
最终第 1、4、9 盏亮，其余全灭，共 3 盏。

再用结论核对：亮着的编号是 1、4、9，恰好是 $1^2, 2^2, 3^2$，全是完全平方数。逐个看约数个数：1 的约数只有 {1}，共 1 个（奇数，亮）；4 的约数是 {1,2,4}，配对时 1↔4 成对、2 与自身重合，共 3 个（奇数，亮）；6 的约数是 {1,2,3,6}，1↔6、2↔3 全部成对，共 4 个（偶数，灭）；10 的约数 {1,2,5,10} 同理是 4 个（偶数，灭）。
代入公式：$\lfloor \sqrt{10} \rfloor = \lfloor 3.162\ldots \rfloor = 3$，与手工模拟完全一致。

代码实现

class Solution {
    // 非完全平方数的因子成对出现，切换偶数次后会熄灭。
    public int bulbSwitch(int n) {
        return (int) Math.sqrt(n);
    }
}

func bulbSwitch(n int) int {
    // 非完全平方数的因子成对出现，切换偶数次后会熄灭。
    return int(math.Sqrt(float64(n)))
}

复杂度分析

时间复杂度：$O(1)$。凭什么：全部工作只有一次浮点开方，现代 CPU 上是单条 sqrtsd 指令，与 $n$ 的大小无关；模拟过程被数学推导完全消解，没有任何循环。

空间复杂度：$O(1)$。凭什么：只用到一个临时的浮点中间值，没有分配任何与 $n$ 相关的数组——这也正是本题必须走数学路线的原因，$n$ 达到十亿级时 $O(n)$ 的数组根本开不出来。

关键点总结

数据规模是解法的路标。当 $n$ 大到连 $O(n)$ 都跑不动时，几乎可以断定答案存在闭式，思考重心应该立刻从「怎么模拟得更快」切换到「最终状态由什么决定」。

先把耦合拆成独立子问题。本题的突破口是发现灯与灯之间毫无影响，于是 $n$ 盏灯的联合状态被拆成 $n$ 个互不相干的单灯判定，问题的维度瞬间塌缩。

「翻转偶数次等于没翻」是一类通用不变量。凡是状态只有两种、操作是反转的题目，都应该立刻去数「每个对象被操作的次数的奇偶性」，而不是追踪状态本身。

约数成对出现、只有完全平方数落单，是数论里最常被复用的一条小结论；它同时也是「枚举约数只需枚举到 $\sqrt{n}$」的理论依据。

闭式解要用小规模暴力交叉验证。写出 $\lfloor \sqrt{n} \rfloor$ 之后，花两分钟对 $n = 1 \dots 10$ 跑一遍暴力模拟比对，是把「猜的规律」变成「确认的结论」的最低成本手段。

面试视角：这题写代码只要 5 秒，面试官真正想听的是那条推导链。回答时务必按「反转次数 = 约数个数 → 约数配对 → 完全平方数落单 → 开方取整」四步讲清楚，并主动补一句「非完全平方数的约数为什么必然成偶数个」的配对论证。只报答案不给证明，通常会被追问到底。

易错点总结

错误写法：return (int) Math.sqrt(n) + 1（误以为要算上编号 0） → 用例 n = 3，正确答案是 1（只有第 1 盏亮），该写法返回 2。灯的编号从 1 开始，0 不是灯也不是正整数。

错误写法：老实开数组模拟 boolean[] bulbs = new boolean[n + 1] → 用例 n = 2000000000，直接抛 OutOfMemoryError；即便内存够，$O(n \log n)$ 次反转也会超时。

错误写法：return (int) Math.pow(n, 0.5) → 用例 n = 4，Math.pow 不保证正确舍入，某些平台可能返回 1.9999999999999998，取整后得 1，正确答案是 2。求平方根要用 Math.sqrt，它有 IEEE 754 正确舍入保证。

错误写法：Go 里写成 int(math.Sqrt(float64(n))) 之后又画蛇添足地做 if (res+1)*(res+1) <= n { res++ } 但漏了溢出保护 → 用例 n = 2147483647，res = 46340，(res+1)*(res+1) = 2147488281 在 32 位下溢出为负数，条件意外成立，答案错成 46341。

错误写法：把「亮」的判据写成「约数个数为偶数」 → 用例 n = 10，会把 2、3、5、6、7、8、10 都算成亮，返回 7，正确答案是 3。灯初始是灭的，必须被碰奇数次才亮。

错误写法：认为第 $i$ 盏灯只被第 $i$ 轮和第 1 轮碰过 → 用例 n = 6，第 6 盏灯实际被第 1、2、3、6 共四轮碰过；漏算中间轮次会得出「除 1 外全灭」的错误结论。

错误写法：n = 0 时额外写 if (n == 0) return 1 → 用例 n = 0 正确答案是 0（一盏灯都没有），多余的特判反而制造了错误；Math.sqrt(0) = 0.0，主逻辑本来就是对的。

错误写法：先用 long 循环 for (long a = 1; a * a <= n; a++) cnt++ 但把 a 声明成 int → 用例 n = 2147483647，a 增长到 46341 时 a * a 在 int 下溢出成负数，循环条件恒成立，直到 a 溢出才退出，结果完全错乱。这类枚举写法本身可行但必须用 long 做乘法。

相似题目

题目	难度	考察点
69. x 的平方根	简单	不借助库函数手写整数平方根，本题结论最终就落在这一步上
367. 有效的完全平方数	简单	判定单个数是否为完全平方数，考二分或牛顿迭代，而非约数个数的奇偶性
1492. n 的第 k 个因子	中等	直接枚举约数并按序取第 k 个，用的是「约数成对、只需枚举到 $\sqrt{n}$」
507. 完美数	简单	对约数求和而不是计数，成对枚举时要小心把 $\sqrt{n}$ 这一个重复约数只算一次
292. Nim 游戏	简单	同样是把博弈模拟压缩成一个模 4 的闭式判定，考的是找必败态而非数论
1006. 笨阶乘	中等	靠观察四项一组的周期规律给出常数级公式，属于同一类「先手算再归纳」的题
279. 完全平方数	中等	完全平方数在这里是背包的候选物品集合，重点是 DP 转移而不是计数结论
633. 平方数之和	中等	在平方数上跑双指针做存在性判定，考的是搜索区间的收缩而非闭式推导