0672：灯泡开关 Ⅱ（★）

力扣第 672 题

题目

房间中有 n 只已经打开的灯泡，编号从 1 到 n 。墙上挂着 4 个开关 。

这 4 个开关各自都具有不同的功能，其中：

• 开关 1 ：反转当前所有灯的状态（即开变为关，关变为开）
• 开关 2 ：反转编号为偶数的灯的状态（即 0, 2, 4, ...）
• 开关 3 ：反转编号为奇数的灯的状态（即 1, 3, ...）
• 开关 4 ：反转编号为 j = 3k + 1 的灯的状态，其中 k = 0, 1, 2, ...（即 1, 4, 7, 10, ...）

你必须 恰好 按压开关 presses 次。每次按压，你都需要从 4 个开关中选出一个来执行按压操作。

给你两个整数 n 和 presses ，执行完所有按压之后，返回 不同可能状态 的数量。

示例 1：

输入：n = 1, presses = 1
输出：2
解释：状态可以是：
- 按压开关 1 ，[关]
- 按压开关 2 ，[开]

示例 2：

输入：n = 2, presses = 1
输出：3
解释：状态可以是：
- 按压开关 1 ，[关, 关]
- 按压开关 2 ，[开, 关]
- 按压开关 3 ，[关, 开]

示例 3：

输入：n = 3, presses = 1
输出：4
解释：状态可以是：
- 按压开关 1 ，[关, 关, 关]
- 按压开关 2 ，[关, 开, 关]
- 按压开关 3 ，[开, 关, 开]
- 按压开关 4 ，[关, 开, 开]

提示：

• 1 <= n <= 1000
• 0 <= presses <= 1000

相似问题：

• 0319：灯泡开关
• 1375：二进制字符串前缀一致的次数（1438 分）

分析

• 令 0/1 分别代表灯泡打开/关闭状态，并假设 4 个开关的状态分别是 a/b/c/d
• 可以得到每个灯泡的状态：
  • a^c^d, a^b, a^c, a^b^d, a^c, a^b, a^c^d, ….
  • 以 6 个为一组循环
  • 注意到灯泡4的状态 a^b^d = (a^c^d)^(a^b)^(a^c)，所以前三个灯泡的状态决定了所有灯泡的状态
• 再考察下哪些灯泡的状态能达到
  • 若刚好开关一次，前三个灯泡的状态可以为 111、101、010、100
  • 若刚好开关两次，前三个灯泡的状态可以为 000、101、010、011、111、001、110，只有 100 无法得到
  • 若刚好开关三次，可以基于开关两次的所有状态，按压开关1，得到除 011 的所有状态，而 011 可以通过按压开关 2/3/4 得到，所以能得到所有状态
  • 若刚好开关三次以上，可以基于开关三次的所有状态，一直按压开关1，得到所有状态
• 再特判下 n<3 的情况即可

解答

1
2
3
4
5
6
7
8
9

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

0 ms