---

0672. 灯泡开关 Ⅱ

• 标签：位运算、深度优先搜索、广度优先搜索、数学
• 难度：中等

题目链接

• 0672. 灯泡开关 Ⅱ - 力扣

题目大意

描述：

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

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

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

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

给定两个整数 $n$ 和 $presses$。

要求：

执行完所有按压之后，返回「不同可能状态」的数量。

说明：

• $1 \le n \le 10^{3}$。
• $0 \le presses \le 10^{3}$。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

思路 1：数学 + 枚举

思路 1：算法描述

这道题目要求在恰好按压开关 $presses$ 次后，返回不同可能状态的数量。

我们需要分析四个开关的作用：

• 开关 1：反转所有灯的状态。
• 开关 2：反转编号为偶数的灯的状态。
• 开关 3：反转编号为奇数的灯的状态。
• 开关 4：反转编号为 $3k + 1$ 的灯的状态（$k = 0, 1, 2, ...$）。

关键观察：

1. 按压同一个开关两次等于没有按压，所以每个开关最多只需要按压一次。
2. 按压开关的顺序不影响最终结果。
3. 对于前 $3$ 个灯，可以完全确定所有灯的状态（因为灯的状态是周期性的）。

我们可以枚举所有可能的开关组合（最多 $2^4 = 16$ 种），然后判断哪些组合是有效的（按压次数的奇偶性与 $presses$ 相同）。

具体步骤如下：

1. 如果 $presses = 0$，返回 $1$（所有灯都亮着）。
2. 枚举所有可能的开关组合（用二进制表示，$0$ 表示不按压，$1$ 表示按压）。
3. 对于每个组合，计算按压次数，判断是否与 $presses$ 的奇偶性相同，且按压次数不超过 $presses$。
4. 如果有效，计算前 $\min(n, 3)$ 个灯的状态，加入集合中。
5. 返回集合的大小。

思路 1：代码

class Solution:
    def flipLights(self, n: int, presses: int) -> int:
        if presses == 0:
            return 1
        
        # 只需要考虑前 3 个灯的状态
        n = min(n, 3)
        states = set()
        
        # 枚举所有可能的开关组合（4 个开关，2^4 = 16 种组合）
        for mask in range(16):
            # 计算按压次数
            press_count = bin(mask).count('1')
            
            # 判断按压次数是否有效
            if press_count % 2 != presses % 2 or press_count > presses:
                continue
            
            # 计算前 n 个灯的状态
            lights = [1] * n  # 初始状态：所有灯都亮着
            
            # 开关 1：反转所有灯
            if mask & 1:
                for i in range(n):
                    lights[i] ^= 1
            
            # 开关 2：反转编号为偶数的灯（索引为 1, 3, 5, ...）
            if mask & 2:
                for i in range(1, n, 2):
                    lights[i] ^= 1
            
            # 开关 3：反转编号为奇数的灯（索引为 0, 2, 4, ...）
            if mask & 4:
                for i in range(0, n, 2):
                    lights[i] ^= 1
            
            # 开关 4：反转编号为 3k + 1 的灯（索引为 0, 3, 6, ...）
            if mask & 8:
                for i in range(0, n, 3):
                    lights[i] ^= 1
            
            # 将状态加入集合
            states.add(tuple(lights))
        
        return len(states)

思路 1：复杂度分析

• 时间复杂度：$O(1)$。枚举的组合数是常数（$16$ 种），每种组合的计算时间也是常数。
• 空间复杂度：$O(1)$。集合中最多存储常数个状态。