题目

现有一个房间,墙上挂有 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);
}
};
05-11 20:13