合肥做网站建设公司,海外制作网站,如何开通网上商城,做网站主机要选好写在前面#xff1a;
今天我们继续看一道 图论和遍历 相关的题目。这道题目的背景是在一个矩阵当中找寻最长的递增数列长度。思路上非常好想#xff0c;绝对和 DFS 相关#xff0c;但是题目的优化要求非常高#xff0c;对于语言和内存特性的考察特别丰富#xff0c;如果是… 写在前面
今天我们继续看一道 图论和遍历 相关的题目。这道题目的背景是在一个矩阵当中找寻最长的递增数列长度。思路上非常好想绝对和 DFS 相关但是题目的优化要求非常高对于语言和内存特性的考察特别丰富如果是单纯的 Leetcoder 或者是 扎根算法而语言相对专精较弱的同学这道题目可能很难做到 AC就让我们一起来看看吧 题目介绍
题目信息
题目链接https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/题目类型ArrayGraphDFSDynamic Programming(是的可以拿 dp 做但是太难了而且并不具备推广价值所以不分享了)题目难度Hard思路 easy优化要求 hard题目来源Google 高频面试真题
题目问题
给定一个大小为 m * n 的矩阵每一个矩阵的位置都代表一个 value找出最长的 递增遍历行走路线在行走的过程中只能上下左右不能走对角线例子 题目想法
深度优先暴力解法
一看到是走 “最长的递增” 数组并且在图中只能上下左右移动我们很容易可以想到 DFS这也是一个标准的 DFS 问题。我们只需要遍历每一个位置当作起点并且不断寻找周围有没有递增的位置可以让我们前进返回当前起点所能达到的最大值。将所有的最大值统筹起来进行返回。
很可惜思路很美好现实很骨感这样的做法不仅会 TLE而且会 MLE在算法时间复杂度和占用空间内存的角度来讲都会爆炸。
RuntimeO(2^(mn)) -- 我们需要遍历所有可能的子数组
SpaceO(mn) -- 我们最坏需要遍历所有的 node 和 edge并且需要mn次 stack 来储存
太慢也太耗空间了如果懂得堆栈的小伙伴应该知道太多 recursion 会占掉很多内存 时间复杂度优化
暴力解法非常简单想到那 Google 和 其他大厂的要求肯定不止这么一点儿 但如果自己想想我们每一次以一个点为起点进行探索的时候我们的目标都是取得这个点所能创造的最大长度从而决定我们是否有机会获得更好的结果。那我们是否可以利用 Memoization 的方法将每个遍历过后的点的最大值记下来这样之后的重复使用不就都不用再遍历了吗
我们在从每一个点开始遍历 DFS 的时候将所有路过的点的最大值进行一个更新而我们在找寻起点的过程中就可以直接从这些点里取值了因为他一定是最大的。
为什么一定如果一个点被遍历过之后存下的结果一定 我们以这个点为起点重新遍历呢
如果这个点的现有最大值是从本点开始那再来一次遍历也会得到相同结果如果这个点的现有最大值是从一个比他更小的点得来的那以他自己为起点此次结果一定会小于我们所存储的节点因为单调递增的单向性而这个点的现有最大值不可能来自己于一个比他更大的起点所以总结存下的结果 以当前为起点遍历可能最大 --- 当前存储的结果一定是最优的
RuntimeO(mn) --- 我们只需要遍历一次图即可可以被 AC
SpaceO(mn) --- 我们需要存储所有的矩阵点的最大值 内存优化
虽然这道题的 O(mn) 的空间复杂度已经是最优复杂度了但不同的 implementation 同样会导致 AC 和 MLE 的区别题主自己在做这道题的时候经过了算法的优化以后还是 MLE后来经过对数据结构和 recursion 变量的优化才最终解决内存问题这可能也是大厂对代码水平更高难度的考察吧这也是我认为这道题是 hard 的一部分原因
如果使用 C 进行代码编写可以优化的点有
对于数据的存储不使用 vector 而是使用 dynamic array 进行内存分配对于Recursion函数传入的矩阵和记忆矩阵把他们变成 member variable在recursion中静态调用而不是不停的动态参数传入
第一个问题的原因是基于 vector 的特性。在 C中动态数组的内存分布并不是按照有多少个元素来分配的而是分配 2^n 个储存空间n 是让 2^n 大于所需长度的最小值。而这样的分配方式会造成内存浪费。例如一个长度为 7 的 vector 实际上占用了 8 个长度的内存而长度为 9 的 vector 实际上占用了 16 个长度的内存。而如果使用 dynamic allocation在 matrix 长度宽度已知不会变的情况下我们完全可以手动分配内存精准的将 矩阵的维度 分配出来。在 2 个维度同时减少内存浪费省去非常多的空间
第二个问题的原因是没有一次 recursion function call这个函数就会在内存中开辟一段储存空间而如果我们将 矩阵和记忆矩阵作为变量不断传入他们就会不断的在内存 stack 中生成很多很多 copy从而导致 stack 崩掉。而如果我们将其改成 member variable他们相对于所有的 recursion 函数就是全局的每个 recursion 都只需要直接调用他的指针所指的真实数据而不是 copy这也会节省更多空间
在同时完成这两个优化以后相信大家也能成功 AC 这道 Leetcode hard 题目代码
class Solution {
public:int x[4] {0, 1, 0, -1};int y[4] {1, 0, -1, 0};int** maxViewed; //use dynamic array instead of vector to prevent memory wasteint** matrix; //use member variable instead of arguement in recursion to prevent //too much stack memory wasted in recursionint DFS(int i, int j, int m, int n){//we have already seen this point, so need to traverse. if(maxViewed[i][j] ! 0){return maxViewed[i][j];}for(int d 0; d 4; d){int new_i i x[d];int new_j j y[d];//check in bound, no need to check revisit, but have check for increasingif(new_i m new_i 0 new_j n new_j 0){if(matrix[i][j] matrix[new_i][new_j]){maxViewed[i][j] max(DFS(new_i, new_j, m, n), maxViewed[i][j]);}}}maxViewed[i][j] 1;return maxViewed[i][j];}int longestIncreasingPath(vectorvectorint matrix_target) {int maxDist 0;int m matrix_target.size(), n matrix_target[0].size();//create a cache and matrix storage for the traversing:maxViewed new int*[m]; // Allocate memory for rowsmatrix new int*[m];for (int i 0; i m; i) {maxViewed[i] new int[n]; // Allocate memory for columnsmatrix[i] new int[n];}for(int i 0; i m; i){for(int j 0; j n; j){maxViewed[i][j] 0;matrix[i][j] matrix_target[i][j];}}for(int i 0; i m; i){for(int j 0; j n; j){maxDist max(maxDist, DFS(i, j, m, n));}}return maxDist;}
};
