华为 OD 训练营 · 题解精讲
LeetCode289、生命游戏
LeetCode289、生命游戏 视频地址：
题目描述
根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。 给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律： 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡； 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活； 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡； 如果死细胞周围正好有三个活细胞，则该位置死细胞复活； 下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。
示例 1： GkpWbCRjioeUI9xZIZzceLllnLd.jpg
输入：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]] 示例 2： MFM8b7jOuoHkk0xJSDpcCVRGnQh.jpg
输入：board = [[1,1],[1,0]] 输出：[[1,1],[1,1]]
提示： m == board.length n == board[i].length 1 <= m, n <= 25 board[i][j] 为 0 或 1
题目解析
解题思路
本题要求原地更新面板，但细胞的新状态依赖于旧状态的邻居信息，直接覆盖会丢失原始数据。参考代码使用状态编码技巧，引入两个额外状态 2 和 3，在遍历过程中同时记录当前状态和下一状态，避免额外空间。
- 状态定义：
0（当前死，下一轮死）、1（当前活，下一轮活）、2（当前死，下一轮活）、3（当前活，下一轮死） - 核心思想：第一遍遍历时，根据规则将需要变化的位置标记为
2或3，但保留原始状态信息（因为1和3都代表当前活，0和2都代表当前死）；第二遍遍历将2→1、3→0完成最终转换。
关键步骤
1. 方向数组：定义 dx、dy 表示 8 个邻居的偏移量。 2. 第一遍遍历：
- 对每个格子
(i,j)，统计 8 个邻居中当前为活细胞的数量（判断条件board[x][y] == 1 or board[x][y] == 3，因为3表示当前活但即将死）。 - 根据规则更新：
- 死细胞且恰好 3 个活邻居 → 标记为
2（复活） - 活细胞且邻居数 <2 或 >3 → 标记为
3（死亡） - 其他情况状态不变（保持
0或1）
3. 第二遍遍历：将 2 改为 1，3 改为 0。
示意图（以单个细胞为例）：
当前状态: 0 (死) 邻居活数=3 → 标记为 2
当前状态: 1 (活) 邻居活数=1 → 标记为 3复杂度分析
- 时间复杂度：
O(m×n)，每个格子遍历两次，每次检查 8 个邻居，总操作次数约为16×m×n。 - 空间复杂度：
O(1)，仅使用常数个额外变量，完全原地修改。
参考代码
class Solution(object):
def gameOfLife(self, board):
# 8个方向数组
dx = [-1, 0, 1, -1, 1, -1, 0, 1]
dy = [-1, -1, -1, 0, 0, 1, 1, 1]
# 通过多设置两个状态，来实现原地修改的目的
# 4个不同数字对应4中不同种状态：
# 0: 当前死；1：当前活；2：当前死，下一步活；3：当前活，下一步死
# 遍历每一个cell
for i in range(len(board)):
for j in range(len(board[0])):
# 对于当前位置(i, j)周围的活细胞数目变量，初始化为0
neighborLive = 0
# 考虑当前位置的八个方向的近邻点(x, y)
for k in range(8):
x = i + dx[k]
y = j + dy[k]
# 近邻点(x, y)尚未越界，且是活细胞，更新近邻活细胞数目neighborLive
if ((x >= 0) and (x <= len(board)-1) and (y >= 0) and (y <= len(board[0])-1)):
if (board[x][y] == 1 or board[x][y] == 3):
neighborLive += 1
# 根据当前位置细胞状态和近邻活细胞数目，更新当前位置的下一个状态
if (board[i][j] == 0) and (neighborLive == 3):
board[i][j] = 2 # 死细胞复活，0改2
elif (board[i][j] == 1) and ((neighborLive < 2) or (neighborLive > 3)):
board[i][j] = 3 # 活细胞死亡，1改3
# 再次遍历每一个cell，将2改成1（活细胞），将3改成0（死细胞）
for i in range(len(board)):
for j in range(len(board[0])):
if (board[i][j] == 2): board[i][j] = 1
elif (board[i][j] == 3): board[i][j] = 0
四、复杂度分析
时间复杂度：O(nm)。
空间复杂度：O(1)。