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