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 outside of the boundary (i.e. wrap-around is not allowed).
Example 1:
Input: nums = [ [9,9,4], [6,6,8], [2,1,1] ] Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].
Example 2:
Input: nums = [ [3,4,5], [3,2,6], [2,2,1] ] Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
Solutionclass Solution { private static final int[][] dirs = {{0,1},{0,-1},{-1,0},{1,0}}; 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 curMax = dfs(matrix, i, j, cache); max = Math.max(max, curMax); } } return max; } private int dfs(int[][] matrix, int i, int j, int[][] cache) { //if saved(visited), return directly if (cache[i][j] != 0) return cache[i][j]; int m = matrix.length, n = matrix[0].length; int max = 1; //this for loop is actually getting dfs result for 4 directions for (int[] dir: dirs) { int x = i+dir[0], y = j+dir[1]; if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) continue; int curMax = 1+dfs(matrix, x, y, cache); max = Math.max(max, curMax); } cache[i][j] = max; return max; } }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/71713.html
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)先算法加上緩存的方式來實現(xiàn)。我們可以看到,以一個節(jié)點作為開始構(gòu)成的最長路徑長度是確定的。因此我們可以充分利用之前得到的結(jié)論來減少重復(fù)遍歷的次數(shù)。 題目要求 Given an integer matrix, find the length of the longest increasing path. From each cell, you can ei...
摘要:復(fù)雜度思路為了避免搜索已經(jīng)搜索的點。所以考慮用一個數(shù)組,記錄到每一個點能產(chǎn)生的最長序列的長度。考慮用進行搜索,對于每一個點來說,考慮先找到最小的那個點針對每一條路徑的。然后對于每一點再遞增回去,依次累積找到增加的值。 LeetCode[329] Longest Increasing Path in a Matrix Given an integer matrix, find the ...
摘要:思路這道題主要使用記憶化遞歸和深度優(yōu)先遍歷。我們以給定的矩陣的每一個位置為起點,進行深度優(yōu)先遍歷。我們存儲每個位置深度優(yōu)先遍歷的結(jié)果,當(dāng)下一次走到這個位置的時候,我們直接返回當(dāng)前位置記錄的值,這樣可以減少遍歷的次數(shù),加快執(zhí)行速度。 Description Given an integer matrix, find the length of the longest increasing...
摘要:題目解答最重要的是用保存每個掃過結(jié)點的最大路徑。我開始做的時候,用全局變量記錄的沒有返回值,這樣很容易出錯,因為任何一個用到的環(huán)節(jié)都有可能改變值,所以還是在函數(shù)中定義,把當(dāng)前的直接返回計算不容易出錯。 題目:Given an integer matrix, find the length of the longest increasing path. From each cell, y...
閱讀 1938·2021-11-24 09:39
閱讀 3278·2021-09-22 14:58
閱讀 1162·2019-08-30 15:54
閱讀 3315·2019-08-29 11:33
閱讀 1788·2019-08-26 13:54
閱讀 1598·2019-08-26 13:35
閱讀 2468·2019-08-23 18:14
閱讀 762·2019-08-23 17:04