資訊專欄INFORMATION COLUMN
摘要：題目鏈接記憶化搜索，用一個(gè)二維記錄找到的最長(zhǎng)路徑的長(zhǎng)度，如果發(fā)現(xiàn)證明這個(gè)點(diǎn)被找過(guò)，不用重復(fù)。和這題一個(gè)思路。
Longest Increasing Path in a Matrix
題目鏈接：https://leetcode.com/problems...
dfs + 記憶化搜索，用一個(gè)二維dp記錄找到的最長(zhǎng)路徑的長(zhǎng)度，如果發(fā)現(xiàn)dpi != 0,證明這個(gè)點(diǎn)被找過(guò)，不用重復(fù)。Number of Islands和這題一個(gè)思路。
public class Solution {
public int longestIncreasingPath(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return 0;
// dp[i][j] the longest increasing len from (i, j)
// enumerate all start position
// dfs find the longest path, if not in dp[i][j]
dp = new int[matrix.length][matrix[0].length];
int global = 0;
for(int i = 0; i < matrix.length; i++) {
for(int j = 0; j < matrix[0].length; j++) {
if(dp[i][j] == 0) {
dp[i][j] = dfs(matrix, i, j);
}
global = Math.max(global, dp[i][j]);
}
}
return global;
}
int[][] dp;
int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private int dfs(int[][] matrix, int x, int y) {
if(dp[x][y] != 0) return dp[x][y];
int len = 1;
for(int i = 0; i < dir.length; i++) {
int nx = x + dir[i][0], ny = y + dir[i][1];
if(nx >= 0 && nx < matrix.length && ny >= 0 && ny < matrix[0].length) {
if(matrix[nx][ny] > matrix[x][y]) len = Math.max(len, dfs(matrix, nx, ny) + 1);
}
}
dp[x][y] = len;
return len;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66571.html
摘要：題目要求思路和代碼這里采用廣度優(yōu)先算法加上緩存的方式來(lái)實(shí)現(xiàn)。我們可以看到，以一個(gè)節(jié)點(diǎn)作為開始構(gòu)成的最長(zhǎng)路徑長(zhǎng)度是確定的。因此我們可以充分利用之前得到的結(jié)論來(lái)減少重復(fù)遍歷的次數(shù)。 題目要求 Given an integer matrix, find the length of the longest increasing path. From each cell, you can ei...
摘要：題目解答最重要的是用保存每個(gè)掃過(guò)結(jié)點(diǎn)的最大路徑。我開始做的時(shí)候，用全局變量記錄的沒(méi)有返回值，這樣很容易出錯(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...
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...
閱讀 2947·2021-11-23 09:51
閱讀 3200·2021-11-12 10:36
閱讀 3233·2021-09-27 13:37
閱讀 3193·2021-08-17 10:15
閱讀 2615·2019-08-30 15:55
閱讀 2781·2019-08-30 13:07
閱讀 814·2019-08-29 16:32
閱讀 2672·2019-08-26 12:00
