LeetCode 957. N 天后的牢房

2022-04-27 HGNULB 约 13 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 957. N 天后的牢房

题意分析

一排 8 间牢房，cells[i] 为 1 表示有人、0 表示空。每过一天，所有房间同时按同一条规则更新：如果房间的左右两个邻居状态相同，它变成 1；否则变成 0。首尾两间房只有一个邻居，因此固定变成 0。给出初始状态和天数 n，求 n 天后的状态。

要抓住的第一个信号是「8 间牢房」这个写死的数字。状态由 8 个二进制位组成，总共只有 $2^8 = 256$ 种可能；而且从第一天起首尾必为 0，实际可达状态最多 $2^6 = 64$ 种。状态空间有限，而演化规则是确定性的（当前状态唯一决定下一状态），这两点合起来必然导致：演化序列迟早会重复，一旦重复就永远按同一个环循环下去。

第二个信号是 n 的范围——最大到 $10^9$。逐天模拟是 $O(n)$，十亿次数组操作必然超时。题目一边把状态数压到几十，一边把天数放大到十亿，意图非常明确：找到循环节，用取模把天数缩小。

更新规则里「同时」两个字是必须落实的细节。所有房间读的都是前一天的状态，不能一边算一边把结果写回原数组，否则靠后的房间会读到已经被本轮改写过的邻居。

边界要留意：首尾房间没有两个邻居，规则约定它们变成 0，所以从第 1 天开始 cells[0] 与 cells[7] 恒为 0；这意味着初始状态（第 0 天）通常不在循环里，环是从第 1 天之后才形成的，这一点决定了不能简单地假设「周期从第 0 天开始」。另外 n 至少为 1，但实现上让 n = 0 直接返回初始状态也不会出错。

解法：状态压缩 + 找环

核心思路

暴力就是老老实实模拟 n 天，每天扫 8 个房间。单天成本是常数，总成本 $O(n)$，n 到 $10^9$ 时约十亿次循环，必然超时。

瓶颈不在单天的计算量（那已经是常数了），而在天数本身。观察：状态只有有限种，而 next 是一个从状态到状态的确定性函数，所以序列 s0 → s1 → s2 → ... 一定在有限步内进入循环。既然进了循环，在循环内部走 k 步和走 k mod cycle 步的结果完全相同，于是可以把十亿天砍成不超过一个周期的天数。

要把这个想法落地，先把「状态」变成可比较、可做哈希键的东西。8 个格子天然对应 8 个二进制位，把 cells[i] 编码到整数的第 i 位，状态就成了一个 0..255 的整数。这样比较两个状态是一次整数相等判断，记录访问过的状态用一张哈希表即可，比逐位比对数组干净得多。

找环的写法有两种常见思路。一种是先跑出完整的状态序列存进列表，找到重复点，算出环起点与环长，再定位目标下标；另一种是本文采用的「记录剩余天数」写法，它更短也更不易错：哈希表 seen 存 状态 → 到达该状态时还剩多少天。当再次遇到同一个状态时，说明兜了一圈回来，两次记录的剩余天数之差就是环长 cycle，此时直接令 n %= cycle，之后继续逐天模拟即可——剩下的天数已经不超过一个周期。

维持的不变量是：循环的每一轮开始时，(state, n) 这一对完整描述了「还需要从当前状态再演化 n 天」这个子问题，答案与原问题一致。三种操作都保持它：记录 seen 不改变任何东西；n %= cycle 因为环内走整数圈回到原地，子问题等价；模拟一天则同时推进 state 并把 n 减一。当 n 归零时，state 就是答案。

这个写法的好处是不必显式区分「环前的尾巴」和「环本身」——取模只会在真正进入环之后才触发（因为只有环内状态才会被第二次遇到），尾巴部分自动被逐天模拟走完。

解题步骤

编码初始状态：把 cells[i] 放到整数的第 i 位，得到 state。为什么要编码：整数可以直接做哈希键和相等比较，避免为数组写哈希与比较逻辑，也避免误用引用相等。位序（低位对应下标 0）只要编码解码保持一致即可，反过来也行，但两处必须统一。

主循环条件 n > 0：语义是「还剩 n 天要走」。为什么用剩余天数而不是已走天数：剩余天数可以直接被取模缩小，而已走天数还要额外记录起点。

遇到重复状态就取模：若 seen 里已有当前 state，取出上次记录的剩余天数 prev，则 cycle = prev - n 就是环长（上次到这里时还剩 prev 天，这次还剩 n 天，中间正好走了一整圈）。令 n %= cycle。为什么 cycle 一定为正：prev 是更早记录的，那时剩余天数一定更大。

记录当前状态的剩余天数：seen.put(state, n)。为什么在取模之后再写：取模后的 n 才是当前子问题的真实剩余天数，写入旧值会让后续再次触发取模时算出错误的环长。实际上取模一旦发生，后面就不会再触发第二次取模了，但保持写入值与循环不变量一致是更稳妥的写法。

提前退出：若此时 n == 0 就 break。为什么要单独判：取模可能把 n 直接变成 0，说明目标日恰好落在当前状态上，再模拟一天就多走了。

模拟一天：state = nextState(state)，然后 n--。两步必须成对出现，顺序不能反着理解——先算出下一天的状态，再把剩余天数减一。

nextState 只处理下标 1..6：新状态从 0 开始构造，第 i 位取决于旧状态的第 i-1 位与第 i+1 位是否相等。为什么首尾不用管：新状态初值为 0，第 0 位和第 7 位不去设置就天然是 0，正好符合规则。为什么必须基于旧 state 读取而不是边写边读：更新是同时发生的，用一个全新的 next 变量构造结果，从源头杜绝了「读到本轮新值」的错误。

解码返回：把整数按同样的位序还原成长度 8 的数组。

以 cells = [0,1,0,1,1,0,0,1]、n = 7 走一遍。
第 0 天状态是 [0,1,0,1,1,0,0,1]，seen 记下它对应剩余 7 天。
演化到第 1 天：逐位算，下标 1 的邻居是 0 与 0，相等得 1；下标 2 的邻居是 1 与 1，得 1；下标 3 的邻居是 0 与 1，得 0；下标 4 的邻居是 1 与 0，得 0；下标 5 的邻居是 1 与 0，得 0；下标 6 的邻居是 0 与 1，得 0。结果 [0,1,1,0,0,0,0,0]，剩余 6 天。注意首尾已经变成 0，此后永远是 0。
第 2 天：[0,0,0,0,1,1,1,0]，剩余 5 天。
第 3 天：[0,1,1,0,0,1,0,0]，剩余 4 天。
第 4 天：[0,0,0,0,0,1,0,0]，剩余 3 天。
第 5 天：[0,1,1,1,0,1,0,0]，剩余 2 天。
第 6 天：[0,0,1,0,1,1,0,0]，剩余 1 天。
第 7 天：[0,0,1,1,0,0,0,0]，剩余 0 天，循环条件不满足，退出。返回 [0,0,1,1,0,0,0,0]，与预期一致。

这一趟里 n 太小，还没走到重复状态就结束了，取模分支没被触发。把同样的初始状态配上 n = 1000000000 就能看到取模生效：模拟会在若干天后再次遇到某个已记录的状态（本题的环长为 14），此时 cycle = prev - n = 14，n 从上亿一步缩到 n mod 14，随后最多再模拟 13 天就结束，总迭代次数只有几十。

代码实现

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)$，与 n 无关。凭什么：从第 1 天起首尾恒为 0，可达状态最多 $2^6 = 64$ 种，所以最多迭代 65 天就必然撞上重复状态并完成取模；取模后剩余天数严格小于环长（不超过 64），因此总迭代次数被一个常数封顶，每次迭代内部是固定的 6 次位运算与一次哈希操作。

空间复杂度：$O(1)$。凭什么：seen 中的键来自同一个有限状态集合，最多存 64 项；其余只有几个整型变量和长度固定为 8 的结果数组，都与输入的 n 无关。

关键点总结

「状态有限 + 转移确定」必然产生循环，这是抽屉原理的直接推论；一旦题目把状态数压得很小又把步数放得极大，就是在明示用循环节取模。

定长小规模的 0/1 数组应当编码成整数：比较、哈希、存储全部变成常数操作，还能顺手用位运算表达邻居关系。编码与解码的位序必须严格一致，这是最容易出岔子的地方。

「同时更新」类的元胞自动机必须写入一个全新容器，绝不能原地改。凡是规则里出现「同时」「一轮之内」的字眼，都要检查这一点。

用「状态 → 剩余步数」记录访问历史，比「状态 → 第几步」更省事：环长直接由两次剩余步数相减得到，也不必显式区分环前尾巴与环体。

取模之后要立刻检查是否已经归零，否则会多走一步，这是找环类代码最典型的差一错误。

面试视角：面试官想听的推理链是「状态数只有 256 → 必然成环 → 天数取模」。先把这条链说完再动手写，然后主动指出「首尾从第一天起恒为 0，所以初始状态可能不在环上，环不是从第 0 天开始的」——这句话能立刻区分是否真的想清楚了；若被追问其他找环方法，可以提 Floyd 判圈（快慢指针）在状态空间上同样适用，只是本题状态太少，哈希表更直观。

易错点总结

错误写法：直接逐天模拟 n 天不找环 → 用例 n = 1000000000 需要十亿次迭代，必然超时。

错误写法：在原数组上原地更新，cells[i] = (cells[i-1] == cells[i+1]) ? 1 : 0 → 用例 [0,1,0,1,1,0,0,1] 中算下标 2 时读到的 cells[1] 已是本轮新值，第 1 天就得出错误的 [0,1,0,...]，后续全盘皆错。

错误写法：认为循环从第 0 天开始，直接令 n %= 14 后模拟 → 用例 [1,0,0,1,0,0,1,0]、n = 14 中初始状态首尾非 0 不在环上，取模后得 n = 0 直接返回初始状态，而正确答案是环上的另一个状态。

错误写法：取模后不检查 n == 0 就继续模拟一天 → 用例中目标日恰好落在当前状态时会多演化一天，返回的是第 n + 1 天的结果。

错误写法：cycle 算成 n - prev → 用例中得到负数，n %= cycle 在 Java 里得到负的剩余天数，while (n > 0) 直接不成立，函数返回当天状态，答案错误。

错误写法：seen 记录的是「已走天数」却仍用 prev - n 求环长 → 用例中两者符号相反，环长算反，取模结果无意义。

错误写法：nextState 里循环写成 for (int i = 0; i < 8; i++) → 用例中读取 state >> (0 - 1) 与 state >> 8，Java 的移位取模 32 会得到诡异结果，首尾位被错误置 1，而规则要求它们恒为 0。

错误写法：nextState 判断写成 left != right 时置 1 → 用例 [0,1,0,1,1,0,0,1] 第 1 天得到 [0,0,0,1,1,1,1,0]，与正确的 [0,1,1,0,0,0,0,0] 完全相反。

错误写法：编码用低位对应下标 0，解码却用高位对应下标 0 → 用例中结果数组整体被左右翻转，只有回文状态才碰巧正确。

错误写法：用 int[] 数组本身当哈希键 → 用例中 Java 的数组按引用比较，每天都是新数组，seen 永远命中不了，等价于退化成逐天模拟并超时；Go 里切片根本不能作为 map 的键，编译不过。

错误写法：先把状态序列全部存进 List 再找重复，但忘记环起点不一定是下标 0 → 用例 [1,0,0,1,0,0,1,0] 中环从第 1 天开始，若按 n % list.size() 定位会取到错误的元素。

错误写法：把 n 声明为 int 却在中间做了 n * something 之类的放大运算 → 用例 n = 10^9 时溢出成负数，循环直接退出。

相似题目

题目	难度	考察点
289. 生命游戏	中等	同为同时更新的元胞自动机，但要求原地做，靠双位编码保存新旧两态
202. 快乐数	简单	同样是确定性转移下的成环判定，但只需判断是否进环而不必求环长
142. 环形链表 II	中等	找环起点的经典模型，用快慢指针把空间降到 $O(1)$，可迁移到状态空间
1041. 困于环中的机器人	中等	靠「四轮之内必回到起点或形成环」的周期性质，无需哈希记录状态
457. 环形数组是否存在循环	中等	在数组上找环并附加方向与长度约束，考的是访问标记而非状态压缩
874. 模拟行走机器人	中等	纯逐步模拟且步数可控，无循环可利用，重点在障碍物的哈希查询