資訊專欄INFORMATION COLUMN
摘要：題目解答最重要的是用保存每個(gè)掃過結(jié)點(diǎn)的最大路徑。我開始做的時(shí)候，用全局變量記錄的沒有返回值，這樣很容易出錯(cuò)，因?yàn)槿魏我粋€(gè)用到的環(huán)節(jié)都有可能改變值，所以還是在函數(shù)中定義，把當(dāng)前的直接返回計(jì)算不容易出錯(cuò)。
題目：
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.
解答：
最重要的是用cache保存每個(gè)掃過結(jié)點(diǎn)的最大路徑。我開始做的時(shí)候，用全局變量記錄的max, dfs沒有返回值，這樣很容易出錯(cuò)，因?yàn)槿魏我粋€(gè)用到max的環(huán)節(jié)都有可能改變max值，所以還是在函數(shù)中定義，把當(dāng)前的max直接返回計(jì)算不容易出錯(cuò)。
public class Solution {
public int DFS(int[][] matrix, int i, int j, int[][] cache) {
if (cache[i][j] != 0) return cache[i][j];
//改進(jìn)：記錄下每一個(gè)訪問過的點(diǎn)的最大長(zhǎng)度，當(dāng)重新訪問到這個(gè)點(diǎn)的時(shí)候，就不需要重復(fù)計(jì)算
int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int max = 1;
for (int k = 0; k < dir.length; k++) {
int x = i + dir[k][0], y = j + dir[k][1];
if (x < 0 || x > matrix.length - 1 || y < 0 || y > matrix[0].length - 1) {
continue;
} else {
if (matrix[x][y] > matrix[i][j]) {
//這里當(dāng)前結(jié)點(diǎn)只算長(zhǎng)度1,然后加上dfs后子路徑的長(zhǎng)度，比較得出最大值
int len = 1 + DFS(matrix, x, y, cache);
max = Math.max(max, len);
}
}
}
cache[i][j] = max;
return max;
}
public int longestIncreasingPath(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int[][] cache = new int[m][n];
int max = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int len = DFS(matrix, i, j, cache);
max = Math.max(max, len);
}
}
return max;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64917.html
摘要：題目要求思路和代碼這里采用廣度優(yōu)先算法加上緩存的方式來實(shí)現(xiàn)。我們可以看到，以一個(gè)節(jié)點(diǎn)作為開始構(gòu)成的最長(zhǎng)路徑長(zhǎng)度是確定的。因此我們可以充分利用之前得到的結(jié)論來減少重復(fù)遍歷的次數(shù)。 題目要求 Given an integer matrix, find the length of the longest increasing path. From each cell, you can ei...
摘要：復(fù)雜度思路為了避免搜索已經(jīng)搜索的點(diǎn)。所以考慮用一個(gè)數(shù)組，記錄到每一個(gè)點(diǎn)能產(chǎn)生的最長(zhǎng)序列的長(zhǎng)度?？紤]用進(jìn)行搜索，對(duì)于每一個(gè)點(diǎn)來說，考慮先找到最小的那個(gè)點(diǎn)針對(duì)每一條路徑的。然后對(duì)于每一點(diǎn)再遞增回去，依次累積找到增加的值。 LeetCode[329] Longest Increasing Path in a Matrix Given an integer matrix, find the ...
Problem 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 ou...
Problem 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 ou...
摘要：思路這道題主要使用記憶化遞歸和深度優(yōu)先遍歷。我們以給定的矩陣的每一個(gè)位置為起點(diǎn)，進(jìn)行深度優(yōu)先遍歷。我們存儲(chǔ)每個(gè)位置深度優(yōu)先遍歷的結(jié)果，當(dāng)下一次走到這個(gè)位置的時(shí)候，我們直接返回當(dāng)前位置記錄的值，這樣可以減少遍歷的次數(shù)，加快執(zhí)行速度。 Description Given an integer matrix, find the length of the longest increasing...
閱讀 667·2023-04-25 18:37
閱讀 2819·2021-10-12 10:12
閱讀 8432·2021-09-22 15:07
閱讀 591·2019-08-30 15:55
閱讀 3205·2019-08-30 15:44
閱讀 2222·2019-08-30 15:44
閱讀 1651·2019-08-30 13:03
閱讀 1586·2019-08-30 12:55
