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

创作时间:

作者:

@小白创作中心

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

引用

CSDN

https://m.blog.csdn.net/m0_72806612/article/details/145969122

力扣（LeetCode）热门100题是算法学习中的经典题目集，涵盖了各种数据结构和算法问题。其中，与二维矩阵相关的题目不仅考察了对矩阵操作的理解，还涉及了空间优化、状态机设计等高级编程技巧。本文总结了四道与矩阵相关的经典题目及其高效解法，适合有一定编程基础的读者学习参考。

1. 矩阵置零

这道题目要求将矩阵中包含0的行和列的所有元素都置为0。为了实现原地修改且不使用额外的空间，我们可以利用矩阵的第一行和第一列作为标记。

具体实现如下：

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m, n = len(matrix), len(matrix[0])
        flag_fc, flag_fr = False, False
        for num in matrix[0]:
            if num == 0:
                flag_fr = True
                break
        for i in range(m):
            if matrix[i][0] == 0:
                flag_fc = 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:
                    matrix[i][j] = 0
        
        if flag_fc == True:
            for i in range(m):
                matrix[i][0] = 0
        
        if flag_fr == True:
            for i in range(n):
                matrix[0][i] = 0

2. 螺旋矩阵

这道题目要求按照螺旋顺序遍历矩阵中的所有元素。我们可以通过设置四个状态来表示当前的移动方向（右、下、左、上），并用一个变量记录已经完成的圈数来确定移动的边界。

具体实现如下：

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 = 0
        ans = []
        now_state, c_r, i, j = 0, 0, 0, 0
        while done_number < (m * n):
            ans.append(matrix[i][j])
            done_number += 1
            if now_state == 0:
                if j < (n - 1 - c_r):
                    j += 1
                else:
                    now_state = 1
                    i += 1
            elif now_state == 1:
                if i < (m - 1 - c_r):
                    i += 1
                else:
                    now_state = 2
                    j -= 1
            elif now_state == 2:
                if j > c_r:
                    j -= 1
                else:
                    now_state = 3
                    i -= 1
                    c_r += 1
            else:
                if i > c_r:
                    i -= 1
                else:
                    # c_r += 1
                    now_state = 0
                    j += 1
            
        return ans

3. 旋转图像

这道题目要求将一个二维矩阵原地顺时针旋转90度。可以通过观察元素的变换规律来实现：matrix[i][j] 旋转后的位置是 matrix[j][n-1-i]。

具体实现如下：

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. 搜索二维矩阵Ⅱ

这道题目要求在一个二维矩阵中搜索目标值。矩阵的每一行和每一列都是递增排序的。可以利用右上角元素的特性（在单行中最大，在单列中最小）来进行搜索。

具体实现如下：

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