0%

leetcode Longest Increasing Path in a Matrix

leetcode 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 the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = [

[9,9,4],

[6,6,8],

[2,1,1]

]

Return 4 The longest increasing path is [1, 2, 6, 9]. Example 2:

nums = [ [3,4,5], [3,2,6], [2,2,1]]

Return 4 The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

题目地址:leetcode Longest Increasing Path in a Matrix

题意:给定一个矩阵,在里面找出最大上升路径

思路:

记忆化搜索。

设dis[i][j]为当前点出发最大上升路径的值。初始设置为0,表示该点未知,需要更新。

再次碰到的时候只需要返回该值即可。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int dx[] = { 1 , -1, 0 , 0  };
int dy[] = { 0 , 0 , 1 , -1 };
class Solution {
public:
int dfs(int x, int y, const int &m,const int &n,vector<vector<int>>& matrix, vector<vector<int>>& dis) {
if (dis[x][y]) return dis[x][y];

for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < m && ny < n && matrix[nx][ny] > matrix[x][y]) {
dis[x][y] = max(dis[x][y], dfs(nx, ny, m, n, matrix, dis));
}
}
return ++dis[x][y];
}

int longestIncreasingPath(vector<vector<int>>& matrix) {
if (!matrix.size()) return 0;
int m = matrix.size(), n = matrix[0].size();
vector<vector<int> > dis(m, vector<int>(n, 0));
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
ans = max(ans, dfs( i, j, m, n, matrix, dis));
}
}
return ans;
}
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
int []dx = { 1 , -1, 0 , 0 };
int []dy = { 0 , 0 , 1 , -1 };
public int longestIncreasingPath(int[][] matrix) {
if (matrix.length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int[][] dis = new int [m][n];
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
ans = Math.max(ans, dfs( i, j, m, n, matrix, dis));
}
}
return ans;
}

int dfs(int x, int y, int m,int n,int[][] matrix, int[][] dis) {
if (dis[x][y] != 0) return dis[x][y];

for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && ny >= 0 && nx < m && ny < n && matrix[nx][ny] > matrix[x][y]) {
dis[x][y] = Math.max(dis[x][y], dfs(nx, ny, m, n, matrix, dis));
}
}
return ++dis[x][y];
}
}

 

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
if not matrix: return 0
m, n = len(matrix), len(matrix[0])
dis = [[0 for j in xrange(n)] for i in xrange(m)]
return max([self.dfs(i, j, m, n, matrix, dis) for j in xrange(n) for i in xrange(m)])

def dfs(self, x, y, m, n, matrix, dis):
if dis[x][y]: return dis[x][y]
for dx, dy in ([(1, 0), (-1, 0), (0, 1), (0, -1)]):
nx, ny = x + dx, y + dy
if nx >= 0 and nx < m and ny >= 0 and ny < n and matrix[x][y] < matrix[nx][ny]:
dis[x][y] = max(dis[x][y], self.dfs(nx, ny, m, n, matrix, dis))
dis[x][y] += 1
return dis[x][y]

 

本文是leetcode 329 Longest Increasing Path in a Matrix  的题解,更多题解可见

https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~