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)``。