LeetCode-672. 灯泡开关 Ⅱ【穷举，位运算】

题目描述：

房间中有 n 只已经打开的灯泡，编号从 1 到 n 。墙上挂着 4 个开关 。

这 4 个开关各自都具有不同的功能，其中：

开关 1 ：反转当前所有灯的状态（即开变为关，关变为开）
开关 2 ：反转编号为偶数的灯的状态（即 2, 4, …）
开关 3 ：反转编号为奇数的灯的状态（即 1, 3, …）
开关 4 ：反转编号为 j = 3k + 1 的灯的状态，其中 k = 0, 1, 2, …（即 1, 4, 7, 10, …）
你必须 恰好 按压开关 presses 次。每次按压，你都需要从 4 个开关中选出一个来执行按压操作。

给你两个整数 n 和 presses ，执行完所有按压之后，返回 不同可能状态 的数量。

示例 1：

输入：n = 1, presses = 1
输出：2
解释：状态可以是：

• 按压开关 1 ，[关]
• 按压开关 2 ，[开]

示例 2：

输入：n = 2, presses = 1
输出：3
解释：状态可以是：

• 按压开关 1 ，[关, 关]
• 按压开关 2 ，[开, 关]
• 按压开关 3 ，[关, 开]

示例 3：

输入：n = 3, presses = 1
输出：4
解释：状态可以是：

• 按压开关 1 ，[关, 关, 关]
• 按压开关 2 ，[关, 开, 关]
• 按压开关 3 ，[开, 关, 开]
• 按压开关 4 ，[关, 开, 开]

提示：

1 <= n <= 1000
0 <= presses <= 1000

解题思路一：直接列出所有可能的情况，因为开关自身按偶数次是等于没有效果的。然后一个开关的效果也可以由另外几个开关来实现。例如：执行a的效果 == 执行b的效果 + 执行c的效果。

class Solution {
public:
    int flipLights(int n, int m) {
        if(n ==0 || m == 0){
            return 1;
        }
        if(n == 1){
            return 2;
        }
        else if(n == 2 && m == 1){
            return 3;
        }
        else if((n == 2 && m >= 2) || m == 1){
            // n < 3的情况已被前面的if排除
            // 因此当n>=3时，只需判断m==1即可
            return 4;
        }
        else if(n >= 3 && m == 2){
            return 7;
        }
        else {
            return 8;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

解题思路二：位运算和考虑四个灯泡。

class Solution {
public:
    int flipLights(int n, int presses) {
        unordered_set<int> seen;
        for (int i = 0; i < 1 << 4; i++) {
            vector<int> pressArr(4);
            for (int j = 0; j < 4; j++) {
                pressArr[j] = (i >> j) & 1;
            }
            int sum = accumulate(pressArr.begin(), pressArr.end(), 0);
            if (sum % 2 == presses % 2 && sum <= presses) {
                int status = pressArr[0] ^ pressArr[1] ^ pressArr[3];
                if (n >= 2) {
                    status |= (pressArr[0] ^ pressArr[1]) << 1;
                }
                if (n >= 3) {
                    status |= (pressArr[0] ^ pressArr[2]) << 2;
                }
                if (n >= 4) {
                    status |= (pressArr[0] ^ pressArr[1] ^ pressArr[3]) << 3;
                }
                seen.emplace(status);
            }
        }
        return seen.size();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

时间复杂度：O(1)。
空间复杂度：O(1)。

解题思路三：暂无

1