leetcode刷题记录——矩阵

这篇Blog将分享我在做leetcode面试经典150题中矩阵部分几道题的做题思路和代码。

36 有效的数组

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

一个有效的数独（部分已被填充）不一定是可解的。

只需要根据以上规则，验证已经填入的数字是否有效即可。

空白格用 '.' 表示。

示例 1：

输入：board =

[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]

输出：true

示例 2：

输入：board =

[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]

输出：false

解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

board.length == 9

board[i].length == 9

board[i][j] 是一位数字（1-9）或者 '.'

思路

1. 核心条件就是每行每列每3*3的区域内不能重复
2. 设置一个索引b来表示该数字在3*3区域内的索引

   class Solution:
       def isValidSudoku(self, board: List[List[str]]) -> bool:
           # 初始化三个二维列表来跟踪三个维度的数字情况
           row = [[0] * 9 for _ in range(9)]
           col = [[0] * 9 for _ in range(9)]
           block = [[0] * 9 for _ in range(9)]
           
           for i in range(9):
               for j in range(9):
                   if board[i][j] != '.':
                       num = int(board[i][j]) - 1 # 将数字字符转化为整数并调整为0索引
                       b = (i // 3) * 3 + j // 3 # 建立b索引
                       if row[i][num] or col[j][num] or block[b][num]:
                           return False
                       row[i][num] = col[j][num] = block[b][num] = 1
           return True

时间复杂度

时间复杂度O(1)，执行时间56ms，消耗内存16.2MB

54 螺旋矩阵

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

示例 1：

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

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

示例 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]

提示：

m == matrix.length

n == matrix[i].length

1 <= m, n <= 10

-100 <= matrix[i][j] <= 100

思路

相当于走格子，第一行走完走最后一列，最后一列走完走最后一行，最后一行走完走第一列，最后各自缩小一格然后走内侧。

提示：这里需要注意，从左到右遍历顶部行的时候不能用[0]来表示，会影响后续。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix: return []
        left, right, top, bottom = 0, len(matrix[0]) - 1, 0, len(matrix) - 1
        res = []
        while left <= right and top <= bottom:
            # 从左到右遍历顶部行
            for i in range(left, right + 1):
                res.append(matrix[top][i])
            # 从上到下遍历右侧列
            for j in range(top + 1, bottom + 1):
                res.append(matrix[j][right])
            if left < right and top < bottom:
                # 从右到左遍历底部行
                for i in range(right - 1, left, -1):
                    res.append(matrix[bottom][i])
                # 从下到上遍历左侧列
                for j in range(bottom, top, -1):
                    res.append(matrix[j][left])
            left, right, top, bottom = left + 1, right - 1, top + 1, bottom - 1
        return res

时间复杂度

时间复杂度O(m*n)，执行用时55ms，消耗内存16.4MB

48 旋转图像

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

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

示例 1：

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

输出：[[7,4,1],[8,5,2],[9,6,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]]

提示：

n == matrix.length == matrix[i].length

1 <= n <= 20

-1000 <= matrix[i][j] <= 1000

思路

1. 先明确题目要求是讲整个矩阵顺时针旋转90°
2. 根据每个元素坐标来看，我们只需要将每个元素的坐标交换，最后将整个图像进行逐行反转就能直接完成

下面有一个比较形象的图来演示一下过程

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for i in range(n):
            for j in range(i, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        for i in range(n):
            matrix[i].reverse()
        return matrix

时间复杂度

时间复杂度O($n^2$)，执行时间36ms，消耗内存16.5MB

73 矩阵置零

给定一个 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]]

示例 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]]

提示：

m == matrix.length

n == matrix[0].length

1 <= m, n <= 200

-231 <= matrix[i][j] <= 231 - 1

思路：

1. 设置两个集合来存储横纵坐标。
2. 两次遍历，第一次遍历标记为0的元素横纵坐标并分别添加到set中，第二次遍历对元素进行修改。

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        if matrix is None or len(matrix) == 0 or len(matrix[0]) == 0:
            return matrix
        rows, cols = set(), set()
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    rows.add(i)
                    cols.add(j)
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if i in rows or j in cols:
                    matrix[i][j] = 0    
        return matrix

时间复杂度

时间复杂度$O(m*n)$，执行时间38ms，消耗内存17.1MB

289 生命游戏

根据 百度百科 ，生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；

如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；

如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；

如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

示例 1：

输入：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]]

示例 2：

输入：board = [[1,1],[1,0]]

输出：[[1,1],[1,1]]

提示：

m == board.length

n == board[i].length

1 <= m, n <= 25

board[i][j] 为 0 或 1

错误代码

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        if not board: return 
        m, n = len(board), len(board[0])
        cnt = 0
        dict = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
        for i in range(m):
            for j in range(n):
                for dx, dy in dict:
                    x, y = i + dx, j + dy
                    if 0 <= x < m and 0 <= y < n:
                        cnt += board[x][y] & 1
                if board[i][j] == 1 and (cnt < 2 or cnt > 3):
                    board[i][j] = 3
                if board[i][j] == 0 and cnt == 3:
                    board[i][j] = 2
        for i in range(m):
            for j in range(n):
                board[i][j] >>= 1

这个版本的代码直接报错，而后根据相似的思路重新写了一个版本的代码，先讲一下思路。

思路

1. 设置好八个位置的坐标
2. 设置一个函数用于对某个位置的细胞周围的活细胞进行标记
3. 根据题目所给出的情况进行处理
4. 最后对所有位置的细胞进行遍历
5. -1表示当前细胞是从活变死，2表示当前细胞是从死变活

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        if not board or not board[0]:
            return
    
        m, n = len(board), len(board[0])
        directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
        
        def count_live_neighbors(x, y):
            count = 0
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and abs(board[nx][ny]) == 1:
                    count += 1
            return count
        
        for i in range(m):
            for j in range(n):
                live_neighbors = count_live_neighbors(i, j)
                
                if board[i][j] == 1 and (live_neighbors < 2 or live_neighbors > 3):
                    board[i][j] = -1
                if board[i][j] == 0 and live_neighbors == 3:
                    board[i][j] = 2
        for i in range(m):
            for j in range(n):
                if board[i][j] == -1:
                    board[i][j] = 0
                elif board[i][j] == 2:
                    board[i][j] = 1

时间复杂度

时间复杂度$O(m * n)$，执行时间36ms，消耗内存16.5MB