力扣hot 100之矩阵四题解法总结

本期总结hot100 中二维矩阵的题，时空复杂度就不分析了

1.矩阵置零

原地标记，用第一行和第一列作为当前行列是否为0的标记，同时用两个标签分别记录0行、0列的标记空间中原本是否有0

class Solution:def setZeroes(self, matrix: List[List[int]]) -> None:"""Do not return anything, modify matrix in-place instead."""# inf, 0, >0分别指示新m, n = len(matrix), len(matrix[0])flag_fc, flag_fr = False, Falsefor num in matrix[0]:if num == 0:flag_fr = Truebreakfor i in range(m):if matrix[i][0] == 0:flag_fc = Truebreakfor i in range(1, m):for j in range(1, n):if matrix[i][j] == 0:matrix[i][0] = 0matrix[0][j] = 0for i in range(1, m):for j in range(1, n):if matrix[i][0] == 0 or matrix[0][j] == 0:matrix[i][j] = 0if flag_fc == True:for i in range(m):matrix[i][0] = 0if flag_fr == True:for i in range(n):matrix[0][i] = 0

2.螺旋矩阵

以四个状态标记当前移动的四个方向，当前移动的界限由其后一个方向已经转的圈数来界定，注意到状态3的前一个圈数为状态0，所以在状态2完成时要及时更新界限，否则状态3的界限会因晚更新而出错

class Solution:def spiralOrder(self, matrix: List[List[int]]) -> List[int]:# 用四个数对应4个遍历的方向[0, 1, 2, 3] - [右，下，左，上]m, n = len(matrix), len(matrix[0])done_number = 0ans = []now_state, c_r, i, j = 0, 0, 0, 0while done_number < (m * n):ans.append(matrix[i][j])done_number += 1if now_state == 0:if j < (n - 1 - c_r):j += 1else:now_state = 1i += 1elif now_state == 1:if i < (m - 1 - c_r):i += 1else:now_state = 2j -= 1elif now_state == 2:if j > c_r:j -= 1else:now_state = 3i -= 1c_r += 1else:if i > c_r:i -= 1else:# c_r += 1now_state = 0j += 1return ans

3.旋转图像

旋转图像，本题是对一个数组原地顺时针旋转90度

规律为

matrix[i][j]（原索引位置）​→matrix[j][n−1−i]（旋转后索引位置）

第一种​复制数组，不满足原地的要求

第二种设置个中间变量，四个为一组螺旋旋转，保存原先maxtrix[i][j]位置的元素，以左上半矩阵为参照，如果行数为奇数，需要规定行或列加一，可用取余来统一奇偶情况：

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 // 2):for j in range(n // 2 + (n % 2)):tem = matrix[i][j]matrix[i][j] = matrix[n - j - 1][i]matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]matrix[j][n - i - 1] = tem

4.搜索二维矩阵Ⅱ

对于这种数组，右上角元素的特点：在单行中最大，在单列中最小

由此可用当前右上角数与target比较，缩小范围，进行排除：如等于则找到；target大于右上角则行数减一（当前行必无target）、反之列数减一（当前列必无target）

class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:cur_r, cur_u = len(matrix[0]) - 1, 0while cur_r >= 0 and cur_u <= (len(matrix) - 1):if matrix[cur_u][cur_r] == target:return Trueelif matrix[cur_u][cur_r] > target:cur_r -= 1else:cur_u += 1return False

思路参考各路题解，欢迎补充