LeetCode 289. 生命游戏
目录
题目描述
题意分析
给一个
m × n的 0/1 面板，1表示活细胞、0表示死细胞。每个细胞有八个方向的邻居（含四个对角）。按四条规则同时演化一步，把结果写回原面板。四条规则可以合并成两句：活细胞在活邻居数为 2 或 3 时存活，否则死亡；死细胞在活邻居数恰好为 3 时复活，否则保持死亡。合并后只剩两个判定分支，比照抄四条规则更不容易漏。
全题的关键词是「同时」。所有细胞的下一状态都必须依据同一份上一代面板计算，而不是边算边改。如果按行列顺序就地覆盖，那么当处理到
(i, j)时，它左边和上面的邻居已经变成了新一代的值，用这些值统计出的活邻居数是错的。这就是本题唯一的技术难点，也是它被归为中等题的原因。最直接的解决办法是复制一份面板，读旧写新。但题目的进阶要求明确说了「你能否原地解决」，这个信号排除了拷贝，要求我们把新旧两代状态同时塞进同一个整数格子里。
面板取值只有 0 和 1，而
int有 32 位，信息容量远远富余——这就是原地编码可行的物质基础。只要新编码满足「能从中恢复出旧状态」，第一趟就可以边写边算，第二趟再统一解码。边界有三处：面板的四条边和四个角上的细胞邻居数不足 8 个，越界方向按不存在处理（不能当成死细胞之外的第三种值，效果上等价于 0，但必须靠边界检查跳过而不是访问越界内存）；面板至少 1 × 1，不会出现空面板但仍值得防；进阶里还提到面板无限大的情形，那要改用稀疏表示只记录活细胞坐标。
解法：原地状态编码
核心思路
朴素做法是深拷贝一份面板
copy，遍历时统计邻居读copy、写结果改board。它完全正确、也最好写，但额外占用 $O(mn)$ 空间，没有回答进阶要求。瓶颈在于：我们只是为了保住「旧值」这一个比特，就复制了整张面板。关键观察是：每个格子真正需要携带的信息只有两比特——旧状态和新状态。原本
0和1只用了「旧状态」这一维，完全可以再引入两个新取值，把「新状态」这一维叠加进去。于是设计一套四值编码：
0= 旧死、新死；1= 旧活、新活；2= 旧活、新死；3= 旧死、新活。这套编码的核心性质是：旧状态为活 ⟺ 值属于
{1, 2}，新状态为活 ⟺ 值属于{1, 3}。两个维度都能被无损读出，互不干扰。之所以要新增两个值而不是原地把 1 改成 0，是因为「不变的格子」和「变化的格子」必须区分开：保持不变的格子沿用
0/1无需改动，只有发生翻转的格子才需要新编码2/3。这样第二趟解码时，只要把2归成0、3归成1即可，0和1原样不动。于是可以显式写出第一趟遍历的循环不变量：在处理格子
(i, j)时，面板上任意格子(x, y)的值都完整保留了它的旧状态——已处理过的格子取值在{0,1,2,3}中但满足「旧活 ⟺ 值∈{1,2}」，未处理的格子仍是原始的0或1，同样满足这条判据。因此统计邻居时统一用board[x][y] == 1 || board[x][y] == 2判断，就能在混合了新旧编码的面板上正确读出旧状态。有了这个不变量，第一趟就可以放心地边遍历边就地改写，完全不需要关心处理顺序。第二趟只做一次纯粹的解码映射，与邻居无关，顺序同样任意。
另一种常见编码是用比特位：低位存旧状态、次低位存新状态，写入用
board[i][j] |= newState << 1，解码用board[i][j] >>= 1。它保存的信息相同，但数值约定与本文不同：位编码下1是旧活新死、2是旧死新活、3是旧活新活；统计旧活要检查最低位。两套编码不能混用判定或解码规则。
解题步骤
- 取出
m、n：m = board.length、n = board[0].length。为什么要先取——后面的越界判断要用到，且提前取出避免在三重循环里反复求长度。- 准备方向偏移
dirs = {-1, 0, 1}并用两层循环枚举(dx, dy)：为什么这样写而不是列出八个方向数组——两层循环共产生 9 个组合，去掉(0,0)恰好是八邻域，比手写两个长度为 8 的数组更短也更不易抄错。- 在邻居枚举里跳过
dx == 0 && dy == 0：为什么必须跳过——那是格子自身，把自己算进活邻居数会让所有判定失效。- 越界检查排在取值之前：
x < 0 || x >= m || y < 0 || y >= n就跳过。为什么顺序不能反——先访问board[x][y]会直接越界异常；同时「界外」在语义上等价于死细胞，跳过即可，不需要补零。- 统计条件写成
board[x][y] == 1 || board[x][y] == 2：为什么是这两个值——它们正是「旧状态为活」的全部编码；只判== 1会漏掉那些已经被处理成「活→死」的邻居，把它们错当成旧死。- 活细胞的死亡判定
board[i][j] == 1 && (live < 2 || live > 3)时写2：为什么条件是「小于 2 或大于 3」——活细胞只在活邻居数为 2 或 3 时存活，其余情况死亡；为什么活且存活的情况什么都不做——它的编码本来就该是1，保持原值即可，这是编码设计带来的省事之处。- 死细胞的复活判定
board[i][j] == 0 && live == 3时写3：为什么是「恰好 3」而不是「大于等于 3」——规则明确规定死细胞只在活邻居数正好为 3 时复活。- 注意这两个判定用的是
board[i][j]的当前值：由于(i, j)还没被本轮改写，它此刻仍是原始的0或1，直接比较即可，不需要解码。- 第二趟遍历解码：
2改成0、3改成1，其余不动。为什么必须分成独立的第二趟——若在第一趟里就解码，格子会立刻丢掉旧状态，后面的邻居再来统计时就读不到正确的旧值了。以
board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]走一遍（这是题目样例，期望结果是[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]）。第一趟，按行优先逐格处理：
(0,0)值为 0。邻居是(0,1)=1、(1,0)=0、(1,1)=0，活邻居数 1。死细胞且live != 3，不改，仍为0。
(0,1)值为 1。邻居(0,0)=0、(0,2)=0、(1,0)=0、(1,1)=0、(1,2)=1，活邻居数 1。活细胞且live < 2，改写为2（活→死）。
(0,2)值为 0。邻居(0,1)现在是2——按判据== 2算作旧活，计 1；(1,1)=0、(1,2)=1计 1，合计 2。死细胞且live != 3，不改。这里正是编码起作用的地方：如果统计时只认== 1，(0,1)会被漏掉，活邻居数变成 1。
(1,0)值为 0。邻居(0,0)=0、(0,1)=2（旧活，计 1）、(1,1)=0、(2,0)=1、(2,1)=1，合计 3。死细胞且live == 3，改写为3（死→活）。
(1,1)值为 0。邻居八个：(0,0)=0、(0,1)=2（计 1）、(0,2)=0、(1,0)=3——按判据3不属于{1,2}，算作旧死，不计；(1,2)=1计 1、(2,0)=1计 1、(2,1)=1计 1、(2,2)=1计 1，合计 5。死细胞且live != 3，不改。这里体现了3的另一半作用：它必须被判为旧死，否则活邻居数会多算成 6。
(1,2)值为 1。邻居(0,1)=2（计 1）、(0,2)=0、(1,1)=0、(2,1)=1、(2,2)=1，合计 3。活细胞且live在{2,3}内，存活，保持1。
(2,0)值为 1。邻居(1,0)=3（旧死，不计）、(1,1)=0、(2,1)=1、(3,0)=0、(3,1)=0，合计 1。活细胞且live < 2，改写为2。
(2,1)值为 1。邻居(1,0)=3不计、(1,1)=0、(1,2)=1计 1、(2,0)=2计 1、(2,2)=1计 1、(3,0)=0、(3,1)=0、(3,2)=0，合计 3。存活，保持1。
(2,2)值为 1。邻居(1,1)=0、(1,2)=1计 1、(2,1)=1计 1、(3,1)=0、(3,2)=0，合计 2。存活，保持1。
(3,0)值为 0。邻居(2,0)=2计 1、(2,1)=1计 1、(3,1)=0，合计 2。不改。
(3,1)值为 0。邻居(2,0)=2计 1、(2,1)=1计 1、(2,2)=1计 1、(3,0)=0、(3,2)=0，合计 3。死细胞且live == 3，改写为3。
(3,2)值为 0。邻居(2,1)=1计 1、(2,2)=1计 1、(3,1)=3（旧死，不计），合计 2。不改。第一趟结束后面板是
[[0,2,0],[3,0,1],[2,1,1],[0,3,0]]。第二趟解码：把每个
2换成0、每个3换成1，得到[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]，与期望结果完全一致。回头看，如果不用编码而直接就地改写（活变 0、死变 1），处理
(0,2)时(0,1)已经变成 0，活邻居数会算成 1 而不是 2；处理(1,1)时(1,0)已经变成 1，活邻居数会算成 6 而不是 5。虽然这两处恰好都不影响本例结果，但(1,0)这一格若把(0,1)算成死的，活邻居数就是 2 而非 3，它就不会复活，最终答案的第 2 行第 1 列会错成 0——这正是「必须区分新旧状态」的直接证据。
代码实现
// 统计邻居时只看原始状态：1 和 2 都代表原来是活细胞。
class Solution {
public void gameOfLife(int[][] board) {
int m = board.length;
int n = board[0].length;
int[] dirs = {-1, 0, 1};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int live = 0;
for (int dx : dirs) {
for (int dy : dirs) {
if (dx == 0 && dy == 0) {
continue;
}
int x = i + dx;
int y = j + dy;
if (x < 0 || x >= m || y < 0 || y >= n) {
continue;
}
if (board[x][y] == 1 || board[x][y] == 2) {
live++;
}
}
}
if (board[i][j] == 1 && (live < 2 || live > 3)) {
board[i][j] = 2;
} else if (board[i][j] == 0 && live == 3) {
board[i][j] = 3;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 2) {
board[i][j] = 0;
} else if (board[i][j] == 3) {
board[i][j] = 1;
}
}
}
}
}
// 统计邻居时只看原始状态：1 和 2 都代表原来是活细胞。
func gameOfLife(board [][]int) {
m := len(board)
n := len(board[0])
dirs := []int{-1, 0, 1}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
live := 0
for _, dx := range dirs {
for _, dy := range dirs {
if dx == 0 && dy == 0 {
continue
}
x := i + dx
y := j + dy
if x < 0 || x >= m || y < 0 || y >= n {
continue
}
if board[x][y] == 1 || board[x][y] == 2 {
live++
}
}
}
if board[i][j] == 1 && (live < 2 || live > 3) {
board[i][j] = 2
} else if board[i][j] == 0 && live == 3 {
board[i][j] = 3
}
}
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if board[i][j] == 2 {
board[i][j] = 0
} else if board[i][j] == 3 {
board[i][j] = 1
}
}
}
}
复杂度分析
- 时间复杂度：$O(m \cdot n)$。凭什么：第一趟遍历 $mn$ 个格子，每格固定枚举 9 个方向偏移（其中 8 个有效），是常数工作量；第二趟再遍历一次做解码映射，同样是 $O(mn)$。八邻域的常数 8 与面板规模无关，所以总量是线性的。
- 空间复杂度：$O(1)$ 额外空间。凭什么：所有中间信息都编码进了
board原有的整型格子里，没有复制面板、没有额外矩阵、没有队列或递归栈；只用了m、n、live、dx、dy等常数个变量。这正是相对「拷贝一份面板」写法的核心优势，也是进阶要求想考的点。
关键点总结
- 凡是「所有元素必须依据同一份快照同时更新」的模拟题，第一反应是拷贝快照，第二反应就该是在原有存储里编码额外状态。判断可行性的依据是「取值域是否有富余空间」——本题值域只有 0/1 而容器是 32 位整数，富余极大。
- 状态编码的设计原则是保证每一维都能被无损读出，并写成显式判据（这里是「旧活 ⟺ 值∈{1,2}」「新活 ⟺ 值∈{1,3}」）。写代码前先把判据写在纸上，统计邻居时直接套用，能避免绝大多数编码类错误。
- 让「不变的情况」沿用原编码、只给「翻转的情况」分配新值，可以把解码简化成一次值映射，也让第一趟里两个「保持不变」的分支彻底消失。少写分支就是少犯错。
- 编码与解码必须是两趟独立遍历。同一趟里既编码又解码会立刻破坏不变量，这是所有原地状态编码题的通用约束。
- 八邻域用
{-1,0,1}的双重循环加一次(0,0)跳过来枚举，比手写两个长度 8 的方向数组更短且不易抄错；四邻域时则相反，显式方向数组更清晰。- 面试视角：这题几乎必被追问进阶。回答顺序建议是：先说拷贝版本证明理解了「同时更新」的语义，再主动提出「值域有富余，可以编码」，给出四值编码及其判据，最后写码。写完后应主动补充另一个进阶——面板无限大时，四值编码失效，要改成只存活细胞坐标的哈希集合，用哈希表统计每个活细胞对其八个邻居的贡献次数，一趟即可算出下一代，复杂度与活细胞数成正比而与面板尺寸无关。
- 面试视角：位运算版本可用低位存旧、次低位存新，写入
board[i][j] |= next << 1，解码board[i][j] >>= 1；但要同步把「旧活」判据改成最低位为 1，不能沿用本文{1,2}的四值判据。
易错点总结
- 统计活邻居时只判
== 1：用例[[0,1,0],[0,0,1],[1,1,1],[0,0,0]]，处理(1,0)时(0,1)已被改成2，活邻居数会算成 2 而不是 3，(1,0)不会复活，结果第 2 行第 1 列错成 0。- 统计活邻居时把
3也算作活：同一用例，处理(1,1)时(1,0)已是3，会把活邻居数算成 6；更致命的是处理(3,2)时(3,1)已是3，活邻居数从 2 变成 3，(3,2)会被错误复活。- 不做编码，直接就地把状态改成 0/1：在样例
[[0,1,0],[0,0,1],[1,1,1],[0,0,0]]中，(0,1)会先由活变死；随后处理(1,0)时少算这个旧活邻居，导致它无法按规则复活。- 在第一趟里就把
2解码成0：用例[[0,1,0],[0,0,1],[1,1,1],[0,0,0]]，(0,1)一旦立刻变成 0，(0,2)和(1,0)统计时都会少算一个活邻居，(1,0)不再复活，答案错。- 邻居枚举忘记跳过
(0,0)：用例[[1,1],[1,1]]，每个活细胞会把自己也计入活邻居，活邻居数从 3 变成 4，四个细胞全部死亡，而正确结果是全部存活。- 越界检查写在数组访问之后：用例
[[1]]，枚举(-1,-1)时先执行board[-1][-1]直接抛越界异常（Go 版 panic）。- 活细胞存活条件写成
live == 2 || live == 3却漏掉「否则改 2」的分支结构：用例[[1,0],[0,0]]，孤立活细胞活邻居数为 0 应当死亡编码成2，若条件分支写反（把存活写成改值、死亡写成不动），解码后会得到活细胞仍为 1，结果错。- 死细胞复活条件写成
live >= 3：用例[[1,1,1],[1,0,1],[1,1,1]]，中心死细胞的活邻居数是 8，>= 3会让它错误复活，而规则要求恰好 3 才复活。- 本文四值编码却照搬位编码的
board[i][j] >>= 1解码：状态2表示旧活新死，右移后会得到 1，恰好与正确新状态相反。本文应把2/3映射为0/1（写% 2也正确）；只有「低位旧、次低位新」的位编码才能统一右移。- 只做了第一趟忘记解码：用例
[[0,1,0],[0,0,1],[1,1,1],[0,0,0]]，返回的面板里含有2和3，而题目要求最终只能是 0/1，直接判错。- 对
board[i][j]做判定时用了解码后的值（如先判board[i][j] == 1 || board[i][j] == 2）：这在本题会把已处理格子的旧活状态也纳入自身判定，但由于(i,j)尚未被本轮改写，它必然是 0 或 1，多余的== 2分支虽不产生错误却暴露了对不变量理解不清，面试中会被追问。- 面板尺寸取成
board.length与board.length（行列混用）：用例[[1,1,1]]（1 行 3 列），把n误取成 1 会漏掉两列，(0,1)和(0,2)完全不被处理，也不会被计入邻居统计。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 73. 矩阵置零 | 中等 | 同样要求原地且不能边算边改，靠首行首列当标记位，是状态编码的另一种形态 |
| 48. 旋转图像 | 中等 | 原地变换但靠四元素轮换而非编码，考察坐标映射的推导 |
| 54. 螺旋矩阵 | 中等 | 纯遍历顺序设计，用四个边界变量收缩，练习矩阵题的边界不变量 |
| 867. 转置矩阵 | 简单 | 非方阵无法原地，用来对照理解「什么时候原地根本不可能」 |
| 498. 对角线遍历 | 中等 | 遍历方向随对角线奇偶翻转，重点在拐弯时的越界分支顺序 |
| 200. 岛屿数量 | 中等 | 同样把原网格当访问标记就地改写，是「用输入值域省掉 visited」的典型 |
| 59. 螺旋矩阵 II | 中等 | 反过来按螺旋顺序填数，考察同一套边界收缩逻辑在构造场景下的复用 |