扬中富裕吗,seo技术自学,软文写作兼职,金融企业网站建设文章目录1. 题目2. 解题2.1 记忆化递归2.2 拓扑排序1. 题目
给定一个整数矩阵#xff0c;找出最长递增路径的长度。
对于每个单元格#xff0c;你可以往上#xff0c;下#xff0c;左#xff0c;右四个方向移动。 你不能在对角线方向上移动或移动到边界外#xff08;即…
文章目录1. 题目2. 解题2.1 记忆化递归2.2 拓扑排序1. 题目
给定一个整数矩阵找出最长递增路径的长度。
对于每个单元格你可以往上下左右四个方向移动。 你不能在对角线方向上移动或移动到边界外即不允许环绕。
示例 1:
输入: nums
[[9,9,4],[6,6,8],[2,1,1]
]
输出: 4
解释: 最长递增路径为 [1, 2, 6, 9]。示例 2:
输入: nums
[[3,4,5],[3,2,6],[2,2,1]
]
输出: 4
解释: 最长递增路径是 [3, 4, 5, 6]。
注意不允许在对角线方向上移动。来源力扣LeetCode 链接https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
2.1 记忆化递归
class Solution {int m, n;int longest 1;vectorvectorint dir {{-1,0},{1,0},{0,1},{0,-1}};
public:int longestIncreasingPath(vectorvectorint mat) {if(mat.empty() || mat[0].empty())return 0;m mat.size(), n mat[0].size();vectorvectorint s(m, vectorint(n,0));for(int i 0, j; i m; i)for(j 0; j n; j){if(s[i][j] ! 0)//走过的路不走continue;longest max(longest, dfs(i,j,mat,s));}return longest;}int dfs(int i, int j, vectorvectorint mat, vectorvectorint s){if(s[i][j] ! 0)return s[i][j];int x, y, k, longestpathofnext 0;for(k 0; k 4; k){x i dir[k][0];y j dir[k][1];if(x0 xm y0 yn mat[i][j] mat[x][y]){longestpathofnext max(longestpathofnext, dfs(x,y,mat,s));}}return s[i][j] 1longestpathofnext;}
};76 ms 14.1 MB
2.2 拓扑排序
见官方解答
找到周围点比我小的入度1统计一遍入度为0的全部入队列BFS的最大层数为最长路径长度 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
