力扣 319. 灯泡开关

题目说明

初始时有 n 个灯泡处于关闭状态。第一轮，你将会打开所有灯泡。接下来的第二轮，你将会每两个灯泡关闭一个。

第三轮，你每三个灯泡就切换一个灯泡的开关（即，打开变关闭，关闭变打开）。第 i 轮，你每 i 个灯泡就切换一个灯泡的开关。直到第 n 轮，你只需要切换最后一个灯泡的开关。

找出并返回 n 轮后有多少个亮着的灯泡。

提示：

  • 0 <= n <= 10^9

示例

示例 1:

img

1
2
3
4
5
6
7
8
9
输入：n = 3
输出：1 
解释：
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭]. 

你应该返回 1，因为只有一个灯泡还亮着。

示例 2:

1
2
输入：n = 0
输出：0

示例 3:

1
2
输入：n = 1
输出：1

笔者理解

此题是一道脑筋急转弯算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题明白原理后就豁然开朗了，我们可以看到题目n的范围是9次幂级的，所以平常的解决办法通常是不行的，我们可以仔细阅读题目再写几组数字，仔细想一下规律，让我们来看看具体如何实现的吧。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    /**
     * 数学
     */
    public int bulbSwitch(int n) {
        /** 
         * 第i个灯泡的反转次数等于它所有因子（包括1和i）的个数，
         * 一开始所有的灯泡都是灭的，只有当他反转奇数次才会变成亮，
         * 所以只有因子总个数为奇数的序号的灯泡才会亮，而且只有平方数的因子数为奇数
         * （比如6=1*6,2*3，它们的因子总是成对出现的，而4=1*4,2*2，平方数的平方根因子会出现1次），
         * 所以最终答案等于n以内（包括n和1）的平方数总数量，所以只需要计算sqrt(n)即可
         */
        return (int) Math.sqrt(n);
    }
}

时间和空间效率还行，可见此解法还比较适合此题。

image-20211115101227712

总结

本题是今天的一题，难度是为中等，感兴趣的朋友都可以去尝试一下，此题还有其他更多的解法，朋友们可以自己逐一尝试。