leetcode每日一题感悟

编程入门行业动态更新时间:2024-10-07 00:15:43

leetcode每日一题感悟

329. 矩阵中的最长递增路径

自己的想法：遍历矩阵中的每个点，同时每个点进行深度优先遍历，但是会超时

原因在于使用朴素深度优先搜索，时间复杂度是指数级，会超出时间限制，因此必须加以优化。

朴素深度优先搜索的时间复杂度过高的原因是进行了大量的重复计算，同一个单元格会被访问多次，每次访问都要重新计算。由于同一个单元格对应的最长递增路径的长度是固定不变的，因此可以使用记忆化的方法进行优化。用矩阵 memo 作为缓存矩阵，已经计算过的单元格的结果存储到缓存矩阵中。

也就是说，记录以及走过点他们所能走的最远的路径，这样再次遍历到这个点的时候，直接加上就可以了

链接：/

from typing import List
# 自己写的，超时了
class Solution:def longestIncreasingPath(self, matrix: List[List[int]]) -> int:if not matrix:return 0result = []row = len(matrix) - 1column = len(matrix[0]) - 1# 判断当前点是否有路可走def valid_path(i,j):if ((i+1<=row and matrix[i+1][j]>matrix[i][j])or (i-1>=0 and matrix[i-1][j]>matrix[i][j])or (j-1>=0 and matrix[i][j-1]>matrix[i][j])or (j+1<=column and matrix[i][j+1]>matrix[i][j])):return Trueelse:return False# 从i，j开始的路径def dfs(i,j,path):path.append((i, j))if valid_path(i,j):if i + 1 <= row and matrix[i+1][j] > matrix[i][j]:dfs(i + 1, j, path)# 回溯path.pop()if i - 1 >= 0 and matrix[i - 1][j] > matrix[i][j]:dfs(i - 1, j, path)path.pop()if j - 1 >= 0 and matrix[i][j - 1] > matrix[i][j]:dfs(i, j-1, path)path.pop()if j + 1 <= column and matrix[i][j + 1] > matrix[i][j]:dfs(i, j + 1, path)path.pop()else:result.append(len(path))# path.pop()returnfor i in range(len(matrix)):for j in range(len(matrix[0])):dfs(i,j,[])return max(result)if __name__ == '__main__':s = Solution()matrix = [[3,4,5],[3,2,6],[2,2,1]]result = s.longestIncreasingPath(matrix)print(result)