leetcode [672] 灯泡开关 Ⅱ

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

现有一个房间，墙上挂有 n 只已经打开的灯泡和 4 个按钮。在进行了 m 次未知操作后，你需要返回这 n 只灯泡可能有多少种不同的状态。

假设这 n 只灯泡被编号为 [1, 2, 3 …, n]，这 4 个按钮的功能如下：

• 将所有灯泡的状态反转（即开变为关，关变为开）
• 将编号为偶数的灯泡的状态反转
• 将编号为奇数的灯泡的状态反转
• 将编号为 3k+1 的灯泡的状态反转（k = 0, 1, 2, …)

示例 1:

输入: n = 1, m = 1.
输出: 2
说明: 状态为: [开], [关]

示例 2:

输入: n = 2, m = 1.
输出: 3
说明: 状态为: [开, 关], [关, 开], [关, 关]

示例 3:

输入: n = 3, m = 1.
输出: 4
说明: 状态为: [关, 开, 关], [开, 关, 开], [关, 关, 关], [关, 开, 开].

来自题解:

因为前 6 个灯唯一地决定了其余的灯。这是因为修改第 x 灯光的每个操作都会修改 第 (x+6)灯光，因此 xxx 灯光始终等于 (x+6)灯光。 实际上，前 3 个灯唯一地确定了序列的其余部分，如下表所示，用于执行操作 a, b, c, d:

Light 1 = 1 + a + c + d
Light 2 = 1 + a + b
Light 3 = 1 + a + c
Light 4 = 1 + a + b + d
Light 5 = 1 + a + c
Light 6 = 1 + a + b

*上述理由表明，在不损失一般性的情况下，取 n=min(n,3)n = min(n, 3)n=min(n,3) 是合理的。

• 让我们用 (a,b,c)来表示灯的状态。与值为 (1,1,1),(0,1,0),(1,0,1),(1,0,0) xor.
• 当 m=0 时，所有灯都亮起，只有一个状态 (1,1,1)。在这种情况下，答案总是 1。
• 当 m=1 时，我们可以得到状态 (0,0,0), (1,0,1), (0,1,0), (0,1,1)。在这种情况下，对于 n=1,2,3 的答案是 2,3,4。
• 当 m=2 时，我们可以检查是否可以获得 7 个状态：除(0,1,1)之外的所有状态。在这种情况下，n=1,2,3 的答案是 2,4,7。
• 当 m=3 时，我们可以得到所有 8 个状态。在这种情况下，n=1,2,3 的答案是 2,4,8

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