[Swift]LeetCode329. 矩阵中的最长递增路径 | Longest Increasing Path in a Matrix

概述Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of

Given an integer matrix,find the length of the longest increasing path.

From each cell,you can either move to four directions: left,right,up or down. You may NOT move diagonally or move outsIDe of the boundary (i.e. wrap-around is not allowed).

Example 1:

input: nums = [  [9,9,4],[6,6,8],[2,1,1]] Output: 4 Explanation: The longest increasing path is .[1,2,9]

Example 2:

input: nums = [  [3,4,5],[3,6],[2,1]] Output: 4 Explanation: The longest increasing path is . Moving diagonally is not allowed.[3,4,5,6]

给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1:

输入: nums = [  [9,[6,1,1]] 输出: 4 解释: 最长递增路径为 。[1,9]

示例 2:

输入: nums = [  [3,5],6],1]] 输出: 4 解释: 最长递增路径是 。注意不允许在对角线方向上移动。[3,6]

 284 ms

 1 class Solution { 2    func longestIncreasingPath(_ matrix: [[Int]]) -> Int { 3          4         if matrix.isEmpty || matrix[0].isEmpty { 5             return 0 6         } 7          8         let m = matrix.count 9         let n = matrix[0].count10         11         var counts = Array(repeating: Array(repeating: 0,count: n),count: m)12         var longest = 013         14         for i in 0..<m {15             for j in 0..<n {16                 let c = longestHelp(matrix,&counts,i,j)17                 longest = max(longest,c)18             }19         }20         21         return longest22     }23     24     func longestHelp(_ matrix: [[Int]],_ counts : inout [[Int]],_ x : Int,_ y : Int) ->Int  {25         if counts[x][y] != 0 {26             return counts[x][y]27         }28         29         var res = 130         if x > 0 && matrix[x-1][y] > matrix[x][y] {31             res = max(res,longestHelp(matrix,&counts,x-1,y) + 1)32         }33         if x < matrix.count-1 && matrix[x+1][y] > matrix[x][y] {34             res = max(res,x+1,y) + 1)35         }36         37         if y > 0 && matrix[x][y-1] > matrix[x][y] {38             res = max(res,x,y-1) + 1)39         }40         if y < matrix[0].count-1 && matrix[x][y+1] > matrix[x][y] {41             res = max(res,y+1) + 1)42         }43         44         counts[x][y] = res45         return res46     }47 }

404ms

 1 class Solution { 2     var dp: [[Int]] = [] 3     let dirs: [[Int]] = [[-1,0],[0,-1],[1,1]] 4     func longestIncreasingPath(_ matrix: [[Int]]) -> Int { 5         if matrix.count == 0 { return 0 } 6         dp = [[Int]](repeating: [Int](repeating: -1,count: matrix[0].count),count: matrix.count) 7         var res = 0 8         for r in 0..<matrix.count { 9             for c in 0..<matrix[0].count {10                 res = max(res,dfs(matrix,r,c))11             }12         }13         14         return res15     }16     17     private func dfs(_ matrix: [[Int]],_ r: Int,_ c: Int) -> Int {18         if self.dp[r][c] != -1 {19             return dp[r][c]20         }21         22         var res = 023         for dir in dirs {24             let newr  = r+dir[0],newc =  c + dir[1]25             if newr >= 0 && newc >= 0 &&26                 newr < matrix.count && newc < matrix[0].count &&27                 matrix[newr][newc] > matrix[r][c] {28                     res = max(res,newr,newc))29                 }30             31         }32         dp[r][c] = res+133         return res + 134     }35 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode329. 矩阵中的最长递增路径 | Longest Increasing Path in a Matrix全部内容，希望文章能够帮你解决[Swift]LeetCode329. 矩阵中的最长递增路径 | Longest Increasing Path in a Matrix所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。