Medium

题目描述

一排有 8 个牢房，每个牢房要么被占用，要么空着。

每天，根据以下规则，牢房的占用状态会发生变化：

  • 如果一个牢房的两个相邻牢房都被占用或都是空的，那么这个牢房就会被占用。
  • 否则，它就会空着。

注意，由于监狱是一排，第一个和最后一个牢房不能有两个相邻的牢房。

给你一个整数数组 cells，其中 cells[i] == 1 表示第 i 个牢房被占用，cells[i] == 0 表示第 i 个牢房是空的，以及一个整数 n。

返回 n 天后监狱的状态（即经过上述 n 次变化后的状态）。

示例 1：

输入：cells = [0,1,0,1,1,0,0,1], n = 7
输出：[0,0,1,1,0,0,0,0]
解释：下表总结了监狱每天的状态：
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

示例 2：

输入：cells = [1,0,0,1,0,0,1,0], n = 1000000000
输出：[0,0,1,1,1,1,1,0]

提示：

  • cells.length == 8
  • cells[i] 要么是 0，要么是 1
  • 1 <= n <= 10^9

解题思路

这道题的关键在于观察状态变化的周期性。由于牢房只有8个，每个牢房只有0或1两种状态，所以总共只有 2^8 = 256 种可能的状态。因此状态变化必然会形成周期。

解题思路：

  1. 模拟状态转换：首先实现状态转换逻辑，注意第一个和最后一个牢房总是变为0（因为它们没有两个相邻牢房）。

  2. 寻找周期：从第一天开始记录每天的状态，当遇到重复状态时，说明找到了周期。由于初始状态可能不在周期内，需要特别处理。

  3. 优化计算：一旦找到周期，就可以通过取模运算直接计算第n天的状态，避免逐天模拟。

具体实现：

  • 使用哈希表记录每个状态第一次出现的天数
  • 当发现重复状态时，计算周期长度
  • 使用 (n - start) % cycle 来确定最终状态在周期中的位置

这种方法特别适合处理n很大的情况，时间复杂度从O(n)优化到O(周期长度)，通常周期长度很小。

代码实现

class Solution {
public:
    vector<int> prisonAfterNDays(vector<int>& cells, int n) {
        if (n == 0) return cells;
        
        unordered_map<string, int> seen;
        vector<vector<int>> history;
        vector<int> current = cells;
        
        for (int day = 1; day <= n; day++) {
            vector<int> next(8, 0);
            for (int i = 1; i < 7; i++) {
                if (current[i-1] == current[i+1]) {
                    next[i] = 1;
                }
            }
            current = next;
            
            string state = "";
            for (int cell : current) {
                state += to_string(cell);
            }
            
            if (seen.count(state)) {
                int cycleStart = seen[state];
                int cycleLength = day - cycleStart;
                int targetDay = cycleStart + (n - cycleStart) % cycleLength;
                return history[targetDay - 1];
            }
            
            seen[state] = day;
            history.push_back(current);
        }
        
        return current;
    }
};

class Solution:
    def prisonAfterNDays(self, cells: List[int], n: int) -> List[int]:
        if n == 0:
            return cells
        
        seen = {}
        history = []
        current = cells[:]
        
        for day in range(1, n + 1):
            next_state = [0] * 8
            for i in range(1, 7):
                if current[i-1] == current[i+1]:
                    next_state[i] = 1
            current = next_state
            
            state = tuple(current)
            if state in seen:
                cycle_start = seen[state]
                cycle_length = day - cycle_start
                target_day = cycle_start + (n - cycle_start) % cycle_length
                return history[target_day - 1]
            
            seen[state] = day
            history.append(current[:])
        
        return current

public class Solution {
    public int[] PrisonAfterNDays(int[] cells, int n) {
        if (n == 0) return cells;
        
        Dictionary<string, int> seen = new Dictionary<string, int>();
        List<int[]> history = new List<int[]>();
        int[] current = (int[])cells.Clone();
        
        for (int day = 1; day <= n; day++) {
            int[] next = new int[8];
            for (int i = 1; i < 7; i++) {
                if (current[i-1] == current[i+1]) {
                    next[i] = 1;
                }
            }
            current = next;
            
            string state = string.Join("", current);
            if (seen.ContainsKey(state)) {
                int cycleStart = seen[state];
                int cycleLength = day - cycleStart;
                int targetDay = cycleStart + (n - cycleStart) % cycleLength;
                return history[targetDay - 1];
            }
            
            seen[state] = day;
            history.Add((int[])current.Clone());
        }
        
        return current;
    }
}

var prisonAfterNDays = function(cells, n) {
    if (n === 0) return cells;
    
    const seen = new Map();
    let current = [...cells];
    
    for (let day = 1; day <= n; day++) {
        const key = current.join('');
        
        if (seen.has(key)) {
            const cycleStart = seen.get(key);
            const cycleLength = day - cycleStart;
            const remaining = (n - cycleStart) % cycleLength;
            
            for (let i = 0; i < remaining; i++) {
                current = getNextDay(current);
            }
            return current;
        }
        
        seen.set(key, day);
        current = getNextDay(current);
    }
    
    return current;
};

function getNextDay(cells) {
    const next = new Array(8).fill(0);
    for (let i = 1; i < 7; i++) {
        if (cells[i-1] === cells[i+1]) {
            next[i] = 1;
        }
    }
    return next;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(min(n, 2^6)) = O(min(n, 64))，最多64种不同状态（去除首尾固定为0的位置）
空间复杂度O(min(n, 2^6)) = O(min(n, 64))，用于存储状态历史和哈希表