資訊專欄INFORMATION COLUMN
摘要：復(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
DP + DFSGiven 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.
復(fù)雜度
O(MN),O(N)
思路
為了避免搜索已經(jīng)搜索的點(diǎn)。所以考慮用一個(gè)dp數(shù)組，記錄到每一個(gè)點(diǎn)能產(chǎn)生的最長序列的長度?？紤]用dfs進(jìn)行搜索，對于每一個(gè)點(diǎn)來說，考慮先找到最小的那個(gè)點(diǎn)針對每一條路徑的。然后對于每一點(diǎn)再遞增回去，依次累積找到增加的值。
代碼
public int longestIncreasingPath(int[][] matrix) {
if(matrix.length == 0) return 0;
int row = matrix.length, col = matrix[0].length;
int[][] dp = new int[row][col];
//dp = {0};
int val = 0;
for(int i = 0; i < row; i ++) {
for(int j = 0; j < col; j ++) {
if(helper(matrix, i, j, dp) > val) {
val = helper(matrix, i, j, dp);
}
}
}
return val;
}
public int helper(int[][] matrix, int i, int j, int[][] dp) {
//this is the point;
if(dp[i][j] != 0) return dp[i][j];
int val = 0;
if(i + 1 < matrix.length && matrix[i + 1][j] < matrix[i][j]) {
val = Math.max(val, helper(matrix, i + 1, j, dp));
}
if(i - 1 >= 0 && matrix[i - 1][j] < matrix[i][j]) {
val = Math.max(val, helper(matrix, i - 1, j, dp));
}
if(j + 1 < matrix[0].length && matrix[i][j + 1] < matrix[i][j]) {
val = Math.max(val, helper(matrix, i, j + 1, dp));
}
if(j - 1 >= 0 && matrix[i][j - 1] < matrix[i][j]) {
val = Math.max(val, helper(matrix, i, j - 1, dp));
}
dp[i][j] = val + 1;
return dp[i][j];
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65237.html
摘要：題目要求思路和代碼這里采用廣度優(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 ei...
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...
摘要：題目解答最重要的是用保存每個(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...
閱讀 1772·2021-11-18 13:20
閱讀 1163·2021-10-11 10:59
閱讀 2995·2021-08-24 10:01
閱讀 3509·2019-08-29 14:21
閱讀 3359·2019-08-29 14:15
閱讀 3527·2019-08-26 12:23
閱讀 3348·2019-08-26 11:46
閱讀 3355·2019-08-26 11:35
