摘要:复杂度思路为了避免搜索已经搜索的点。所以考虑用一个数组,记录到每一个点能产生的最长序列的长度。考虑用进行搜索,对于每一个点来说,考虑先找到最小的那个点针对每一条路径的。然后对于每一点再递增回去,依次累积找到增加的值。
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.
复杂度
O(MN),O(N)
思路
为了避免搜索已经搜索的点。所以考虑用一个dp数组,记录到每一个点能产生的最长序列的长度。考虑用dfs进行搜索,对于每一个点来说,考虑先找到最小的那个点针对每一条路径的。然后对于每一点再递增回去,依次累积找到增加的值。
代码
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]; }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/65237.html
摘要:题目要求思路和代码这里采用广度优先算法加上缓存的方式来实现。我们可以看到,以一个节点作为开始构成的最长路径长度是确定的。因此我们可以充分利用之前得到的结论来减少重复遍历的次数。 题目要求 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...
摘要:思路这道题主要使用记忆化递归和深度优先遍历。我们以给定的矩阵的每一个位置为起点,进行深度优先遍历。我们存储每个位置深度优先遍历的结果,当下一次走到这个位置的时候,我们直接返回当前位置记录的值,这样可以减少遍历的次数,加快执行速度。 Description Given an integer matrix, find the length of the longest increasing...
摘要:题目解答最重要的是用保存每个扫过结点的最大路径。我开始做的时候,用全局变量记录的没有返回值,这样很容易出错,因为任何一个用到的环节都有可能改变值,所以还是在函数中定义,把当前的直接返回计算不容易出错。 题目:Given an integer matrix, find the length of the longest increasing path. From each cell, y...
阅读 1708·2021-11-18 13:20
阅读 1109·2021-10-11 10:59
阅读 2938·2021-08-24 10:01
阅读 3483·2019-08-29 14:21
阅读 3321·2019-08-29 14:15
阅读 3497·2019-08-26 12:23
阅读 3320·2019-08-26 11:46
阅读 3324·2019-08-26 11:35