0319. Bulb Switcher¶
题目信息¶
- 题号:
0319
- 难度:
Medium
- 主题:
灯泡切换、轮次规则、最终状态、计数
- 原题:
- 重点:
灯泡初始全部关闭、第 i 轮切换编号为 i 倍数的灯、返回最终亮灯数量
题目重述¶
有 n 盏编号为 1 到 n 的灯泡,初始全部关闭。依次执行 n 轮操作:第 i 轮切换所有编号能被 i 整除的灯泡;切换表示亮灯变暗、暗灯变亮。
完成全部轮次后,返回仍然亮着的灯泡数量。n 位于 [0, 10^9];当 n == 0 时没有灯泡和操作,结果为 0。题目只要求最终数量,不要求返回亮灯编号。
自建示例¶
多轮切换后的结果:
输入:n = 15
输出:3
解释:最终亮着的是编号 1、4、9 的灯泡,因此数量为 3。
没有灯泡:
输入:n = 0
输出:0
解释:不存在任何灯泡,最终亮灯数量自然为 0。
最终亮灯只取决于因数个数¶
编号为 x 的灯会在每一个能整除 x 的轮次被切换,因此它被切换的次数等于 x 的正因数个数。因数通常成对出现:d 与 x / d 配成一对;只有当 d * d == x 时,这一对的两个成员相同,完美平方会多出一个未配对的因数。
灯初始关闭,切换偶数次仍关闭,切换奇数次才点亮。所以最终点亮的灯恰好是 1 到 n 中的完美平方,答案就是不超过 n 的平方根。n == 0 时平方根也为零,直接覆盖空灯泡边界。
C++ 实现¶
class Solution {
public:
int bulbSwitch(int n) {
long long root = static_cast<long long>(
std::sqrt(static_cast<long double>(n)));
while ((root + 1) * (root + 1) <= n) ++root;
while (root * root > n) --root;
return static_cast<int>(root);
}
};
代码分析¶
算法不模拟轮次,也不逐灯统计因数,而是直接利用“只有平方数拥有奇数个因数”的结构。平方根初值来自浮点计算,两个校正循环消除边界附近的舍入风险;在题目范围内乘法不会溢出。时间复杂度为 O(1),额外空间为 O(1)。