Medium

题目描述

房间中有 n 个灯泡，编号从 1 到 n，初始时所有灯泡都是开着的，墙上有 4 个按钮。每个按钮都有不同的功能：

  • 按钮 1：切换所有灯泡的状态。
  • 按钮 2：切换编号为偶数的灯泡的状态（即 2, 4, …）。
  • 按钮 3：切换编号为奇数的灯泡的状态（即 1, 3, …）。
  • 按钮 4：切换编号为 j = 3k + 1 的灯泡的状态，其中 k = 0, 1, 2, …（即 1, 4, 7, 10, …）。

你必须恰好按下 presses 次按钮。每次按下时，你可以选择按下四个按钮中的任意一个。

给定两个整数 n 和 presses，返回执行所有 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

解题思路

这道题的关键是理解按钮的周期性质和数学性质。

首先分析按钮的效果：

  • 按钮1影响所有位置
  • 按钮2影响偶数位置
  • 按钮3影响奇数位置
  • 按钮4影响位置1, 4, 7, 10…（即3k+1位置）

关键观察：

  1. 按钮的交换性：按钮的按下顺序不影响最终结果
  2. 按钮的幂等性：每个按钮按偶数次等于没按，按奇数次等于按一次
  3. 周期性：由于按钮4的周期是3，整个系统的状态在前3个灯泡后开始重复

因此只需要考虑前min(n,3)个灯泡的状态，因为：

  • 当n>=3时，第4个灯泡的状态等于第1个灯泡
  • 第5个灯泡状态等于第2个灯泡，以此类推

算法步骤：

  1. 枚举每个按钮按下0次或1次的所有可能组合（2^4=16种）
  2. 对于每种组合，检查按下次数的奇偶性是否与presses匹配
  3. 计算前min(n,3)个灯泡的最终状态
  4. 统计不同状态的数量

时间复杂度O(1)，因为只需要枚举16种固定组合。

代码实现

class Solution {
public:
    int flipLights(int n, int presses) {
        set<vector<int>> states;
        
        for (int i = 0; i < 16; i++) {
            vector<int> pressed(4);
            for (int j = 0; j < 4; j++) {
                pressed[j] = (i >> j) & 1;
            }
            
            int totalPresses = pressed[0] + pressed[1] + pressed[2] + pressed[3];
            if (totalPresses % 2 != presses % 2 || totalPresses > presses) {
                continue;
            }
            
            vector<int> lights(min(n, 3), 1);
            
            if (pressed[0]) {
                for (int k = 0; k < lights.size(); k++) {
                    lights[k] ^= 1;
                }
            }
            if (pressed[1]) {
                for (int k = 1; k < lights.size(); k += 2) {
                    lights[k] ^= 1;
                }
            }
            if (pressed[2]) {
                for (int k = 0; k < lights.size(); k += 2) {
                    lights[k] ^= 1;
                }
            }
            if (pressed[3]) {
                for (int k = 0; k < lights.size(); k += 3) {
                    lights[k] ^= 1;
                }
            }
            
            states.insert(lights);
        }
        
        return states.size();
    }
};

class Solution:
    def flipLights(self, n: int, presses: int) -> int:
        states = set()
        
        for i in range(16):
            pressed = [(i >> j) & 1 for j in range(4)]
            
            total_presses = sum(pressed)
            if total_presses % 2 != presses % 2 or total_presses > presses:
                continue
            
            lights = [1] * min(n, 3)
            
            if pressed[0]:  # Button 1
                for k in range(len(lights)):
                    lights[k] ^= 1
            if pressed[1]:  # Button 2
                for k in range(1, len(lights), 2):
                    lights[k] ^= 1
            if pressed[2]:  # Button 3
                for k in range(0, len(lights), 2):
                    lights[k] ^= 1
            if pressed[3]:  # Button 4
                for k in range(0, len(lights), 3):
                    lights[k] ^= 1
            
            states.add(tuple(lights))
        
        return len(states)

public class Solution {
    public int FlipLights(int n, int presses) {
        HashSet<string> states = new HashSet<string>();
        
        for (int i = 0; i < 16; i++) {
            int[] pressed = new int[4];
            for (int j = 0; j < 4; j++) {
                pressed[j] = (i >> j) & 1;
            }
            
            int totalPresses = pressed[0] + pressed[1] + pressed[2] + pressed[3];
            if (totalPresses % 2 != presses % 2 || totalPresses > presses) {
                continue;
            }
            
            int[] lights = new int[Math.Min(n, 3)];
            for (int k = 0; k < lights.Length; k++) {
                lights[k] = 1;
            }
            
            if (pressed[0] == 1) {
                for (int k = 0; k < lights.Length; k++) {
                    lights[k] ^= 1;
                }
            }
            if (pressed[1] == 1) {
                for (int k = 1; k < lights.Length; k += 2) {
                    lights[k] ^= 1;
                }
            }
            if (pressed[2] == 1) {
                for (int k = 0; k < lights.Length; k += 2) {
                    lights[k] ^= 1;
                }
            }
            if (pressed[3] == 1) {
                for (int k = 0; k < lights.Length; k += 3) {
                    lights[k] ^= 1;
                }
            }
            
            states.Add(string.Join("", lights));
        }
        
        return states.Count;
    }
}

var flipLights = function(n, presses) {
    const states = new Set();
    
    for (let i = 0; i < 16; i++) {
        const pressed = [];
        for (let j = 0; j < 4; j++) {
            pressed[j] = (i >> j) & 1;
        }
        
        const totalPresses = pressed[0] + pressed[1] + pressed[2] + pressed[3];
        if (totalPresses % 2 !== presses % 2 || totalPresses > presses) {
            continue;
        }
        
        const lights = new Array(Math.min(n, 3)).fill(1);
        
        if (pressed[0]) {
            for (let k = 0; k < lights.length; k++) {
                lights[k] ^= 1;
            }
        }
        if (pressed[1]) {
            for (let k = 1; k < lights.length; k += 2) {
                lights[k] ^= 1;
            }
        }
        if (pressed[2]) {
            for (let k = 0; k < lights.length; k += 2) {
                lights[k] ^= 1;
            }
        }
        if (pressed[3]) {
            for (let k = 0; k < lights.length; k += 3) {
                lights[k] ^= 1;
            }
        }
        
        states.add(lights.join(''));
    }
    
    return states.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(1)只需枚举16种固定的按钮组合，每种组合的处理时间为常数
空间复杂度O(1)使用的额外空间与输入规模无关，最多存储有限个状态

相关题目