生命游戏 图解题解
这道题到底在问什么
- 输入
- 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]]
最优解：一步一步想明白
- 3记住两个判定：活细胞要 2~3 个活邻居才活，死细胞要恰好 3 个活邻居才复活。靠编码 2/3 区分「将变」的格子，先全判完再统一落地，保证「同时」。
- 4这是第 0 代的网格：绿色是活细胞(1)，灰色是死细胞(0)。我们要逐格判定它下一代的命运，原地把结果写回来。
- 5轮到格 (0,0)，它现在是死细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 1 个活邻居。
- 6判定：死细胞只有 1 个活邻居(不等于 3)，不满足复活条件，仍是 0，不用改。
- 7轮到格 (0,1)，它现在是活细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 1 个活邻居。
- 8判定：活细胞遇到 1 个活邻居，邻居太少(<2)会孤独而死。先记成编码 3(橙色=活将变死)，但数后面格子时它仍按「原来是活」算。
- 9轮到格 (0,2)，它现在是死细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 2 个活邻居。
- 10判定：死细胞只有 2 个活邻居(不等于 3)，不满足复活条件，仍是 0，不用改。
- 11轮到格 (1,0)，它现在是死细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 3 个活邻居。
- 12判定：死细胞周围恰好 3 个活邻居，按规则复活。先记成编码 2(绿色=死将变活)，但数后面格子时它仍按「原来是死」算。
- 13轮到格 (1,1)，它现在是死细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 5 个活邻居。
- 14判定：死细胞只有 5 个活邻居(不等于 3)，不满足复活条件，仍是 0，不用改。
- 15轮到格 (1,2)，它现在是活细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 3 个活邻居。
- 16判定：活细胞有 3 个活邻居(2 或 3 个)，正好能活下去，保持为 1，不用改。
- 17轮到格 (2,0)，它现在是活细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 1 个活邻居。
- 18判定：活细胞遇到 1 个活邻居，邻居太少(<2)会孤独而死。先记成编码 3(橙色=活将变死)，但数后面格子时它仍按「原来是活」算。
- 19轮到格 (2,1)，它现在是活细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 3 个活邻居。
- 20判定：活细胞有 3 个活邻居(2 或 3 个)，正好能活下去，保持为 1，不用改。
- 21轮到格 (2,2)，它现在是活细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 2 个活邻居。
- 22判定：活细胞有 2 个活邻居(2 或 3 个)，正好能活下去，保持为 1，不用改。
- 23轮到格 (3,0)，它现在是死细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 2 个活邻居。
- 24判定：死细胞只有 2 个活邻居(不等于 3)，不满足复活条件，仍是 0，不用改。
- 25轮到格 (3,1)，它现在是死细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 3 个活邻居。
- 26判定：死细胞周围恰好 3 个活邻居，按规则复活。先记成编码 2(绿色=死将变活)，但数后面格子时它仍按「原来是死」算。
- 27轮到格 (3,2)，它现在是死细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 2 个活邻居。
- 28判定：死细胞只有 2 个活邻居(不等于 3)，不满足复活条件，仍是 0，不用改。
- 29所有格子判完，最后一趟统一落地：把记成 2 的(死→活)写成 1，把记成 3 的(活→死)写成 0。这就是下一代的网格。
- 30下一代诞生：board 已被原地改成 [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]，没有额外开一张新网格。
⚠️ 容易写错的地方
✗ 错：边算边改，直接把新值写回原格
✓ 对：先用 2/3 编码记中间态，数邻居时只认原位
若直接改，后面格子数邻居会数到已经更新的新值，破坏「同代同时更新」
✗ 错：数邻居时把编码 2/3 当成新状态来判
✓ 对：判邻居只看最低位(&1)，即「原来是不是活」
2 表示原来死(将活)、3 表示原来活(将死)，最低位才是这一代的真实状态
✗ 错：忘了最后统一落地那一趟
✓ 对：全部判完再把 2→1、3→0(整体右移一位)
中间值 2/3 不是合法的 0/1，必须收尾把每格还原成下一代的真实值
完整代码（Python / C++ / Java）
Python
def gameOfLife(board):
m, n = len(board), len(board[0])
for i in range(m):
for j in range(n):
live = 0 # 数活邻居(只认原位)
for di in (-1, 0, 1):
for dj in (-1, 0, 1):
if di == 0 and dj == 0: continue
x, y = i + di, j + dj
if 0 <= x < m and 0 <= y < n and board[x][y] & 1:
live += 1
if board[i][j] & 1: # 当前活
if live in (2, 3): board[i][j] |= 2 # 留活
elif live == 3: board[i][j] |= 2 # 复活
for i in range(m):
for j in range(n):
board[i][j] >>= 1 # 第2位即下一代C++
void gameOfLife(vector<vector<int>>& b){
int m=b.size(), n=b[0].size();
for(int i=0;i<m;i++)for(int j=0;j<n;j++){
int live=0;
for(int di=-1;di<=1;di++)for(int dj=-1;dj<=1;dj++){
if(!di&&!dj) continue;
int x=i+di,y=j+dj;
if(x>=0&&x<m&&y>=0&&y<n&&(b[x][y]&1)) live++;
}
if((b[i][j]&1)&&(live==2||live==3)) b[i][j]|=2;
if(!(b[i][j]&1)&&live==3) b[i][j]|=2;
}
for(auto&row:b)for(int&v:row) v>>=1;
}Java
public void gameOfLife(int[][] b){
int m=b.length, n=b[0].length;
for(int i=0;i<m;i++)for(int j=0;j<n;j++){
int live=0;
for(int di=-1;di<=1;di++)for(int dj=-1;dj<=1;dj++){
if(di==0&&dj==0) continue;
int x=i+di,y=j+dj;
if(x>=0&&x<m&&y>=0&&y<n&&(b[x][y]&1)==1) live++;
}
if((b[i][j]&1)==1&&(live==2||live==3)) b[i][j]|=2;
if((b[i][j]&1)==0&&live==3) b[i][j]|=2;
}
for(int i=0;i<m;i++)for(int j=0;j<n;j++) b[i][j]>>=1;
}复杂度
时间
O(m·n)
每个格子访问一次，数它固定 8 个邻居是常数时间
空间
O(1)
用编码把新旧两代塞进同一格的两个二进制位，不开额外网格
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 生命游戏 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么这道题不能算一格就立刻改一格？+
因为下一代的判定依据是「当前这一代」每个格子的邻居。如果边算边改，后扫到的格子在数邻居时会读到前面已经改过的新值，相当于混用了两代的状态，结果就错了。
编码 2 和 3 分别是什么含义？怎么落地？+
2 = 这一代死、下一代活(born)；3 = 这一代活、下一代死(dying)。数邻居时只看最低位(&1，即原状态)；全判完后把 2→1、3→0，工程上就是每格右移一位(>>=1)，第 2 位的下一代落到第 1 位。
如果网格是无限大该怎么办？+
原地编码法只适合有限网格。无限网格通常改用哈希集合只存活细胞坐标，遍历所有活细胞及其邻居、统计候选格的活邻居数，避免遍历无边界的空白区域。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 生命游戏 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。