【Python 算法零底子 2.模拟 ④ 基于矩阵】

目录
  基于矩阵
  Ⅰ、 2120. 执行所有后缀指令
  思路与算法
  ① 初始化结果列表
  ② 方向映射
  ③ 遍历每个起始位置
  ④ 记载结果
  Ⅱ、1252. 奇数值单元格的数目
  思路与算法
  ① 初始化矩阵
  ② 处理每个操作
  ③ 统计奇数元素
  Ⅲ、 832. 翻转图像
  思路与算法
  ① 水平翻转图像
  ② 像素值取反
  ③ 返回结果
  Ⅳ、657. 呆板人能否返回原点
  思路与算法
  ① 定义方向映射
  ② 初始化位置
  ③ 遍历移动指令
  ④ 判断是否回到原点
  Ⅴ、 289. 生命游戏
  思路与算法
  ① 获取矩阵尺寸
  ② 创建原矩阵的副本
  ③ 定义八个方向的偏移量
  ④ 遍历每个细胞
  ⑤ 计算活细胞邻人数目
  ⑥ 应用生命规则
  ⑦ 直接修改原矩阵
  Ⅵ、59. 螺旋矩阵 II
  思路与算法
  ① 初始化矩阵
  ② 初始位置与方向
  ③ 填充数字
  ④ 方向切换逻辑
  ⑤ 界限查抄：
  ⑤ 终止条件：
  Ⅶ、885. 螺旋矩阵 III
  思路与算法
  ① 方向控制
  ② 步长规律
  ③ 界限查抄
  

---

  相由心生，所见都是你，统统都是自己的相
                                                                 —— 25.5.14
  基于矩阵

        利用矩阵的数据布局，根据题目要求，实现算法，如：
Ⅰ、 2120. 执行所有后缀指令

   现有一个 n x n 大小的网格，左上角单元格坐标 (0, 0) ，右下角单元格坐标 (n - 1, n - 1) 。给你整数 n 和一个整数数组 startPos ，此中 startPos = [startrow, startcol] 表现呆板人最开始在坐标为 (startrow, startcol) 的单元格上。
  另给你一个长度为 m 、下标从 0 开始的字符串 s ，此中 s 是对呆板人的第 i 条指令：'L'（向左移动），'R'（向右移动），'U'（向上移动）和 'D'（向下移动）。
  呆板人可以从 s 中的任一第 i 条指令开始执行。它将会逐条执行指令直到 s 的末尾，但在满意下述条件之一时，呆板人将会制止：
  

• 下一条指令将会导致呆板人移动到网格外。
  
• 没有指令可以执行。
  

  返回一个长度为 m 的数组 answer ，此中 answer 是呆板人从第 i 条指令 开始 ，可以执行的 指令数目 。
  
  示例 1：
  
  

1. <strong>输入：</strong>n = 3, startPos = [0,1], s = "RRDDLU"
2. <strong>输出：</strong>[1,5,4,3,1,0]
3. <strong>解释：</strong>机器人从 startPos 出发，并从第 i 条指令开始执行：
4. - 0: "<em><strong>R</strong></em>RDDLU" 在移动到网格外之前，只能执行一条 "R" 指令。
5. - 1:  "<em><strong>RDDLU</strong></em>" 可以执行全部五条指令，机器人仍在网格内，最终到达 (0, 0) 。
6. - 2:   "<em><strong>DDLU</strong></em>" 可以执行全部四条指令，机器人仍在网格内，最终到达 (0, 0) 。
7. - 3:    "<em><strong>DLU</strong></em>" 可以执行全部三条指令，机器人仍在网格内，最终到达 (0, 0) 。
8. - 4:     "<em><strong>L</strong></em>U" 在移动到网格外之前，只能执行一条 "L" 指令。
9. - 5:      "U" 如果向上移动，将会移动到网格外。

复制代码

示例 2：
  
  

1. <strong>输入：</strong>n = 2, startPos = [1,1], s = "LURD"
2. <strong>输出：</strong>[4,1,0,0]
3. <strong>解释：</strong>
4. - 0: "<em><strong>LURD</strong></em>"
5. - 1:  "<em><strong>U</strong></em>RD"
6. - 2:   "RD"
7. - 3:    "D"

复制代码

示例 3：
  
  

1. <strong>输入：</strong>n = 1, startPos = [0,0], s = "LRUD"
2. <strong>输出：</strong>[0,0,0,0]
3. <strong>解释：</strong>无论机器人从哪条指令开始执行，都会移动到网格外。

复制代码

提示：
  

• m == s.length
  
• 1 <= n, m <= 500
  
• startPos.length == 2
  
• 0 <= startrow, startcol < n
  
• s 由 'L'、'R'、'U' 和 'D' 构成
  

  思路与算法

① 初始化结果列表

用于存储每个起始位置对应的可执行指令数。
② 方向映射

通过字典将方向字符映射为坐标变化量，方便后续移动计算。
③ 遍历每个起始位置

对于每个起始位置 i，重置临时计数器 tmp 和呆板人的初始位置 (x, y)。从 s 开始逐个执行指令：根据指令更新呆板人位置。查抄新位置是否越界。若越界，立即终止循环；否则计数器加一。
④ 记载结果

将每个起始位置对应的计数器值存入结果列表。

1. class Solution:
2.     def executeInstructions(self, n: int, startPos: List[int], s: str) -> List[int]:
3.         res = []
4.         # 定义方向矩阵
5.         dir = {"L" : (0, -1), "R" : (0, 1), "U" : (-1, 0), "D" : (1, 0)}
6.         for i in range(len(s)):
7.             tmp = 0
8.             x, y = startPos[0], startPos[1]
9.             for j in s[i:]:
10.                 x = x + dir[j][0]
11.                 y = y + dir[j][1]
12.                 if x < 0 or y < 0 or x >= n or y >= n:
13.                     break
14.                 else:
15.                     tmp += 1
16.             res.append(tmp)
17.         return res

复制代码

---

Ⅱ、1252. 奇数值单元格的数目

   给你一个 m x n 的矩阵，最开始的时候，每个单元格中的值都是 0。
  另有一个二维索引数组 indices，indices = [ri, ci] 指向矩阵中的某个位置，此中 ri 和 ci 分别表现指定的行和列（从 0 开始编号）。
  对 indices 所指向的每个位置，应同时执行下述增量操作：
  

• ri 行上的所有单元格，加 1 。
  
• ci 列上的所有单元格，加 1 。
  

  给你 m、n 和 indices 。请你在执行完所有 indices 指定的增量操作后，返回矩阵中 奇数值单元格 的数目。
  
  示例 1：
  
  

1. <strong>输入：</strong>m = 2, n = 3, indices = [[0,1],[1,1]]
2. <strong>输出：</strong>6
3. <strong>解释：</strong>最开始的矩阵是 [[0,0,0],[0,0,0]]。
4. 第一次增量操作后得到 [[1,2,1],[0,1,0]]。
5. 最后的矩阵是 [[1,3,1],[1,3,1]]，里面有 6 个奇数。

复制代码

示例 2：
  
  

1. <strong>输入：</strong>m = 2, n = 2, indices = [[1,1],[0,0]]
2. <strong>输出：</strong>0
3. <strong>解释：</strong>最后的矩阵是 [[2,2],[2,2]]，里面没有奇数。

复制代码

提示：
  

• 1 <= m, n <= 50
  
• 1 <= indices.length <= 100
  
• 0 <= ri < m
  
• 0 <= ci < n
  

  思路与算法

① 初始化矩阵

创建一个 m 行 n 列的矩阵 matrix，所有元素初始化为 0。
② 处理每个操作

遍历 indices 中的每个操作 (x, y)，此中 x 表现行索引，y 表现列索引。
③ 统计奇数元素

遍历整个矩阵，统计值为奇数的元素个数。 

1. class Solution:
2.     def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
3.         matrix = [[0] * n for _ in range(m)]  # 正确初始化m行n列的矩阵
4.         for x, y in indices:
5.             # 处理行x的所有列元素
6.             for col in range(n):
7.                 matrix[x][col] += 1
8.             # 处理列y的所有行元素
9.             for row in range(m):
10.                 matrix[row][y] += 1
11.         # 统计奇数数量
12.         count = 0
13.         for row in matrix:
14.             for num in row:
15.                 if num % 2 != 0:
16.                     count += 1
17.         return count

复制代码

---

Ⅲ、 832. 翻转图像

   给定一个 n x n 的二进制矩阵 image ，先 水平 翻转图像，然后 反转 图像并返回 结果 。
  水平翻转图片就是将图片的每一行都进行翻转，即逆序。
  

• 例如，水平翻转 [1,1,0] 的结果是 [0,1,1]。
  

  反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。
  

• 例如，反转 [0,1,1] 的结果是 [1,0,0]。
  

  
  示例 1：

1. <strong>输入：</strong>image = [[1,1,0],[1,0,1],[0,0,0]]
2. <strong>输出：</strong>[[1,0,0],[0,1,0],[1,1,1]]
3. <strong>解释：</strong>首先翻转每一行: [[0,1,1],[1,0,1],[0,0,0]]；
4.      然后反转图片: [[1,0,0],[0,1,0],[1,1,1]]

复制代码

示例 2：

1. <strong>输入：</strong>image = [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
2. <strong>输出：</strong>[[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
3. <strong>解释：</strong>首先翻转每一行: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]；
4.      然后反转图片: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

复制代码

提示：
  

• n == image.length
  
• n == image.length
  
• 1 <= n <= 20
  
• images[j] == 0 或 1.
  

  思路与算法

① 水平翻转图像

遍历图像的每一行。对于每一行，使用切片操作 [::-1] 将该行元素反转，实现水平翻转。
② 像素值取反

再次遍历图像的每一行。对于每一行中的每个像素，查抄其值。如果像素值为 0，则将其改为 1；如果像素值为 1，则将其改为 0，实现像素值取反。
③ 返回结果

颠末上述两步操作后，返回处理后的图像矩阵。

1. class Solution:
2.     def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
3.         n = len(image[0])
4.         for i in range(n):
5.             image[i] = image[i][::-1]
6.         for i in range(n):
7.             for j in range(n):
8.                 if image[i][j] == 0:
9.                     image[i][j] = 1
10.                 else:
11.                     image[i][j] = 0
12.         return image

复制代码

---

Ⅳ、657. 呆板人能否返回原点

   在二维平面上，有一个呆板人从原点 (0, 0) 开始。给出它的移动顺序，判断这个呆板人在完成移动后是否在 (0, 0) 处结束。
  移动顺序由字符串 moves 表现。字符 move 表现其第 i 次移动。呆板人的有效动作有 R（右），L（左），U（上）和 D（下）。
  如果呆板人在完成所有动作后返回原点，则返回 true。否则，返回 false。
  注意：呆板人“面朝”的方向无关紧要。 “R” 将始终使呆板人向右移动一次，“L” 将始终向左移动等。别的，假设每次移动呆板人的移动幅度相同。
  
  示例 1:

1. <strong>输入:</strong> moves = "UD"
2. <strong>输出:</strong> true
3. <strong>解释：</strong>机器人向上移动一次，然后向下移动一次。所有动作都具有相同的幅度，因此它最终回到它开始的原点。因此，我们返回 true。

复制代码

示例 2:

1. <strong>输入:</strong> moves = "LL"
2. <strong>输出:</strong> false
3. <strong>解释：</strong>机器人向左移动两次。它最终位于原点的左侧，距原点有两次 “移动” 的距离。我们返回 false，因为它在移动结束时没有返回原点。

复制代码

提示:
  

• 1 <= moves.length <= 2 * 104
  
• moves 只包含字符 'U', 'D', 'L' 和 'R'
  

  思路与算法

① 定义方向映射

创建字典 des，将每个移动指令（R, L, U, D）映射为对应的坐标变化量：R（右）：(1, 0) L（左）：(-1, 0) U（上）：(0, 1) D（下）：(0, -1)
② 初始化位置

将呆板人的初始坐标 (x, y) 设为 (0, 0)。
③ 遍历移动指令

对于每个指令 i（如 R, L 等）：从字典 des 中获取对应的坐标变化量 (dx, dy)。更新当前坐标：x += dx, y += dy。
④ 判断是否回到原点

遍历完所有指令后，查抄终极坐标 (x, y) 是否为 (0, 0)。如果是，则返回 True；否则返回 False。

1. class Solution:
2.     def judgeCircle(self, moves: str) -> bool:
3.         des = {"R" : (1, 0), "L" : (-1, 0), "U" : (0, 1), "D" : (0, -1)}
4.         x, y = 0, 0
5.         for i in moves:
6.             x += des[i][0]
7.             y += des[i][1]
8.         return x == y == 0

复制代码

---

Ⅴ、 289. 生命游戏

   根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞主动机。
  给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
  

• 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
  
• 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
  
• 如果活细胞周围八个位置有高出三个活细胞，则该位置活细胞死亡；
  
• 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
  

  下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，此中细胞的出生和死亡是 同时 发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。
  给定当前 board 的状态，更新 board 到下一个状态。
  注意 你不需要返回任何东西。
  
  示例 1：
  

1. <strong>输入：</strong>board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
2. <strong>输出：</strong>[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

复制代码

示例 2：
  

1. <strong>输入：</strong>board = [[1,1],[1,0]]
2. <strong>输出：</strong>[[1,1],[1,1]]

复制代码

  提示：
  

• m == board.length
  
• n == board.length
  
• 1 <= m, n <= 25
  
• board[j] 为 0 或 1
  

  思路与算法

① 获取矩阵尺寸

确定二维数组的大小，用于后续遍历和界限查抄。
② 创建原矩阵的副本

复制原始矩阵 board 的所有值到 copy_board，确保在更新过程中使用的是原始状态，避免影响后续细胞的计算。
③ 定义八个方向的偏移量

每个元组 (dx, dy) 表现相对于当前细胞的一个方向（上、下、左、右、对角），用于遍历周围的 8 个邻人。
④ 遍历每个细胞

对矩阵中的每个细胞 (i, j) 进行处理
⑤ 计算活细胞邻人数目

对于每个细胞 (i, j)，遍历其 8 个邻人：
        计算邻人坐标 (x, y) = (i+dx, j+dy)。
        查抄坐标是否越界（0 ≤ x < m 且 0 ≤ y < n）。
        若邻人在有效范围内且为活细胞（值为 1），则计数器 live_neighbors 加 1。
⑥ 应用生命规则

规则 1：活细胞周围的活邻人少于 2 个 → 死亡（孤独）。
规则 2：活细胞周围的活邻人为 2 或 3 个 → 存活（保持现状）。
规则 3：活细胞周围的活邻人多于 3 个 → 死亡（拥挤）。
规则 4：死细胞周围的活邻人恰好为 3 个 → 复活（繁殖）。
⑦ 直接修改原矩阵

所有更新直接应用到原始矩阵 board 中，符合题目 “不返回任何东西” 的要求。

1. class Solution:
2.     def gameOfLife(self, board: List[List[int]]) -> None:
3.         """
4.         Do not return anything, modify board in-place instead.
5.         """
6.         m = len(board)      # 行数
7.         n = len(board[0])   # 列数
8.         
9.         # 创建一个复制数组，用于存储原始状态
10.         copy_board = [[board[i][j] for j in range(n)] for i in range(m)]
11.         
12.         # 定义8个方向的偏移量
13.         directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
14.         
15.         # 遍历每个细胞
16.         for i in range(m):
17.             for j in range(n):
18.                 # 计算周围活细胞的数量
19.                 live_neighbors = 0
20.                 for dx, dy in directions:
21.                     x = i + dx
22.                     y = j + dy
23.                     # 检查邻居是否在有效范围内并且是活细胞
24.                     if 0 <= x < m and 0 <= y < n and copy_board[x][y] == 1:
25.                         live_neighbors += 1
26.                
27.                 # 应用生命游戏规则
28.                 if copy_board[i][j] == 1:
29.                     if live_neighbors < 2 or live_neighbors > 3:
30.                         board[i][j] = 0
31.                 else:
32.                     if live_neighbors == 3:
33.                         board[i][j] = 1

复制代码

---

Ⅵ、59. 螺旋矩阵 II

   给你一个正整数 n ，天生一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋分列的 n x n 正方形矩阵 matrix 。
  
  示例 1：
  

1. <strong>输入：</strong>n = 3
2. <strong>输出：</strong>[[1,2,3],[8,9,4],[7,6,5]]

复制代码

示例 2：

1. <strong>输入：</strong>n = 1
2. <strong>输出：</strong>[[1]]

复制代码

提示：
  

• 1 <= n <= 20
  

  思路与算法

① 初始化矩阵

创建一个 n×n 的零矩阵 ans。
② 初始位置与方向

从坐标 (0, 0) 开始，初始方向为右（di = 0）。
③ 填充数字

按当前方向尝试进步到下一个位置 (x, y)。
④ 方向切换逻辑

算法通过索引 di 选择当前方向：
初始方向：di = 0（向右）
转向条件：遇到界限或已填充的位置时
转向操作：di = (di + 1) % 4 → 按 右→下→左→上 循环切换
⑤ 界限查抄：

若新位置超出矩阵范围或已被填充，则右转（di = (di + 1) % 4）。更新当前位置 (i, j) 并填充数字。
⑤ 终止条件：

填充完所有 n² 个数字后结束循环。

1. class Solution:
2.     def generateMatrix(self, n: int) -> List[List[int]]:
3.         DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右下左上
4.         ans = [[0] * n for _ in range(n)]
5.         i = j = di = 0
6.         for val in range(1, n * n + 1):  # 要填入的数
7.             ans[i][j] = val
8.             x, y = i + DIRS[di][0], j + DIRS[di][1]  # 下一步的位置
9.             # 如果 (x, y) 出界或者已经填入数字
10.             if x < 0 or x >= n or y < 0 or y >= n or ans[x][y]:
11.                 di = (di + 1) % 4  # 右转 90°
12.             i += DIRS[di][0]
13.             j += DIRS[di][1]  # 走一步
14.         return ans

复制代码

---

Ⅶ、885. 螺旋矩阵 III

   在 rows x cols 的网格上，你从单元格 (rStart, cStart) 面朝东面开始。网格的西北角位于第一行第一列，网格的东南角位于末了一行末了一列。
  你需要以顺时针按螺旋状行走，访问此网格中的每个位置。每当移动到网格的界限之外时，需要继续在网格之生手走（但稍后大概会返回到网格界限）。
  终极，我们到过网格的所有 rows x cols 个空间。
  按照访问顺序返回表现网格位置的坐标列表。
  
  示例 1：
  

1. <strong>输入：</strong>rows = 1, cols = 4, rStart = 0, cStart = 0
2. <strong>输出：</strong>[[0,0],[0,1],[0,2],[0,3]]

复制代码

示例 2：
  

1. <strong>输入：</strong>rows = 5, cols = 6, rStart = 1, cStart = 4
2. <strong>输出：</strong>[[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

复制代码

提示：
  

• 1 <= rows, cols <= 100
  
• 0 <= rStart < rows
  
• 0 <= cStart < cols
  

  思路与算法

① 方向控制

与螺旋矩阵 I 类似，按右→下→左→上循环切换方向。
② 步长规律

每次转向后，步长递增 1（第一次向右走 1 步，下一次向下走 1 步，再向左走 2 步，向上走 2 步，依此类推）。
③ 界限查抄

每走一步，查抄坐标是否在矩阵内，若是则记载。

1. class Solution:
2.     def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:
3.         DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右、下、左、上
4.         res = [[rStart, cStart]]  # 起始点
5.         i, j = rStart, cStart
6.         steps = 0  # 当前方向的步数
7.         di = 0     # 方向索引
8.         
9.         while len(res) < rows * cols:
10.             # 每次转向后，步数递增1（偶数次转向时增加）
11.             if di % 2 == 0:
12.                 steps += 1
13.             
14.             # 沿当前方向走steps步
15.             for _ in range(steps):
16.                 i += DIRS[di][0]
17.                 j += DIRS[di][1]
18.                
19.                 # 检查是否在矩阵内
20.                 if 0 <= i < rows and 0 <= j < cols:
21.                     res.append([i, j])
22.             
23.             # 转向
24.             di = (di + 1) % 4
25.         
26.         return res

复制代码