0%

leetCode-319:Bulb Switcher

发表于 2021-11-19 分类于 leetCode

问题描述

假设有 n 个灯泡，编号从 1 到 n，初始状态是关的，现在执行以下动作：第一次，全部打开，第二次把能被 2 整除的灯泡改变下状态（从开变成关，从关变成开），第三次把能被 3 整除的灯泡改变下状态（从开变成关，从关变成开），第 i 此把能被 i 整除的灯泡改变下状态（从开变成关，从关变成开），以此类推，直到第 n 次结束。要求统计最后灯泡亮着的数量。题目链接：**点我**

样例输入输出

输入：3

输出：1

解释：初始状态灯泡状态为：关、关、关

第一次遍历后灯泡状态为：开、开、开

第二次遍历后灯泡状态为：开、关、开

第三次遍历后灯泡状态为：开、关、关

最后灯泡开着的数量为 1

输入：1

输出：1

问题解法

首先，分析每个灯泡，在第一轮过后，灯泡都是亮着的，此后的每一轮，如果灯泡编号能被 i 整除，则会改变状态，如果 i 不是灯泡编号的平方根，那么在 [1, 灯泡编号] 这个区间内肯定存在另一个数 k 使得 i * k = 灯泡变化，也就是说灯泡的状态会在第 i 次遍历时改变状态，但是在第 k 次遍历时又把状态还原回去。所以，要想灯泡亮着，灯泡的编号必须是一个完全平方数（否则，合数个数是偶数，负负得正，相当于没变）。此题也就转换为求 [1, n] 范围内完全平方数的个数，更进一步，也就是求 n 的平方根向下取整的值。代码如下：

class Solution
{
    public int bulbSwitch(int n)
    {
        return (int) Math.sqrt(n);
    }
}

参考资料