题目描述
现有一个房间,墙上挂有 只已经打开的灯泡和 个按钮。在进行了 次未知操作后,你需要返回这 只灯泡可能有多少种不同的状态。
假设这 只灯泡被编号为 ,这 个按钮的功能如下:
- 将所有灯泡的状态反转(即开变为关,关变为开)
- 将编号为偶数的灯泡的状态反转
- 将编号为奇数的灯泡的状态反转
- 将编号为 的灯泡的状态反转()
示例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)