算法練習 Leetcode 力扣 329. Longest Increasing Path in a Matrix 解法

這題不知道為什麼被標記為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很適用。

Leave a Comment

Your email address will not be published.