【每日算法Day 61】LeetCode 672. 灯泡开关 Ⅱ
题目描述
现有一个房间，墙上挂有 只已经打开的灯泡和
个按钮。在进行了
次未知操作后，你需要返回这
只灯泡可能有多少种不同的状态。
假设这 只灯泡被编号为
，这
个按钮的功能如下：
- 将所有灯泡的状态反转（即开变为关，关变为开）
- 将编号为偶数的灯泡的状态反转
- 将编号为奇数的灯泡的状态反转
- 将编号为
的灯泡的状态反转（
)
示例1
输入：
n = 1, m = 1.
输出：
2
解释：
状态为: [开], [关]
示例2
输入：
n = 2, m = 1.
输出：
3
解释：
状态为: [开, 关], [关, 开], [关, 关]
示例3
输入：
n = 3, m = 1.
输出：
4
解释：
状态为: [关, 开, 关], [开, 关, 开], [关, 关, 关], [关, 开, 开].
提示
和
都属于
.
题解
首先我们要知道，一个操作做两次就等于没做，所以一个操作只有没做和做了两种状态，也就是说有效操作数量最多 次：
。
然后我们观察每一个操作对灯状态（初始都开着，状态都为 ）的影响：
- 操作
每
异或）。
- 操作
每
异或）。
- 操作
每
异或）。
- 操作
每
异或）。
综上，我们只需要取周期的最小公倍数 就行了。也就是只需要看前
盏灯的最终状态，就能唯一确定后面所有灯的最终状态。
形式化表示，用 表示第
个操作是否用过。那么对于第
盏灯来说，它的最终状态可以表示为：
由此可以推出： ，也就是灯的最终状态以
为周期。
到此其实可以直接暴力枚举 的所有状态了，但是还是有优化空间的。
如果我们列出前 盏灯的状态：
我们可以看出，如果前 盏灯状态确定了，可以唯一确定出后
盏灯状态。因此，我们只需要计算前
盏灯有多少种状态就行了。
最终经过枚举计算（）：
- 如果
，那么就只有
- 否则如果
，那么有
- 否则如果
，若
，就有
，就有
- 否则如果
，若
，就有
种状态；若
，就有
种状态。
如果你实在不想手动计算，那你可以枚举所有的 种操作状态，然后保存前三盏灯的状态到一个集合中，最终输出集合大小就行了。
代码
c++
class Solution {
public:
int flipLights(int n, int m) {
if (m == 0) return 1;
if (n == 1) return 2;
m = min(m, 3);
if (n == 2) return vector<int>{3, 4, 4}[m-1];
return vector<int>{4, 7, 8}[m-1];
}
};
python
class Solution:
def flipLights(self, n: int, m: int) -> int:
if m == 0: return 1
if n == 1: return 2
m = min(m, 3)
if n == 2: return [3, 4, 4][m-1]
return [4, 7, 8][m-1]
python（枚举）
class Solution:
def flipLights(self, n, m):
seen = set()
for cand in itertools.product((0, 1), repeat = 4):
if sum(cand) % 2 == m % 2 and sum(cand) <= m:
A = []
for i in range(min(n, 3)):
light = 1
light ^= cand[0]
light ^= cand[1] and i % 2
light ^= cand[2] and i % 2 == 0
light ^= cand[3] and i % 3 == 0
A.append(light)
seen.add(tuple(A))
return len(seen)
算法码上来 文章被收录于专栏
公众号「算法码上来」。godweiyang带你学习算法，不管是编程算法，还是深度学习、自然语言处理算法都一网打尽，更有各种计算机新鲜知识和你分享。别急，算法码上来。
投递美团等公司10个岗位 >
