Leetcode 672. 灯泡开关 Ⅱ

1.题目描述

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

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

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

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

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

输入：n = 1, presses = 1
输出：2
解释：状态可以是：

• 按压开关 1 ，[关]
• 按压开关 2 ，[开]

输入：n = 2, presses = 1
输出：3
解释：状态可以是：

• 按压开关 1 ，[关, 关]
• 按压开关 2 ，[开, 关]
• 按压开关 3 ，[关, 开]

输入：n = 3, presses = 1
输出：4
解释：状态可以是：

• 按压开关 1 ，[关, 关, 关]
• 按压开关 2 ，[关, 开, 关]
• 按压开关 3 ，[开, 关, 开]
• 按压开关 4 ，[关, 开, 开]

提示：

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

2.思路分析

根据题意，我们先找到每个开关影响的灯

如图所示，两个虚框的灯的状态完全一致，因此我们任意取一盏灯i，则i的状态和i + 6的状态完全一致，所以灯的状态的周期T = 6 。 因此我们只需要观察前六盏灯的状态。

设六盏灯的编号为6k+1、6k+2、6k+3、6k+4、6k+5、6k+6，则有:

• 6k+1会受到1、3、4开关的影响
• 6k+2会受到1、2开关的影响
• 6k+3会受到1、3开关的影响
• 6k+4会受到1、2、4开关的影响
• 6k+5会受到1、3开关的影响
• 6k+6会受到1、2开关的影响

由于 6k+2 和 6k+6 都受到 1、2 开关的影响，因此两盏灯的状态一致

由于6k+3 和 6k+5 都受到 1、3 开关的影响，因此两盏灯的状态一致

因此我们只需要观察前4盏灯的状态。

设按下4种开关的次数分别为a、b、c、d，由于偶数次按压相当于没按，所以有

• ① 6k+1的状态为(a + c + d) % 2 (开关:1、3、4)
• ② 6k+2的状态为(a + b) % 2 (开关:1、2)
• ③ 6k+3的状态为(a + c) % 2 (开关:1、3)
• ④ 6k+4的状态为(a + b + d) % 2 (开关:1、2、4)

由于①、③均受到开关1、3的影响, 所以①、③状态相同, 则d必为偶数; 若①③状态不同，则d必然为奇数。

由于②、④都受到1、2开关的影响，并且④和d有关系，所以若d为偶数，则②④状态相同；若d为奇数，则②④状态不同。

所以我们可以通过①②③的状态来确定④的状态, 因此我们只需要观察前3盏灯的状态

设前三盏灯开始的状态为111，我们最开始枚举状态，最多也就8种（每个灯只有亮和不亮）

• 按1次出现4种状态: 000, 101, 010, 011
• 按2次出现7中状态: 000, 101, 010, , 100, 001, 110, 111

以此类推，011可以由111获得，因此当presses >= 3时 可以获得8种

综上可得:

• 当n == 1时，开关1、3、4对其造成影响，也只有开和关两种状态
• 当n == 2时，按照推理111的状态推理11，按一次有3种状态，按2次及以上有4种状态。
• 当n == 3时，按一次有4种状态，按2次及以上有7种状态,3次及以上有8种状态。

3.代码实现

class Solution:
    def flipLights(self, n: int, presses: int) -> int:
        # 不按开关
        if presses == 0:
            return 1
        if n == 1:
            return 2
        elif n == 2:
            return 3 if presses == 1 else 4
        else:
            return 4 if presses == 1 else 7 if presses == 2 else 8
1
2
3
4
5
6
7
8
9
10
11

复杂度分析:

• 时间复杂度:$O(1)$。
• 空间复杂度:$O(1)$。

参考: https://leetcode.cn/problems/bulb-switcher-ii/solution/dengp-by-capital-worker-51rb/