LeetCode 题解工作台
灯泡开关 Ⅱ
房间中有 n 只已经打开的灯泡，编号从 1 到 n 。墙上挂着 4 个开关 。 这 4 个开关各自都具有不同的功能，其中： 开关 1 ： 反转当前所有灯的状态（即开变为关，关变为开） 开关 2 ： 反转编号为偶数的灯的状态（即 0, 2, 4, ... ） 开关 3 ： 反转编号为奇数的灯的状态（即…
4
题型
4
代码语言
3
相关题
当前训练重点
中等 · 数学·位运算
答案摘要
观察灯泡开关随按钮操作的变化规律，我们可以发现，位置 与 的灯泡，开关状态始终保持一致，因此，我们只需要考虑最多前 个灯泡的开关状态。 另外，对于每个按钮，若操作偶数次，相当于没执行操作；若操作奇数次，相当于操作了 次。同时，不同按钮操作的先后顺序，也不影响结果。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·位运算 题型思路
题目描述
房间中有 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 <= 10000 <= presses <= 1000
解题思路
方法一：位运算
观察灯泡开关随按钮操作的变化规律，我们可以发现，位置 与 的灯泡，开关状态始终保持一致，因此，我们只需要考虑最多前 个灯泡的开关状态。
另外，对于每个按钮，若操作偶数次，相当于没执行操作；若操作奇数次，相当于操作了 次。同时，不同按钮操作的先后顺序，也不影响结果。
题目有 个按钮，每个按钮有“操作偶数次”和“操作奇数次”两种状态，因此总共有 种按钮状态。
二进制枚举按钮的状态 mask，若当前状态满足题目 presses 的限制，我们可以通过位运算，模拟操作对应按钮，最终得到灯泡的状态 ，去重后的 的数量就是答案。
时空复杂度均为常数级别。
class Solution:
def flipLights(self, n: int, presses: int) -> int:
ops = (0b111111, 0b010101, 0b101010, 0b100100)
n = min(n, 6)
vis = set()
for mask in range(1 << 4):
cnt = mask.bit_count()
if cnt <= presses and cnt % 2 == presses % 2:
t = 0
for i, op in enumerate(ops):
if (mask >> i) & 1:
t ^= op
t &= (1 << 6) - 1
t >>= 6 - n
vis.add(t)
return len(vis)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(1) because the maximum number of unique configurations is constant, bounded by 8 for n>=3. Space complexity is O(1) as only a fixed number of configurations are stored and manipulated. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Expect candidates to identify bit patterns representing bulb toggles.
- question_mark
Check if the solution avoids brute-force simulation for large n.
- question_mark
Probe understanding of how repeated presses affect unique states and symmetry.
常见陷阱
外企场景- error
Ignoring symmetry when n > 3, overcounting states.
- error
Not considering that extra presses beyond 3 do not create new configurations.
- error
Attempting full 2^n simulation instead of using bit masks and math analysis.
进阶变体
外企场景- arrow_right_alt
Vary number of bulbs or buttons to test combinatorial reasoning.
- arrow_right_alt
Ask for maximum distinct states achievable with limited presses.
- arrow_right_alt
Change toggle rules to multiples other than 2 or 3 to examine pattern generalization.