算法练习 Leetcode 力扣 329. Longest Increasing Path in a Matrix 解法

feellikelearning June 21, 2020 0 Comments

这题不知道为什么被标记为topological sort，但其实和topological sort没什么关系，只是DFS。Implementation确实和DFS的topological sort有点像，但是因为没有graph的dependency关系，其实还是不一样的。不过cache的使用上确实有相似性。以下是我写得比较满意的python解法

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if (matrix is None or len(matrix) == 0 or  
                matrix[0] is None or len(matrix[0]) == 0):
                return 0
        lines = len(matrix)
        cols = len(matrix[0])
        
        cache = [[0] * len(line) for line in matrix]
        
        def is_valid(i, j):
            return i >= 0 and i < lines and j >= 0 and j < cols
        
        max_l = 0
        dirs = [(1,0), (-1,0), (0,1), (0,-1)]
        
        def dfs(i: int, j: int) -> int:
            if cache[i][j] > 0:
                return cache[i][j]
            for d in dirs:
                i2 = i + d[0]
                j2 = j + d[1]
                if is_valid(i2, j2) and matrix[i2][j2] > matrix[i][j]:
                    cache[i][j] = max(cache[i][j], dfs(i2, j2))
            cache[i][j] += 1
            nonlocal max_l
            max_l = max(max_l, cache[i][j])
            return cache[i][j]
        
        for i in range(lines):
            for j in range(cols):
                dfs(i, j)
                
        return max_l

要点总结：

1. 用这种方式初始化cache比较简洁 ，新学到的 cache = [[0] * len(line) for line in matrix]
2. 用nested function大大减少需要传递状态的参数
3. nonlocal max_l可以让nested function直接改变外面的参数很方便，所以在外面call dfs的时候连return都不用处理
4. dirs = [(1,0), (-1,0), (0,1), (0,-1)]，i2 = i + d[0]，j2 = j + d[1]处理方向。以前都是手写上下左右，太啰嗦而且容易出错。这种方法对2维DFS很适用。