题目描述
思路解析动画文字版
记住两个判定:活细胞要 2~3 个活邻居才活,死细胞要恰好 3 个活邻居才复活。靠编码 2/3 区分「将变」的格子,先全判完再统一落地,保证「同时」。
这是第 0 代的网格:绿色是活细胞(1),灰色是死细胞(0)。我们要逐格判定它下一代的命运,原地把结果写回来。
轮到格 (0,0),它现在是死细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 1 个活邻居。
判定:死细胞只有 1 个活邻居(不等于 3),不满足复活条件,仍是 0,不用改。
轮到格 (0,1),它现在是活细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 1 个活邻居。
判定:活细胞遇到 1 个活邻居,邻居太少(<2)会孤独而死。先记成编码 3(橙色=活将变死),但数后面格子时它仍按「原来是活」算。
轮到格 (0,2),它现在是死细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 2 个活邻居。
判定:死细胞只有 2 个活邻居(不等于 3),不满足复活条件,仍是 0,不用改。
轮到格 (1,0),它现在是死细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 3 个活邻居。
判定:死细胞周围恰好 3 个活邻居,按规则复活。先记成编码 2(绿色=死将变活),但数后面格子时它仍按「原来是死」算。
轮到格 (1,1),它现在是死细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 5 个活邻居。
判定:死细胞只有 5 个活邻居(不等于 3),不满足复活条件,仍是 0,不用改。
轮到格 (1,2),它现在是活细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 3 个活邻居。
判定:活细胞有 3 个活邻居(2 或 3 个),正好能活下去,保持为 1,不用改。
轮到格 (2,0),它现在是活细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 1 个活邻居。
判定:活细胞遇到 1 个活邻居,邻居太少(<2)会孤独而死。先记成编码 3(橙色=活将变死),但数后面格子时它仍按「原来是活」算。
轮到格 (2,1),它现在是活细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 3 个活邻居。
判定:活细胞有 3 个活邻居(2 或 3 个),正好能活下去,保持为 1,不用改。
轮到格 (2,2),它现在是活细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 2 个活邻居。
判定:活细胞有 2 个活邻居(2 或 3 个),正好能活下去,保持为 1,不用改。
轮到格 (3,0),它现在是死细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 2 个活邻居。
判定:死细胞只有 2 个活邻居(不等于 3),不满足复活条件,仍是 0,不用改。
轮到格 (3,1),它现在是死细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 3 个活邻居。
判定:死细胞周围恰好 3 个活邻居,按规则复活。先记成编码 2(绿色=死将变活),但数后面格子时它仍按「原来是死」算。
轮到格 (3,2),它现在是死细胞。先数它周围 8 格里有几个「原来就活」的——这一格有 2 个活邻居。
判定:死细胞只有 2 个活邻居(不等于 3),不满足复活条件,仍是 0,不用改。
所有格子判完,最后一趟统一落地:把记成 2 的(死→活)写成 1,把记成 3 的(活→死)写成 0。这就是下一代的网格。
下一代诞生:board 已被原地改成 [[0,0,0],[1,0,1],[0,1,1],[0,1,0]],没有额外开一张新网格。
三个高频追问:为什么要同时更新、编码 2/3 的含义与落地、以及无限网格的进阶解法。
参考代码
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位即下一代复杂度
- 时间:O(m·n),每个格子访问一次,数它固定 8 个邻居是常数时间
- 空间:O(1),用编码把新旧两代塞进同一格的两个二进制位,不开额外网格
易错点
面试追问把动画讲成自己的话
追问为什么这道题不能算一格就立刻改一格?
追问编码 2 和 3 分别是什么含义?怎么落地?
追问如果网格是无限大该怎么办?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
对角线遍历
LeetCode 498 · 中等 · 沿着 矩阵模拟套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题