0319. Bulb Switcher

题目信息

题号:

0319

难度:

Medium

主题:

灯泡切换、轮次规则、最终状态、计数

原题:

LeetCode 0319

重点:

灯泡初始全部关闭、第 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)。