原文链接: https://leetcode-cn.com/problems/bulb-switcher-ii

英文原文

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

Example 4:

Input: n = 1, presses = 0
Output: 1
Explanation: Status can only be [on] since you cannot press any of the buttons.

Example 5:

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

 

Constraints:

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

中文题目

现有一个房间，墙上挂有 n 只已经打开的灯泡和 4 个按钮。在进行了 m 次未知操作后，你需要返回这 n 只灯泡可能有多少种不同的状态。

假设这 n 只灯泡被编号为 [1, 2, 3 ..., n]，这 4 个按钮的功能如下：

1. 将所有灯泡的状态反转（即开变为关，关变为开）
2. 将编号为偶数的灯泡的状态反转
3. 将编号为奇数的灯泡的状态反转
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].

通过代码

官方题解

解决方法：

方法一：减少搜索空间 [通过]

由于搜索空间非常大（$2^N$ 个灯光的状态，$4^M$ 个操作顺序 ），让我们尝试减少它。

前6个灯唯一地决定了其余的灯。这是因为每一个修改 第 $x$ 的灯光的操作都会修改第 $(x+6)$ 的灯光。

另外：进行 A 操作后接 B 操作 和 B 操作后接 A 操作是一样的，所以我们可以假设我们按顺序进行所有操作。

最后，连续两次执行相同的操作与不执行任何操作相同。所以我们只需要考虑每个操作是 0 次还是 1 次。

算法：

• 假设我们做了第 $i$ 个操作 $f_i$ 次。 也就是说：$c_i = f_i$ ($\mod 2$ )
• 因为 $c_i \equiv f_i$ and $c_i \leq f_i$，所以 $\sum f_i \not \equiv \sum c_i$ 和 $\sum f_i<\sum c_i$ 是不可能的。否则，可以通过一个简单的构造来实现：执行由 $c_i$ 指定的操作，然后使用剩余的偶数操作执行操作 1。
• 对于每个可能性，让我们模拟并记住前 6 个灯的状态，将其存储在集合结构 seen 中。最后，我们将返回这个集合的大小。

[ ]
def flipLights(self, n, m):
    seen = set()
    for cand in itertools.product((0, 1), repeat = 4):
        if sum(cand) % 2 == m % 2 and sum(cand) <= m:
            A = []
            for i in xrange(min(n, 3)):
                light = 1
                light ^= cand[0]
                light ^= cand[1] and i % 2
                light ^= cand[2] and i % 2 == 0
                light ^= cand[3] and i % 3 == 0
                A.append(light)
            seen.add(tuple(A))

    return len(seen)

[ ]
class Solution {
    public int flipLights(int n, int m) {
        Set<Integer> seen = new HashSet();
        n = Math.min(n, 6);
        int shift = Math.max(0, 6-n);
        for (int cand = 0; cand < 16; ++cand) {
            int bcount = Integer.bitCount(cand);
            if (bcount % 2 == m % 2 && bcount <= m) {
                int lights = 0;
                if (((cand >> 0) & 1) > 0) lights ^= 0b111111 >> shift;
                if (((cand >> 1) & 1) > 0) lights ^= 0b010101 >> shift;
                if (((cand >> 2) & 1) > 0) lights ^= 0b101010 >> shift;
                if (((cand >> 3) & 1) > 0) lights ^= 0b100100 >> shift;
                seen.add(lights);
            }
        }
        return seen.size();
    }
}

复杂度分析

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

方法二：

算法：

• 因为前 6 个灯唯一地决定了其余的灯。这是因为修改第 $x$ 灯光的每个操作都会修改 第 $(x+6)$ 灯光，因此 $x$ 灯光始终等于 $(x+6)$ 灯光。
• 实际上，前 3 个灯唯一地确定了序列的其余部分，如下表所示，用于执行操作 a, b, c, d:

Light 1 = 1 + a + c + d
Light 2 = 1 + a + b
Light 3 = 1 + a + c
Light 4 = 1 + a + b + d
Light 5 = 1 + a + c
Light 6 = 1 + a + b

• 上述理由表明，在不损失一般性的情况下，取 $n = min(n, 3)$ 是合理的。
• 让我们用 $(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(object):
    def flipLights(self, n, m):
        n = min(n, 3)
        if m == 0: return 1
        if m == 1: return [2, 3, 4][n-1]
        if m == 2: return [2, 4, 7][n-1]
        return [2, 4, 8][n-1]

[ ]
class Solution {
    public int flipLights(int n, int m) {
        n = Math.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;
    }
}

复杂度分析

• 时空复杂性：$O(1)$。整个程序使用常量。

统计信息

通过次数	提交次数	AC比率
3974	7240	54.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
灯泡开关	中等