网站建设远程培训,网站建设实战案例,网络平台代理,重庆秀山网站建设公司#x1f34e;作者简介#xff1a;硕风和炜#xff0c;CSDN-Java领域新星创作者#x1f3c6;#xff0c;保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享#x1f48e;#x1f48e;#x1f48e; #x1f34e;座右… 作者简介硕风和炜CSDN-Java领域新星创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 座右铭人生如棋我愿为卒行动虽慢可谁曾见我后退一步 目录题目链接题目描述求解思路实现代码运行结果DFS求解思路实现代码运行结果记忆化缓存求解思路实现代码运行结果共勉题目链接
剑指 Offer II 112. 最长递增路径 329. 矩阵中的最长递增路径
题目描述
给定一个 m x n 整数矩阵 matrix 找出其中 最长递增路径 的长度。
对于每个单元格你可以往上下左右四个方向移动。 不能 在 对角线 方向上移动或移动到 边界外即不允许环绕。 提示
m matrix.length n matrix[i].length 1 m, n 200 0 matrix[i][j] 231 - 1 求解思路实现代码运行结果
DFS
求解思路
该题目的求解思路比较简单我们直接从给定数组中的每一个位置开始遍历通过DFS的思想找到上、下、左、右中最长的递增路径记录当前位置的最大长度。因为我们遍历的是整个数组从每一个位置开始所以说我们最后还需要比较每一个位置的长度找到最长的即可。
实现代码
实现代码的方式有很多你可以在设计递归的时候将参数放到函数中也可以将参数设置为成员变量都是可以的甚至再求一些值的时候你可以将最后的答案放到参数中当然也可以将每一步的答案都进行返回递归设置相应的返回值。方式有很多大家选择自己最喜欢最熟悉的方式即可。
class Solution {public int longestIncreasingPath(int[][] matrix) {int mmatrix.length,nmatrix[0].length;int maxInteger.MIN_VALUE;for(int i0;im;i){for(int j0;jn;j){maxMath.max(max,process(i,j,m,n,matrix));}}return max;}public int process(int x,int y,int m,int n,int[][] matrix){int upx0matrix[x][y]matrix[x-1][y]?process(x-1,y,m,n,matrix):0;int rightyn-1matrix[x][y]matrix[x][y1]?process(x,y1,m,n,matrix):0;int downxm-1matrix[x][y]matrix[x1][y]?process(x1,y,m,n,matrix):0;int lefty0matrix[x][y]matrix[x][y-1]?process(x,y-1,m,n,matrix):0;return Math.max(Math.max(up,right),Math.max(down,left))1;}
}运行结果
我们可以看到时间超限了不要紧至少证明我们的思路是没有问题的我们可以继续优化嘛。
记忆化缓存
求解思路
我们直接添加一个缓存表避免一个结果会重复产生计算如果我们之前计算过此时直接返回就可以。
实现代码
class Solution {public int longestIncreasingPath(int[][] matrix) {int mmatrix.length,nmatrix[0].length;int[][] dpnew int[m][n];for(int i0;im;i){Arrays.fill(dp[i],-1);}int maxInteger.MIN_VALUE;for(int i0;im;i){for(int j0;jn;j){maxMath.max(max,process(i,j,m,n,matrix,dp));}}return max;}public int process(int x,int y,int m,int n,int[][] matrix,int[][] dp){if(dp[x][y]!-1) return dp[x][y];int upx0matrix[x][y]matrix[x-1][y]?process(x-1,y,m,n,matrix,dp):0;int rightyn-1matrix[x][y]matrix[x][y1]?process(x,y1,m,n,matrix,dp):0;int downxm-1matrix[x][y]matrix[x1][y]?process(x1,y,m,n,matrix,dp):0;int lefty0matrix[x][y]matrix[x][y-1]?process(x,y-1,m,n,matrix,dp):0;return dp[x][y]Math.max(Math.max(up,right),Math.max(down,left))1;}
}运行结果 共勉
最后我想送给大家一句一直激励我的座右铭希望可以与大家共勉
