資訊專欄INFORMATION COLUMN
摘要：題目要求思路和代碼這里采用廣度優(yōu)先算法加上緩存的方式來實(shí)現(xiàn)。我們可以看到，以一個(gè)節(jié)點(diǎn)作為開始構(gòu)成的最長路徑長度是確定的。因此我們可以充分利用之前得到的結(jié)論來減少重復(fù)遍歷的次數(shù)。
題目要求
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.思路和代碼
這里采用廣度優(yōu)先算法加上緩存的方式來實(shí)現(xiàn)。我們可以看到，以一個(gè)節(jié)點(diǎn)作為開始構(gòu)成的最長路徑長度是確定的。因此我們可以充分利用之前得到的結(jié)論來減少重復(fù)遍歷的次數(shù)。
public class LongestIncreasingPathinaMatrix_329 {
//緩存
int max = 1;
public int longestIncreasingPath(int[][] matrix) {
if(matrix==null || matrix.length==0 || matrix[0].length == 0) return 0;
int[][] cache = new int[matrix.length][matrix[0].length];
for(int i = 0 ; i 0) return cache[i][j];
int max = 1;
int cur = matrix[i][j];
//如果上方的元素存在且大于當(dāng)前值，則獲取上方元素作為開頭的最長路徑的長度
if(i>0 && matrix[i-1][j] > cur){
max = Math.max(max, longestIncreasingPath(matrix, i-1, j, cache) + 1);
}
//如果下方的元素存在且大于當(dāng)前的值，則獲取下方元素作為開頭的最長路徑的長度
if(i cur){
max = Math.max(max, longestIncreasingPath(matrix, i+1, j, cache) + 1);
}
//如果左側(cè)元素存在且大于當(dāng)前的值，則獲取左側(cè)元素作為開頭的最長路徑的長度
if(j>0 && matrix[i][j-1] > cur){
max = Math.max(max, longestIncreasingPath(matrix, i, j-1, cache) + 1);
}
//如果右側(cè)元素存在且大于當(dāng)前的值，則獲取右側(cè)元素作為開頭的最長路徑的長度
if(j cur){
max = Math.max(max, longestIncreasingPath(matrix, i, j+1, cache) + 1);
}
//加入緩存
cache[i][j] = max;
return max;
}
}
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/71044.html
摘要：復(fù)雜度思路為了避免搜索已經(jīng)搜索的點(diǎn)。所以考慮用一個(gè)數(shù)組，記錄到每一個(gè)點(diǎn)能產(chǎn)生的最長序列的長度?？紤]用進(jìn)行搜索，對于每一個(gè)點(diǎn)來說，考慮先找到最小的那個(gè)點(diǎn)針對每一條路徑的。然后對于每一點(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)先遍歷。我們存儲每個(gè)位置深度優(yōu)先遍歷的結(jié)果，當(dāng)下一次走到這個(gè)位置的時(shí)候，我們直接返回當(dāng)前位置記錄的值，這樣可以減少遍歷的次數(shù)，加快執(zhí)行速度。 Description Given an integer matrix, find the length of the longest increasing...
摘要：題目解答最重要的是用保存每個(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, y...
閱讀 1024·2023-04-25 23:50
閱讀 2176·2021-11-19 09:40
閱讀 670·2019-08-30 13:50
閱讀 2785·2019-08-29 17:11
閱讀 1100·2019-08-29 16:37
閱讀 3084·2019-08-29 12:54
閱讀 2861·2019-08-28 18:17
閱讀 2728·2019-08-26 16:55
