LeetCode 289中等矩阵模拟
生命游戏 图解题解
这道题到底在问什么
每个细胞 活(1)/死(0)。下一代：活细胞周围2~3 个活则存活，否则死；死细胞周围恰好 3 个活则复活。所有细胞同时更新。
- board
- 竖条 010/010/010
- 输出
- 横条 000/111/000
最优解：一步一步想明白
- 3最直接的做法：拿一块新画布，照旧网格算出每格的下一代写进去，最后整块拷回。能对，但题目要求原地，多开一整张网格不划算。
- 4转折：与其另开网格，不如把「旧值 + 新命运」一起编码进同一格。用 4 个数：0 死、1 活、2 将生(原死下步活)、3 将死(原活下步死)。数邻居时把 1 和 3 都算「原来是活的」，全标完再统一把 2→1、3→0。这样不用额外网格。
- 5中间列是活的绿色是活细胞，组成一根竖条。接下来逐个判断每个细胞下一代的命运，数邻居时只看「旧状态」。
- 6上下 2 个活邻居盯住中心 (1,1)。数它周围 8 格：只有上方 (0,1)、下方 (2,1) 是活的，共 2 个活邻居。
- 72 个活 → 保持 1(1,1) 本是活的，2 个活邻居落在「2~3 存活」区间 → 它继续活，保持 1，不用打中间态。
- 81 个活邻居 → 将死负例分支：(0,1) 是活的，但活邻居只有下方 (1,1) 这 1 个，少于 2 → 下一步死。标成 将死(3)，但本轮数别人邻居时它仍按「活」算。
- 93 个活邻居 → 将生(1,0) 本是死的，但周围 (0,1)、(1,1)、(2,1) 恰好 3 个活(注意 (0,1) 虽标了将死，仍按「原来活」算) → 复活！标成 将生(2)。
- 10标记完所有格子(1,2) 同样被 3 个活邻居环绕 → 将生；(2,1) 和 (0,1) 一样只有 1 个活邻居 → 将死。四个角始终 0 个活邻居，保持死。全部标记完毕。
- 110 个活邻居 → 不变再看四个角(蓝框)：每个角的 8 邻居里活的(含将死的 3)都凑不满 3 个，死格复活需要恰好 3 个 → 它们保持死(0)，不打任何中间态。负例确认完毕，可以收尾。
- 12将生→活, 将死→死最后再扫一遍：将生(2)→活(1)、将死(3)→死(0)。竖条变成了横条——和示例对上了。这就是「同时更新」靠中间态实现的效果。
- 15需要「同时」更新又想原地的问题，常用「编码中间状态、最后统一还原」这一招。
⚠️ 容易写错的地方
✗ 错：数邻居只数值为 1 的
✓ 对：把 3(将死) 也算「原来是活的」
比如 (1,0) 那格，它三个活邻居里 (0,1) 已被标成 3，若不算它就只数到 2，会漏判复活；本轮它还没真正死，邻居计数必须用旧状态
✗ 错：边遍历边改成 0/1
✓ 对：用 2/3 中间态，最后统一还原
直接改 0/1 会污染后面格子的邻居计数，等于偷偷用了「新值」数邻居，违反同时更新
完整代码（Python）
Python
class Solution:
def gameOfLife(self, board):
m, n = len(board), len(board[0])
dirs = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
for r in range(m):
for c in range(n):
live = 0
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and board[nr][nc] in (1, 3):
live += 1
if board[r][c] == 1 and (live < 2 or live > 3):
board[r][c] = 3
elif board[r][c] == 0 and live == 3:
board[r][c] = 2
for r in range(m):
for c in range(n):
if board[r][c] == 2:
board[r][c] = 1
elif board[r][c] == 3:
board[r][c] = 0套路模板 · 原地标记「编码中间态 + 统一还原」（背下来）
# 编码: 0死 1活 2将生(死→活) 3将死(活→死)
for i, j in 所有格子:
live = sum(board[x][y] in (1,3) for x,y in 8邻居) # 1和3都算"原来活"!
if board[i][j]==1 and not 2<=live<=3: board[i][j]=3 # 活→将死
elif board[i][j]==0 and live==3: board[i][j]=2 # 死→将生
for i, j in 所有格子:
board[i][j] = {2:1, 3:0}.get(board[i][j], board[i][j]) # 统一还原复杂度
时间复杂度
O(m×n)
每格看 8 个邻居是常数，两遍扫描仍是 m×n
空间复杂度
O(1)
原地改，只靠 2/3 两个中间状态，不开新网格
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 生命游戏 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「矩阵模拟」，换最直接的暴力解会差在哪？+
矩阵模拟抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。