LeetCode每日一题——672. 灯泡开关 Ⅱ

LeetCode每日一题系列

题目：672. 灯泡开关 Ⅱ
难度：普通

---

---

题目

房间中有 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 ，执行完所有按压之后，返回 不同可能状态 的数量。

示例

示例 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 ，[关, 开, 开]

思路

代码较简单，并不用搜索所有的位置判断结果，这里有规律可寻。
4个按钮的作用效果，考虑到后边再多灯泡也是重复前边灯泡的情况，将4个按钮效果用最少灯泡来表示

• 1.将所有灯泡的状态反转（即开变为关，关变为开）：1个灯泡
• 2.将编号为偶数的灯泡的状态反转：2个灯泡
• 3.将编号为奇数的灯泡的状态反转：2个灯泡
• 4.将编号为 3k+1 的灯泡的状态反转（k = 0, 1, 2, …)：3个灯泡
• 因此可转化为：n = n < 3 ? n : 3;
• 一旦n >= 3,m >= 3,则可能情况就是3个灯泡的所有可能情况，每个灯泡2种情况，则总数是2^3=8种

剩余极端情况，枚举即可

• 若presses == 0，则答案为1

• 若n == 1，则答案为2 ** 1 = 2

• 若n == 2，若presses == 1则答案为三，否则答案为4

• 若n ==3，若pressses>2答案为8，等于2答案为7，等于1答案为4

题解

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 if presses == 1 else 4
        return 8 if presses > 2 else(4 if presses == 1 else 7)
1
2
3
4
5
6
7
8
9
10