Leetcode【319、672】

问题描述：【Math】319. Bulb Switcher

解题思路：

灯泡开关。初始时有 n 个灯泡关闭，第 i 轮，每 i 个灯泡切换一次开关。找出 n 轮后有多少个亮着的灯泡。

刚开始写了个暴力版 O(n^2)，但是超时了，代码如下：

class Solution:
    def bulbSwitch(self, n: int) -> int:
        bulbs = [0] * n
        i = 1
        while i <= n:  # 第i轮
            for j in range(i-1, n, i):   # 每i个灯泡切换一次开关
                bulbs[j] = 1 - bulbs[j]
            i += 1
        return sum(bulbs)

但是，很明显这道题是有规律可循的。可以发现，对于编号为 x 的灯，它切换的次数就是 x 的因数的个数。比如编号为 8 的灯，会在 1、2、4、8 时被切换。如果切换次数（因子个数）为偶数，最后肯定是关；如果切换次数（因子个数）为奇数，最后肯定是开。因此这道题转化为求解因子个数为奇数的灯有几个。

如果我们从 1 一个个去求到 N，计算每个数的因子个数，那样时间复杂度也近似于 O(n^2)，所以也不对。注意到：除了完全平方数外，其他所有数的因子都是偶数个（包括质数）。而完全平方数的因子个数为奇数个（比如 36 的因子为 1、2、3、6、12、18、36，总共 7 个），因此我们只需要统计 n 以下的完全平方数个数即可。时间复杂度为 O(1)。

Python3 实现：

class Solution:
    def bulbSwitch(self, n: int) -> int:
        return int(n ** 0.5)  # 计算n以下的完全平方数有多少个

问题描述：【Math】672. Bulb Switcher II

解题思路：

灯泡开关 2 。有 n 只已经打开的灯泡和 4 个按钮，每个按钮有不同的切换灯泡的功能。在进行 m 次未知操作后，返回这 n 只灯泡可能有多少种不同的状态。

• 考虑 n = 3 的情况：m = 1 时，有 4 个状态；m = 2 时，有 7 个状态；m >= 3 时，有 8 个状态；
• 考虑 n = 4 的情况：m = 1 时，有 4 个状态；m = 2 时，有 7 个状态；m >= 3 时，有 8 个状态；

因此，我们猜想，对于 n >= 3，会不会都是上面这样的答案？答案是 YES。虽然感觉是找规律，但是我也不会证明。

而对于 n = 1 和 n = 2 的情况，我们单独考虑即可。

鉴于这道题被踩的那么惨，实际上也没有做的必要了，参考代码如下。

Python3 实现：

class Solution:
    def flipLights(self, n: int, m: int) -> int:
        if m == 0: return 1
        if n == 1: return 2
        if n == 2 and m == 1: return 3
        if n == 2 and m > 1: return 4
        if m == 1: return 4
        if m == 2: return 7
        if m > 2: return 8