LeetCode 289. 生命游戏
题目描述
题意分析
根据当前面板计算下一代，并直接修改原数组。每格查看水平、垂直和对角线方向的八个邻居：原来存活的细胞只有在活邻居数为 $2$ 或 $3$ 时继续存活；原来死亡的细胞只有在活邻居数恰为 $3$ 时复活。
所有格子必须依据同一代状态同时变化。逐格计算时，前面已经写出的新状态不能影响后面格子的判断，这正是原地更新需要解决的问题。
解法：原地状态编码
核心思路
[!blue]
一个格子需要同时表达旧状态和下一代状态，但不必复制整张面板。保留未发生变化的 $0$、$1$，再引入两个临时值：$2$ 表示“原来活、下一代死”，$3$ 表示“原来死、下一代活”。于是四种旧新组合都能在原格子中区分。
第一遍遍历只标记状态变化。统计某个邻居的旧状态时，值为 $1$ 或 $2$ 都说明它原来存活；$0$ 或 $3$ 都说明它原来死亡。因此不论邻居是否已经处理过，计数使用的始终是同一代信息。
当前格子只会在轮到自己时被写入一次，所以判断它自身时仍是原始的 $0$ 或 $1$：若原来为 $1$ 且活邻居少于 $2$ 或多于 $3$，写成 $2$；若原来为 $0$ 且活邻居恰有 $3$ 个，写成 $3$；其余情况保持原值。方向偏移由
-1、0、1两两组合，排除(0, 0)后恰好是八个方向，越界位置直接略过。等整张面板完成判断，再开始第二遍：把 $2$ 解码为 $0$，把 $3$ 解码为 $1$，未变化的值保持不动。此时已经没有格子需要读取旧状态，可以安全丢弃旧信息，得到同时更新后的面板。
无限面板的进阶：若活细胞数量有限且分布稀疏，可以用坐标集合只保存活细胞，坐标不受原数组边界限制。遍历每个活细胞，为它的八个邻居累计活邻居数；只有这些邻居位置可能存活或复活。用旧集合判断原状态，再把“邻居数为 $3$”或“邻居数为 $2$ 且原来存活”的位置放入新集合，最后整体替换。没有活邻居的旧活细胞自然不进入新集合，边界外可能诞生的新细胞也不会被截掉。若当前有
p个活细胞，候选位置至多为8p，一次更新的期望时间和额外空间都是 $O(p)$。
解题步骤
- 遍历每个格子，检查八个方向，跳过自身与越界位置。
- 按邻居值为 1 或 2 统计旧活细胞数。
- 活转死标为 2，死转活标为 3，其他保持。
- 第二次遍历统一解码。
代码实现
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;
}
}
}
}
}
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(mn)$，每格检查固定八个邻居，再统一解码。
- 空间复杂度：$O(1)$，新旧信息保存在原面板中。
关键点总结
[!green]
- 所有判断读取同一代旧状态。
- 只有发生变化的格子需要额外编码。
- 编码与解码分开，直到整轮结束才丢弃旧信息。
易错点总结
[!yellow]
- 邻居只认值一：漏掉已经标为活转死的旧活细胞。
- 把值三也算作旧活：提前计入本轮刚复活的细胞。
- 统计时包含自身：邻居数多一，规则被改变。
- 第一遍就解码：后续格子无法恢复正确旧状态。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 73. 矩阵置零 | 中等 | 同样需要避免新写入的状态影响后续读取，原地编码或分两阶段处理可保存旧信息。 |