力扣hot100题解（python版18-21题）

18、矩阵置零

给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法**。**

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

1
2
3

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

1
2
3

提示：

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -231 <= matrix[i][j] <= 231 - 1

思路解答：

1. 遍历矩阵：首先遍历矩阵，记录出哪些行和列需要被置为0。
2. 更新矩阵：根据标记，将对应行和列的元素置为0。

def setZeroes(self, matrix: list[list[int]]) -> None:

    row = len(matrix)
    col = len(matrix[0])
    row_zero = set()
    col_zero = set()
    for i in range(row):
        for j in range(col):
            if matrix[i][j] == 0:
                row_zero.add(i)
                col_zero.add(j)
    for i in range(row):
        for j in range(col):
            if i in row_zero or j in col_zero:
                matrix[i][j] = 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

19、螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

1
2
3

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

1
2
3

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

思路解答：

1. 模拟螺旋过程：模拟顺时针螺旋的过程，逐层遍历矩阵。
2. 定义边界：定义四个边界，分别表示当前层的上、下、左、右边界。
3. 按顺时针方向遍历：从左到右、从上到下、从右到左、从下到上，依次遍历矩阵。

def spiralOrder(self, matrix: list[list[int]]) -> list[int]:

    if not matrix:
        return []

    rows, cols = len(matrix), len(matrix[0])
    top, bottom, left, right = 0, rows - 1, 0, cols - 1
    result = []

    while True:
        # 从左到右
        for j in range(left, right + 1):
            result.append(matrix[top][j])
        top += 1

        if top > bottom:
            break

        # 从上到下
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1

        if left > right:
            break

        # 从右到左
        for j in range(right, left - 1, -1):
            result.append(matrix[bottom][j])
        bottom -= 1

        if top > bottom:
            break

        # 从下到上
        for i in range(bottom, top - 1, -1):
            result.append(matrix[i][left])
        left += 1

        if left > right:
            break

    return result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

20、旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

1
2
3

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

1
2
3

提示：

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

思路解答：

1. 转置矩阵：先对矩阵进行转置操作，即将矩阵的行和列互换。
2. 翻转每一行：对每一行进行翻转操作，可以通过交换元素的方式实现。

def rotate(self, matrix: list[list[int]]) -> None:

    n = len(matrix)

    # 转置矩阵
    for i in range(n):
        for j in range(i, n):
            temp = matrix[i][j]
            matrix[i][j] = matrix[j][i]
            matrix[j][i] = temp

    # 翻转每一行
    for i in range(n):
        matrix[i].reverse()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

21、搜索二维矩阵II

编写一个高效的算法来搜索 *m* x *n* 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

1
2
3

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

1
2
3

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -109 <= matrix[i][j] <= 109
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -109 <= target <= 109

思路解答：

1. 从矩阵的右上角开始，如果目标值等于当前位置的值，则返回True。
2. 如果目标值大于当前位置的值，则目标值一定在当前位置的下方或左方，因为当前位置向左和向下都是递增的。
3. 如果目标值小于当前位置的值，则目标值一定在当前位置的左上方，因为当前位置向上和向右都是递增的。
4. 重复上述步骤，直到找到目标值或者搜索完整个矩阵。

def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:

    if not matrix or not matrix[0]:
        return False

    rows, cols = len(matrix), len(matrix[0])
    row, col = 0, cols - 1

    while row < rows and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            row += 1
        else:
            col -= 1

    return False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18