672. Bulb Switcher II

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

There is a room with n bulbs labeled from 1 to n that all are turned on initially, and four buttons on the wall. Each of the four buttons has a different functionality where:

• Button 1: Flips the status of all the bulbs.
• Button 2: Flips the status of all the bulbs with even labels (i.e., 2, 4, …).
• Button 3: Flips the status of all the bulbs with odd labels (i.e., 1, 3, …).
• Button 4: Flips the status of all the bulbs with a label j = 3k + 1 where k = 0, 1, 2, … (i.e., 1, 4, 7, 10, …).

You must make exactly presses button presses in total. For each press, you may pick any of the four buttons to press.

Given the two integers n and presses, return the number of different possible statuses after performing all presses button presses.

Example 1:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

Example 2:

Input: n = 2, presses = 1
Output: 3
Explanation: Status can be:
- [off, off] by pressing button 1
- [on, off] by pressing button 2
- [off, on] by pressing button 3

Example 3:

Input: n = 3, presses = 1
Output: 4
Explanation: Status can be:
- [off, off, off] by pressing button 1
- [off, on, off] by pressing button 2
- [on, off, on] by pressing button 3
- [off, on, on] by pressing button 4

Constraints:

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

Code

• b1 + b2 = b3
• b1 + b3 = b2
• b2 + b3 = b1

所以最多有 8 种情况

1. 抵消 (b1 + b1) -> 全亮
2. b1
3. b2
4. b3
5. b4
6. b1 + b4
7. b2 + b4
8. b3 + b4

只有以下情况:

• 当 n = 0 或 presses = 0 时, 有 1 种情况, 返回 1
• 当 n = 1 时, 有 2 种情况, 0 和 1, 返回 2
• 当 n = 2 时, 看 presses 的次数, 如果
  • presses = 1, 那么有三种状态 00,01,10
  • presses > 1, 那么有四种状态 00,01,10,11
• 当 n > 2 时
  • 当 presses = 1 时, 有四种状态: 000,010,101,011
  • 当 presses = 2 时, 有七种状态: 111,101,010,100,000,001,110
  • 当 presses > 2 时, 有八种状态:
    • 111 - 抵消, 例如 b2 + b3 + b1
    • 000 - b1
    • 101 - b2
    • 010 - b3
    • 011 - b4
    • 100 - b1 + b4
    • 001 - b2 + b4
    • 110 - b3 + b4

class Solution {
    public int flipLights(int n, int presses) {
        if (n == 0 || presses == 0) return 1;
        if (n == 1) return 2;
        if (n == 2) return presses == 1 ? 3 : 4;
        if (presses == 1) return 4;
        return presses == 2 ? 7 : 8;
    }
}

class Solution {
    public int flipLights(int n, int presses) {
        if (n == 0 || presses == 0) return 1;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer((1 << n) - 1);

        for (int i = 0; i < presses; i++) {
            int size = queue.size();
            Set<Integer> visited = new HashSet<>();

            for (int k = 0; k < size; k++) {
                int curr = queue.poll();
                int[] flips = new int[] {
                    btn1(curr, n),
                    btn2(curr, n),
                    btn3(curr, n),
                    btn4(curr, n),
                };

                for (int flip: flips) {
                    if (visited.add(flip)) {
                        queue.offer(flip);
                    }
                }
            }
        }

        return queue.size();
    }

    private int btn1(int curr, int n) {
        return curr ^ ((1 << n) - 1);
    }

    private int btn2(int curr, int n) {
        for (int i = 0; i < n; i += 2) {
            curr ^= 1 << i;
        }
        return curr;
    }

    private int btn3(int curr, int n) {
        for (int i = 1; i < n; i += 2) {
            curr ^= 1 << i;
        }
        return curr;
    }

    private int btn4(int curr, int n) {
        for (int i = 0; i < n; i += 3) {
            curr ^= 1 << i;
        }
        return curr;
    }
}