灯泡开关 Ⅱ

难度: Medium

房间中有 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

Submission

运行时间: 20 ms

内存: 16.1 MB

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

Explain

这个题解的思路是分情况讨论。通过观察可以发现，当灯泡个数 n 大于等于 3 时，无论怎么按压开关，最多只能得到 8 种不同的状态。所以题解直接根据 n 和 presses 的不同取值，返回对应的结果。具体来说： 1. 当 presses 为 0 时，无论 n 为多少，都只有 1 种状态，即全亮。 2. 当 n 为 1 时，只有 2 种状态：全亮或全暗。 3. 当 n 为 2 时，如果只按一次开关，有 3 种状态；按多次的话，就有 4 种状态。 4. 当 n 大于等于 3 时，如果只按一次开关，有 4 种状态；按两次有 7 种状态；按更多次就有 8 种状态。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def flipLights(self, n: int, presses: int) -> int:
        if presses == 0:
            # 不按开关，只有 1 种状态
            return 1
        if n == 1:
            # 只有 1 盏灯，有 2 种状态
            return 2
        elif n == 2:
            # 有 2 盏灯
            return 3 if presses == 1 else 4
        else:
            # 有 3 盏或更多灯 
            return 4 if presses == 1 else 7 if presses == 2 else 8

Explore

当n大于等于3时，可以通过四种不同的开关操作来影响灯泡的状态：(1) 打开所有灯泡，(2) 打开奇数位的灯泡，(3) 打开偶数位的灯泡，(4) 打开3k+1位置的灯泡。由于每种操作都可能独立执行，也可以与其他操作组合执行，这些操作可以产生多种不同的灯泡状态。然而，当操作数量和灯泡数量增加时，特定的操作组合的效果可能会相互抵消或重复，因此最终可能的不同状态数是有限的。当我们仔细分析可能的操作组合时，可以找到最多8种不同的结果，这是因为操作之间的交互和特定位置的影响限制了可能的状态变化。

当有两盏灯且按压次数大于1时，我们可以通过不同的按压组合达到四种状态：(1) 两盏灯都亮，(2) 两盏灯都灭，(3) 第一盏灯亮、第二盏灯灭，(4) 第一盏灯灭、第二盏灯亮。这些状态可以通过以下方式实现：不按任何开关得到全亮；按下所有灯泡的开关得到全灭；只按第一次或第三次开关得到一个灯亮一个灯灭的两种情况。如果按压次数超过两次，由于操作的可逆性，这些状态会开始重复，因此总状态数不会增加。

当presses为0时，意味着没有任何开关被按压，因此所有灯泡都将保持其初始状态。在该题目中，默认的初始状态是所有灯泡都亮起。因此，不论灯泡数量n为多少，如果没有开关操作，最终的灯泡状态只能是全亮，即只有一种状态。

在题解的分析中，考虑到开关的操作是可以逆转的，并且执行相同的操作顺序最终会导致相同的状态，因此操作的顺序并不影响最终的灯泡状态。例如，无论是先按奇数位灯泡的开关再按偶数位的开关，还是先按偶数位再按奇数位，结果都是相同的。因此，计算不同状态的数量时，只需要考虑不同操作的组合，而不是具体的操作顺序。