Leetcode Hot100之矩阵

1. 矩阵置零

• 题目描述
  给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
  
• 解题思路
  题目要求进行原地更改，也就是不能使用额外的空间，因此我们可以使用第一行的元素来记录对应的每一列是不是该置零，用第一列的元素来记录对应的每一行是不是该置零。但是这样的话就会有一个问题，就是第一行和第一列的元素会被覆盖，因此我们在覆盖第一行和第一列的元素前，需要额外的两个变量row_0_flag和col_0_flag来记录第一行和第一列是不是该置零。
  时间复杂度：O(m*n) 空间复杂度：O(1)
• 代码

  class Solution:
      def setZeroes(self, matrix: List[List[int]]) -> None:
          """
          Do not return anything, modify matrix in-place instead.
          """
          m = len(matrix)
          if m == 0:
              return 
          n = len(matrix[0])
          # 在使用第一行和第一列进行记录之前，先把第一行和第一列是否需要置零给求出来
          row_0_flag = False
          for i in range(n):
              if matrix[0][i] == 0:
                  row_0_flag = True
                  break
          col_0_flag = False
          for i in range(m):
              if matrix[i][0] == 0:
                  col_0_flag = True
                  break
          # 使用第一行和第一列进行记录
          for i in range(1, m):
              for j in range(1, n):
                  if matrix[i][j] == 0:
                      matrix[i][0] = 0
                      matrix[0][j] = 0
          for i in range(1, m):
              for j in range(1, n):
                  if (matrix[i][0] == 0 or matrix[0][j] == 0) and matrix[i][j] != 0:
                      matrix[i][j] = 0
          if row_0_flag:
              for i in range(n):
                  matrix[0][i] = 0
          if col_0_flag:
              for i in range(m):
                  matrix[i][0] = 0
  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

2. 螺旋矩阵

• 题目描述
  给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
  
• 解题思路
  1. 首先确认螺旋的圈数，圈数是（min(m, n) + 1） // 2，也就是最外层的循环数。
  2. 在每一圈中，我们需要分别从左到右，从上到下，从右到左，从下到上四个方向遍历，在解题时可以现在纸上把每个方向遍历的起始位置和终止位置写出来，这样就很容易写出代码。
  3. 注意在从右往左、从下到上遍历的时候，要判断是不是和从左往右、从上往下是不是一行，是一行的话就不用遍历了。
     时间复杂度：O(m*n) 空间复杂度：O(1)
• 代码

  class Solution:
      def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
          m = len(matrix)
          n = len(matrix[0])
          iters = (min(m, n) + 1) // 2
          res = []
          for i in range(iters):
              # 从左往右打印
              for j in range(i, n - i):
                  res.append(matrix[i][j])
              # 从上往下打印
              for j in range(i + 1, m - i):
                  res.append(matrix[j][n - 1 - i])
              # 从右往左打印，此时要判断是不是和从左往右打印的是一行，是一行的话很明显就不用打印了
              if m - i - 1 > i:
                  for j in range(n - 2 - i, i - 1, -1):
                      res.append(matrix[m - i - 1][j])
              # 从下往上打印，此时要判断是不是和从上往下打印是一列，是一列的话很明显就不用打印了
              if i < n - 1 - i:
                  for j in range(m - i - 2, i, -1):
                      res.append(matrix[j][i])
          return res
  
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23

3. 旋转图像

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

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

• 解题思路
  先转置，再左右镜像

• 代码

  class Solution:
      def rotate(self, matrix: List[List[int]]) -> None:
          """
          Do not return anything, modify matrix in-place instead.
          """
          n = len(matrix)
          # 转置
          for i in range(n):
              for j in range(i + 1, n):
                  matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
          # 左右镜像
          for i in range(n):
              l, r = 0, n - 1
              while l < r:
                  matrix[i][l], matrix[i][r] = matrix[i][r], matrix[i][l]
                  l += 1
                  r -= 1
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

4. 搜索二维矩阵 II

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

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

• 解题思路
  二分查找：从左上角开始搜索，小于target的话向下查找，大于target的话向左查找

• 代码

  class Solution:
      def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
          m = len(matrix)
          n = len(matrix[0])
          i = 0
          j = n - 1
          while i < m and j >= 0:
              if matrix[i][j] == target:
                  return True
              elif matrix[i][j] > target:
                  j -= 1
              else:
                  i += 1
          return False
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14