微软和谷歌的几个大佬组织了一个面试刷题群，可以加管理员VX：sxxzs3998（备注CSDN），进群参与讨论和直播
1 .问题是有现有的房间，墙上挂着n个已经打开的灯泡和按钮。 在进行了m次未知操作后，需要返回到这n个灯泡可能有多少不同的状态。 假设这n个灯泡被编号为[ 1，2，3…，n]。 这四个按钮的功能如下：
反转所有灯泡的状态(即，从开到关、从关到开)；反转偶数灯泡的状态；反转奇数灯泡的状态) k=0、1、2、…)示例1:输入： n=1， m=1.输出：说明：状态为： [关闭]示例2:输入： n=2，m=1.输出： 3说明：状态为： [打开，关闭]，[关闭，打开]，[关闭，关闭] m=1.输出33604 [开、关、开]、[关、关、关]、[关、开、开]. 2 .分析2.1认知下图分析了6个灯泡的全部情况：
从图中可以看出，灯泡数量多于6个时，是前6个灯泡反复循环的情况。 如下开始理论分析。
2.2问题的解答探索空间非常大(2N2 ^ n2n个灯的状态，4 M4 ^ m4m个操作顺序)，所以试着减少它。
前六盏灯决定了唯一剩下的灯。 这是因为对于修改第xx个灯光的每个操作，都会修改第(x 6) ) x^6)个灯光。
首先简化m
a操作后继续b操作和b操作后继续a操作相同，所以可以假设按顺序进行所有操作。
最后，连续执行两次相同的操作就等于什么都不做。 所以，每次操作只需考虑0次还是1次。
其次，简化n
有以下四个操作，分别为a、b、c、d a。 反转所有灯泡的状态。 也就是说，从开变为关，从关变为开。 b .反转第偶数个灯泡的状态。 c .反转第奇数个灯泡的状态。 反转第3k^1个灯泡的状态。 (k=0、1、2、…)。
假设已经执行了a、b、c、d a、b、c、d a、b、c、d四个操作。 A， B， C， d！ A， B， C， d！ A， B， C， d没有执行四项操作。 其中，前六盏灯唯一确定了其馀的灯，因此将其简化为6。
假设为n 6，则可以看到所有灯泡都已在早期打开，并且所有状态都有灯泡()这一部分也可以解释为什么前六盏灯决定剩下的灯() ) )。
light1=true ^ a ^ c ^ d light2=true ^ a ^ blight3=true ^ a ^ clight4=true ^ a ^ b ^ d light5=true ^ a ^ clight6=true
^ dLight 8 = true ^ a ^ bLight 9 = true ^ a ^ cLight 10 = true ^ a ^ b ^ d可以发现，第 i i i个灯泡的状态 = 第 i i % 6 i 个灯泡的状态。简单看四个操作的最小公约数也可以求得循环，此时可以求前6个灯泡的所有状态即可。
然后再简化到3
假设 n>3 进一步思考可以发现，决定所有灯泡的操作为abcd，如果前三个灯泡的状态确定了，就可以得到个四元一次方程，就可以确定abcd的操作是否执行，即前三个灯泡的状态可以决定后续所有灯泡的状态。证明如下：
Light 1 = 1 ^ a ^ c ^ dLight 2 = 1 ^ a ^ bLight 3 = 1 ^ a ^ cLight 4 = 1 ^ a ^ b ^ dLight 5 = 1 ^ a ^ cLight 6 = 1 ^ a ^ b上述理由表明，在不损失一般性的情况下，取 n = m i n ( n , 3 ) n = min(n, 3) n=min(n,3) 是合理的。
前三个灯泡的状态共有8种，即后续灯泡的状态都由8种决定，所有灯泡的状态也最多只有8种。
让我们用 (a,b,c) 来表示灯的状态。与值为 (1, 1, 1), (0, 1, 0), (1, 0, 1), (1, 0, 0) xor。
当 m=0 时，所有灯都亮起，只有一个状态 (1, 1, 1)。在这种情况下，答案总是 1。当 m=1 时，我们可以得到状态 (0, 0, 0), (1, 0, 1), (0, 1, 0), (0, 1, 1)。在这种情况下，对于 n = 1, 2, 3 的答案是 2, 3, 4。当 m=2 时，我们可以检查是否可以获得 7 个状态：除(0, 1, 1)之外的所有状态。在这种情况下，n = 1, 2, 3 的答案是 2, 4, 7。当 m=3时，我们可以得到所有 8 个状态。在这种情况下，n = 1, 2, 3 的答案是 2, 4, 8。于是，代码就变得很好写了：
class Solution {public: int flipLights(int n, int m) { n = min(n, 3); if (m == 0) return 1; if (m == 1) return n == 1 ? 2 : n == 2 ? 3 : 4; if (m == 2) return n == 1 ? 2 : n == 2 ? 4 : 7; return n == 1 ? 2 : n == 2 ? 4 : 8; }};微软和谷歌的几个大佬组织了一个面试刷题群，可以加管理员VX：sxxzs3998（备注CSDN），进群参与讨论和直播