[Swift]LeetCode329. 矩阵中的最长递增路径 | Longest Increasin

发布时间：2020-12-14 05:06:14 所属栏目：百科来源：网络整理

导读：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 allo

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].count
10         
11         var counts = Array(repeating: Array(repeating: 0,count: n),count: m)
12         var longest = 0
13         
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 longest
22     }
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 = 1
30         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] = res
45         return res
46     }
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 res
15     }
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 = 0
23         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+1
33         return res + 1
34     }
35 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!