「亚麻」289 ～ Game of Life
IPFS
基本信息
- 题号：289
- 题厂：亚麻
- 难度系数：中
一个 m * n 的矩阵。
左上、上、右上、左、右、左下、下、右下 8 个方位代表邻居。
如果邻居为 1，说明是活邻居，如果邻居为 0，说明是死邻居。
如果 8 个邻居中，活邻居数量少于 2， 那么格子因为人口过少，死了……
如果 8 个邻居中，活邻居数量鉴于 2 ～ 3 之间，那么可以持续延续该格子人口……
如果 8 个邻居中，活邻居数量大于 3，格子因为人口过剩，死了……
如果 8 个邻居中，活邻居数量刚好为 3，格子可以获得重生……
根据以上游戏规则，计算一下棋盘下一代人口分布……
例如 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]]
解题思路
- 很明显，首先我们需要遍历矩阵计算一下每个格子对应的活邻居数量。
- 有了活邻居有效数据后，在根据题目规则，决定每个格子的死活（0 或者 1）
题目存在一个比较迷惑的陷阱，「如果 8 个邻居中，活邻居数量鉴于 2 ～ 3 之间，那么可以持续延续该格子人口」。这里的延续人口，就是延续当前格子的数据。
如果格子有 2 个邻居，格子自己为 0，那格子继续为 0；
如果格子有 3 个邻居，格子自己为 1，那格子继续为 1；
但是当格子有 3 个邻居时，无论格子目前是死是活，都自动获得重生……
为了简化以上条件，我们可以理解为：
- 如果 8 个邻居中，活邻居数量少于 2， 无论格子是 0 还是 1，都变成 0
- 如果 8 个邻居中，活邻居数量等于 2 ，无论格子是 0 还是 1，维持现状
- 如果 8 个邻居中，活邻居数量大于 3，无论格子是 0 还是 1，都变成 0
- 如果 8 个邻居中，活邻居数量等于 3，无论格子是 0 还是 1，都变成 1
分析完成之后，这道题还是挺简单的……
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
# 创建一下棋盘行列数，方便后续
ROW = len(board)
COL = len(board[0])
# 解此题，我们只需要关注活邻居数量，创建一个棋盘用于计数
live_map = [[0] * COL for i in range(ROW)]
# 按照 8 个方向遍历棋盘，计算 活邻居数量
for r in range(ROW):
for c in range(COL):
directions = [(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1)]
l = 0
for t in directions:
r_neighbor = t[0] + r
c_neighbor = t[1] + c
if (r_neighbor >= 0 and c_neighbor >= 0 and r_neighbor < ROW and c_neighbor < COL):
if board[r_neighbor][c_neighbor] == 1:
l += 1
live_map[r][c] = l
# 根据活邻居数量，判断下一代是死是活……
for r in range(ROW):
for c in range(COL):
if live_map[r][c] < 2:
board[r][c] = 0
elif live_map[r][c] == 3:
board[r][c] = 1
elif live_map[r][c] > 3:
board[r][c] = 0
Constraints
m == board.lengthn == board[i].length1 <= m, n <= 25board[i][j] is 0 or 1.
测试
- n = 1， m = 1 时
- 当整个棋盘全为 1 时
- ……
Big O
时间复杂度：O（m * n）- 空间复杂度： O（m * n）
总结
- 把题目信息分析明白后，本题就是一道在大一编程课 for 循环的基础上加一些花样的题……
- 8 个方向计算邻居数量问题，可以参考各种矩阵问题的方向模板……
到此为止，本题还没有结束，还有 follow up……
- Could you solve it in-place? Remember that the board needs to be updated simultaneously: You cannot update some cells first and then use their updated values to update other cells.
题目要求进阶一下，在不额外占用内存的情况下计算下一代人口死活
解题思路
- 这种限制内存使用 in-place 的题目，我们很容易想到需要特殊 mark 标记（类似曾经遇到过的 #41， 只不过这一次的数据结构由单维数组升级为双重数组了，但原理还是一样的）
- 题目明确告诉我们，格子就两种数据 0 代表死亡邻居，1 代表活跃邻居。当我们更新下一代人口数量时无非就两种情况：「0 变 1」，「1 变 0」。「0 维持 0」「1 维持 1」的情况不需要考虑。
- 借鉴过往经验，这里我们把 「1 变 0」标记为 「-1」，「0 变 1」标记为 「2」。数邻居数量时，计算格子绝对值为 1 的情况，0 或 2 直接略过……
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
ROW, COL = len(board), len(board[0])
# 把算邻居提炼成一个 helper 方法
def count_neighbor(r, c):
l = 0
directions = [(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1)]
for d in directions:
r_nei = r + d[0]
c_nei = c + d[1]
if (r_nei >= 0 and c_nei >= 0 and r_nei < ROW and c_nei < COL):
if abs(board[r_nei][c_nei]) == 1:
l += 1
return l
# 标记 「-1」 1 -> 0
# 标记 「2」 0 -> 1
for r in range(ROW):
for c in range(COL):
l = count_neighbor(r, c)
if l < 2 and board[r][c] != 0:
board[r][c] = -1
elif l == 3 and board[r][c] != 1:
board[r][c] = 2
elif l > 3 and board[r][c] != 0:
board[r][c] = -1
# 计算完成后再标记回去
for r in range(ROW):
for c in range(COL):
if board[r][c] == -1:
board[r][c] = 0
elif board[r][c] == 2:
board[r][c] = 1
总结
- 本题我们复习了矩阵当中涉及的方向坐标查找代码
- 还复习了 in-place 处理中的常见小技巧
喜欢我的作品吗？别忘了给予支持与赞赏，让我知道在创作的路上有你陪伴，一起延续这份热忱！
