LeetCode 957. N 天后的牢房

约 6 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 华为
标签
数组 哈希表 数学 位运算

题目描述

✅ 957. N 天后的牢房

image-20260929105419055

image-20260929105419219

题意分析

八个牢房每天同时更新：一个内部牢房的左右邻居状态相同，下一天它就为 1，否则为 0。首尾没有两个邻居，每次更新后都为 0。给定初始状态和天数，返回完成这些次更新后的状态；初始首尾并不要求为 0。

解法：状态压缩 + 循环跳跃

核心思路

[!blue]

用一个八位整数保存整排状态，第 i 位对应 cells[i]。计算下一天时，从旧整数取出第 i - 1、i + 1 位，若相同就在新整数的第 i 位置 1。新整数初始为 0，只处理内部六格，首尾自然保持为 0；所有判断都读旧状态，符合同时更新的要求。

相同的完整状态一定产生相同的下一状态，而可能的状态有限，所以反复更新最终会进入循环。第一天后首尾固定为 0，只剩六个自由位，最多有 64 种状态。初态可能在循环外，不能从第零天直接套用一个固定周期，必须根据实际重复状态判断。

用 seen[state] 记录上次处在这个状态时的剩余天数 prev。再次遇到它时，当前还剩 n 天，差值 prev - n 表示一段回到同一状态的完整循环长度，或完整周期的整数倍。跳过这么多天不会改变当前状态，因此可以令 n %= prev - n，只保留不足这段循环的余数。

每次真正更新后剩余天数减一，取模也不会增大它，因此再次遇到记录时 prev - n 一定为正。取模后如果 n == 0，当前状态已经是目标状态，应立刻结束；否则继续模拟一天。整个过程中，state 和剩余的 n 始终表示一个与原任务等价的求解位置。

解题步骤

  1. 把初始数组编码为整数，创建状态到剩余天数的映射。
  2. 当 n > 0 时，若当前状态已出现，就用两次剩余天数之差对 n 取模。
  3. 记录当前状态及缩短后的剩余天数；若剩余为 0，直接退出。
  4. 用旧状态计算新状态，再将剩余天数减一。
  5. 结束后按相同的位序取出八位，恢复结果数组。

代码实现

class Solution {
    public int[] prisonAfterNDays(int[] cells, int n) {
        int state = encode(cells);
        // seen 记录到达某状态时尚余的天数。
        Map<Integer, Integer> seen = new HashMap<>();

        while (n > 0) {
            if (seen.containsKey(state)) {
                int prev = seen.get(state);
                // 重复状态允许跳过完整周期，剩余天数差是周期长度的整数倍。
                int cycle = prev - n;

                n %= cycle;
            }

            seen.put(state, n);

            if (n == 0) {
                break;
            }

            state = nextState(state);
            n--;
        }

        return decode(state);
    }

    private int nextState(int state) {
        // 全新变量构造结果，保证读到的都是前一天的值。
        int next = 0;

        for (int i = 1; i <= 6; i++) {
            int left = (state >> (i - 1)) & 1;
            int right = (state >> (i + 1)) & 1;

            if (left == right) {
                next |= 1 << i;
            }
        }

        return next;
    }

    private int encode(int[] cells) {
        int state = 0;

        for (int i = 0; i < 8; i++) {
            state |= (cells[i] & 1) << i;
        }

        return state;
    }

    private int[] decode(int state) {
        int[] cells = new int[8];

        for (int i = 0; i < 8; i++) {
            cells[i] = (state >> i) & 1;
        }

        return cells;
    }
}

func prisonAfterNDays(cells []int, n int) []int {
    state := encode(cells)
    // seen 记录到达某状态时尚余的天数。
    seen := make(map[int]int)

    for n > 0 {
        if prev, ok := seen[state]; ok {
            // 重复状态允许跳过完整周期，剩余天数差是周期长度的整数倍。
            cycle := prev - n
            n %= cycle
        }
        seen[state] = n
        if n == 0 {
            break
        }
        state = nextState(state)
        n--
    }
    return decode(state)
}

func nextState(state int) int {
    // 全新变量构造结果，保证读到的都是前一天的值。
    next := 0
    for i := 1; i <= 6; i++ {
        left := (state >> (i - 1)) & 1
        right := (state >> (i + 1)) & 1
        if left == right {
            next |= 1 << i
        }
    }
    return next
}

func encode(cells []int) int {
    state := 0
    for i := 0; i < 8; i++ {
        state |= (cells[i] & 1) << i
    }
    return state
}

func decode(state int) []int {
    cells := make([]int, 8)
    for i := 0; i < 8; i++ {
        cells[i] = (state >> i) & 1
    }
    return cells
}

复杂度分析

  • 时间复杂度：$O(1)$。牢房数固定为 8，第一天后最多 64 种状态，再加可能在其外的一个初态；首次重复前只会访问常数种状态，跳过循环后还需模拟的步数不足一个循环，每步也只处理固定六个内部位置。
  • 空间复杂度：$O(1)$，状态映射至多保存 65 项，编码和输出长度也固定。

关键点总结

[!green]

  • 状态重复且转移确定，才能把未来的完整循环从剩余天数中删去。
  • 映射保存剩余天数，两次记录相减得到可跳过的循环长度。
  • 先处理可能的环外过程，再依据实际重复跳跃，不假定初态已经在环内。

易错点总结

[!yellow]

  • 原地逐格覆盖会让后面的格子读到本轮新值，必须从旧状态统一生成新状态。
  • 只比较部分牢房就判断循环，不能保证后续完整状态相同。
  • 取模后余数为 0 还更新一天，会比目标多走一步。
  • 编码和解码若使用不同位序，会把结果位置颠倒。
  • 初态首尾可能为 1，不能在正式执行第一天更新前就把它们当作 0。

相似题目

题目 难度 关联与区别
202. 快乐数 简单 有限状态的确定性转移最终进入循环，本题记录状态首次出现的天数后可跳过整周期。
289. 生命游戏 中等 同样按旧邻居状态同步更新，不能一边修改当前数组一边让后续格子读取新值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/43973728
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！