• 【力扣hot100】刷题笔记Day7

    前言

    • 身边同学已经陆陆续续回来啦，舍友都开始投简历了，我也要加油啦！刷完hot100就投！

    73. 矩阵置零 - 力扣（LeetCode）

    • 标记数组：空间复杂度O(m+n)

        1. class Solution:
        2.     def setZeroes(self, matrix: List[List[int]]) -> None:
        3.         m, n = len(matrix), len(matrix[0])
        4.         row, col = [False] * m, [False] * n  # 标记数组
        5.         # 遍历一次，标记对应的行列为0
        6.         for i in range(m):
        7.             for j in range(n):
        8.                 if matrix[i][j] == 0:
        9.                     row[i] = col[j] = True
        10.         # 遍历二次，根据标记修改对应行列
        11.         for i in range(m):
        12.             for j in range(n):
        13.                 if row[i] or col[j]:
        14.                     matrix[i][j] = 0

    • 两个标记变量：空间复杂度O(1)

      • 思路参考题解，遇到0就向首行首列汇报，最后再把首行首列置0
        1. class Solution:
        2.     def setZeroes(self, matrix: List[List[int]]) -> None:
        3.         m, n = len(matrix), len(matrix[0])
        4.         # 如果可迭代对象中有任何一个元素为 True，则 any 函数返回 True；否则返回 False
        5.         flag_col0 = any(matrix[i][0] == 0 for i in range(m))  # 判断首行是否有0
        6.         flag_row0 = any(matrix[0][j] == 0 for j in range(n))  # 判读首列是否有0
        7.         # 迭代非首行非首列，遇到0就把置0指令放在首行首列
        8.         for i in range(1, m):
        9.             for j in range(1, n):
        10.                 if matrix[i][j] == 0:
        11.                     matrix[i][0] = matrix[0][j] = 0
        12.         # 迭代非首行非首列，根据指令置0
        13.         for i in range(1, m):
        14.             for j in range(1, n):
        15.                 if matrix[i][0] == 0 or matrix[0][j] == 0:
        16.                     matrix[i][j] = 0
        17.         # 首行有0，则全置0
        18.         if flag_col0:
        19.             for i in range(m):
        20.                 matrix[i][0] = 0
        21.         # 首列有0，则全置0
        22.         if flag_row0:
        23.             for j in range(n):
        24.                 matrix[0][j] = 0

    • 一个标记变量：空间复杂度O(1)

      • 参考题解，保存首行，但是要全部倒序遍历，防止提前更新，太难想仅作参考
        1. class Solution:
        2.     def setZeroes(self, matrix: List[List[int]]) -> None:
        3.         m = len(matrix)
        4.         n = len(matrix[0])
        5.         first_row = False   # 标记首行是否有0元素
        6.         for i, row in enumerate(matrix):
        7.             for j, item in enumerate(row):
        8.                 if i == 0 and item == 0:
        9.                     first_row = True    # 首行出现0元素，用标志位标记
        10.                 elif item == 0:
        11.                     matrix[i][0] = 0    # 非首行出现0元素，将对应的列首置为0，说明该列要置为0
        12.                     matrix[0][j] = 0    # 将对应的行首置为0，说明该行要置为0
        13.         for i in range(m - 1, -1, -1):
        14.             for j in range(n - 1, -1, -1):
        15.                 # 从最后一个元素反向遍历，避免行首和列首的信息被篡改
        16.                 if i == 0 and first_row:
        17.                     matrix[i][j] = 0    # 首行元素是否置为0看标志位
        18.                 elif i != 0 and (matrix[i][0] == 0 or matrix[0][j] == 0):
        19.                     matrix[i][j] = 0    # 非首行元素是否置为0看行首和列首是否为0

    54. 螺旋矩阵 - 力扣（LeetCode）

    • 边界模拟

      • 类似之前C++版本，设置边界，依次循环模拟输出，边界溢出则跳出循环
        1. class Solution:
        2.     def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        3.         res = []
        4.         l, r, u, d = 0, len(matrix[0])-1, 0, len(matrix)-1
        5.         while True:
        6.             # 向右
        7.             for i in range(l, r+1): res.append(matrix[u][i])
        8.             u += 1
        9.             if u > d: break
        10.             # 向下
        11.             for i in range(u, d+1): res.append(matrix[i][r])
        12.             r -= 1
        13.             if r < l: break
        14.             # 向左
        15.             for i in range(r, l-1, -1): res.append(matrix[d][i])
        16.             d -= 1
        17.             if d < u: break
        18.             # 向上
        19.             for i in range(d, u-1, -1): res.append(matrix[i][l])
        20.             l += 1
        21.             if l > r: break
        22.         return res

     48. 旋转图像 - 力扣（LeetCode）

    • 辅助数组

        1. class Solution:
        2.     def rotate(self, matrix: List[List[int]]) -> None:
        3.         n = len(matrix)
        4.         matrix_new = [[0] * n for _ in range(n)]  # 新的n*n的矩阵
        5.         for i in range(n):
        6.             for j in range(n):
        7.                 # matrix[row][col]旋转到matrix_new[col][n−row−1]
        8.                 matrix_new[j][n-i-1] = matrix[i][j]
        9.         # 不能写成 matrix = matrix_new
        10.         matrix[:] = matrix_new

    •  原地旋转

        1. class Solution:
        2.     def rotate(self, matrix: List[List[int]]) -> None:
        3.         n = len(matrix)
        4.         for i in range(n // 2):  # 偶数n/2，奇数(n-1)/2
        5.             for j in range((n + 1) // 2):  # 偶数n/2，奇数(n+1)/2
        6.                 matrix[i][j], matrix[n-j-1][i], matrix[n-i-1][n-j-1], matrix[j][n-i-1] \
        7.                 = matrix[n-j-1][i], matrix[n-i-1][n-j-1], matrix[j][n-i-1], matrix[i][j]

    •  两次翻转

        1. class Solution:
        2.     def rotate(self, matrix: List[List[int]]) -> None:
        3.         n = len(matrix)
        4.         # 上下翻转：只遍历上半部
        5.         for i in range(n // 2):
        6.             for j in range(n):
        7.                 matrix[i][j], matrix[n-i-1][j] = matrix[n-i-1][j], matrix[i][j]
        8.         # 对角翻转：只遍历下三角
        9.         for i in range(n):
        10.             for j in range(i):
        11.                 matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

     240. 搜索二维矩阵 II - 力扣（LeetCode）

    • 直接搜索：N(mn)

      • 就不用传统的遍历写法了，这里记录两种仅用一行就可以实现的搜索算法
        1. class Solution:
        2.     def searchMatrix(self, M: List[List[int]], target: int) -> bool:
        3.     # chain()函数于将多个可迭代对象连接成一个单独的迭代器
        4.     # 这里用于连接多个被*M解包得到的多个一维列表   
        5.     return target in chain(*M)
        6.     # 直接利用sum函数转化为一个一维列表
        7.     return target in sum(M,[])

    • 二分查找：N(log(mn))

        1. class Solution:
        2.     def searchMatrix(self, M: List[List[int]], target: int) -> bool:
        3.         def bin_search(arr,target):
        4.             l,r = 0,len(arr)-1
        5.             while l <= r:
        6.                 mid = (l+r) // 2
        7.                 if arr[mid] == target:
        8.                     return True
        9.                 elif arr[mid] < target:
        10.                     l = mid + 1
        11.                 else:
        12.                     r = mid - 1
        13.             return False
        14.         m = len(M)
        15.         # 逐行进行二分查找
        16.         for i in range(m):
        17.             if bin_search(M[i], target):
        18.                 return True
        19.         return False

    • 贪心BST

      • 也叫折线搜索，来源于题解，图画的很清晰，从右上角出发进行搜索
        1. class Solution:
        2.     def searchMatrix(self, M: List[List[int]], target: int) -> bool:
        3.         i, j = len(M) - 1, 0
        4.         # 右上角出发进行搜索
        5.         while i >= 0 and j <= len(M[0]) - 1:
        6.             if target > M[i][j]:
        7.                 j += 1  # 往下移，排除一行
        8.             elif target < M[i][j]:
        9.                 i -= 1  # 往左移，排除一列
        10.             else:
        11.                 return True
        12.         return False

     后言

    • 一题多解的还是尽量每个解都弄懂，前期基础打好点，后面能快速写出最简单的就好啦
  • 相关阅读:
    STS中打开Ibatis的xml文件提示错误
    阿旭机器学习实战【5】KNN算法实战练习2：利用KNN模型进行手写体数字识别
    Android---Synchronized 和 ReentrantLock
    《Google软件工程之道》软件工程随想
    K_A01_001 基于单片机驱动WS2812 点灯流水灯 0-9显示
    通过lame_enc.dll实现将Wav转为mp3格式.wav要求是16bit
    C#-多线程的使用Tread
    python实现ModBusRTU客户端
    分布式多级缓存
    windows cmd 常用操作命令
  • 原文地址：https://blog.csdn.net/qq_56077562/article/details/136177123