题目
现有一个房间,墙上挂有 n 只已经打开的灯泡和 4 个按钮。在进行了 m 次未知操作后,你需要返回这 n 只灯泡可能有多少种不同的状态。
假设这 n 只灯泡被编号为 [1, 2, 3 ..., n],这 4 个按钮的功能如下:
将所有灯泡的状态反转(即开变为关,关变为开)
将编号为偶数的灯泡的状态反转
将编号为奇数的灯泡的状态反转
将编号为 3k+1 的灯泡的状态反转(k = 0, 1, 2, ...)
示例 1:
输入: n = 1, m = 1.
输出: 2
说明: 状态为: [开], [关]
示例 2:
输入: n = 2, m = 1.
输出: 3
说明: 状态为: [开, 关], [关, 开], [关, 关]
示例 3:
输入: n = 3, m = 1.
输出: 4
说明: 状态为: [关, 开, 关], [开, 关, 开], [关, 关, 关], [关, 开, 开].
注意: n 和 m 都属于 [0, 1000].
解法
这道题与灯泡开关1是有所区别的,灯泡开关1的题目类似数学问题,找到规律后可以很清晰的确定出最后剩余的一定是完全平方数。这道题找的规律略为复杂一些:
首先考虑周期性:假设灯足够多,如果只有按钮1,至多两种可能:全灭或者全亮;如果按钮2和按钮3考虑进来的话,最后灯的状态就是以2为周期的;如果把按钮4考虑进来的话最后灯的状态是以6为周期的,因为按钮4是(3*k+1)。
按钮的按的顺序可以交换不改变结果;同一个按钮状态跟按的奇偶次有关;按钮1、按钮2、按钮3其中两个是可以替代另一个的,也就是说按这三个中的任意两个等于按下另一个,四个按钮中有效的也就是三个,三个按钮各自按和不按两种情况,最多有8种状态。
当 m =3时,m = 4 时这8种状态都是可以实现的,m>=5的情况只要从m = 3 或者m = 4的情况对某个灯增加按偶数次即可得到。
用一个二进制的数来表示灯的状态,灯的状态以6位周期,所以只看6位。初始状态为000000,按一次按钮1变为111111;按一次按钮2变为010101;按一次按钮3变为101010;按一次按钮4变为100100。
m = 1时,按一次开关有四种可能111111、010101、101010、100100,如果n = 1,就看第一位,只有1和0两种可能。如果n = 2看前两位,11,01,10三种,如果n >=3 那么就有四种可能。
m = 2时,按两次开关有4^2=16种可能,但是不同的状态有7种:000000、001110、010101、011011、101010、110001、111111。如果n=1,看第一位,有0和1两种可能。如果n=2,看前两位,有00、01、10、11四种可能;如果n>=3,所有7种可能都互不相同。
m>=3时,总共有8种不同可能:000000、001110、010101、011011、100100、101010、110001、111111。如果n=1,可以只看第1位,有0和1两种可能;如果n=2,看前两位,有00、01、10、11四种可能;如果n>=3,所有8种可能都互不相同。
代码:
class Solution {
public:
int flipLights(int n, int m) {
if (m == 0) return 1;
if (n <= 0 || m < 0) return 0;
if (n == 1) return 2;
else if (n == 2) return (m == 1) ? 3 : 4;
else return (m == 1) ? 4 : ((m == 2) ? 7 : 8);
}
};