这是 2020 年 7 月 26 日的每日一题。经历了一大堆动态规划后,终于迎来了新题型。图的搜索。新知识,保存一下。

题目

给定一个整数矩阵,找出最长递增路径的长度。

对于每个单元格,你可以往上,下,左,右四个方向移动。 你不能在对角线方向上移动或移动到边界外(即不允许环绕)。

示例 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]。注意不允许在对角线方向上移动。

思路

拿到这道题,先把矩阵换成有向图,其中两点之间有从 AB 的边当且仅当 A B 相邻且 B 大于 A。如下图:

N1@X@1YQK3$HUT}WDB)K9G.png

于是问题就转变为了寻找有向图的最长路径。
并且因为路径条件是单调递增,所以这个有向图不可能有回路。

对于这种在无回路有向图中寻找最长道路的题,有两种做法,广搜和深搜,一起来看下吧。

深度优先搜索 + 记忆化 - DFS

对于这道题深搜还是很好理解的,首先思考朴素法。朴素法就是最简单的以每个点作为起点遍历所有道路,并找出最长的一条。

对朴素法进行优化。我们发现对每一个点来说,以该点为起点的最长路径长度是唯一的。并且图没有回路。所以我们可以新开一个矩阵来将以该点为起点的最长路径长度保存下来。

记忆化深度优先搜索还是比较好理解的,这里直接上代码:

  • 语言:C++
class Solution {

    vector<pair<int,int>> next_v = {{0,1},{0,-1},{1,0},{-1,0}};

public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return 0;
        }
        vector<vector<int>> visit(matrix.size(),vector<int>(matrix[0].size(),0));
        int result = 0;
        for(int i = 0 ; i < matrix.size() ; i ++){
            for(int j = 0 ; j < matrix[0].size() ; j++){
                result = max(result, dfs(i,j,matrix,visit));
            }
        }
        return result;
    }

    int dfs(int i, int j, vector<vector<int>>& matrix, vector<vector<int>>& visit){
        if(visit[i][j] != 0){
            return visit[i][j];
        }
        visit[i][j] = 1;
        for(auto next: next_v){
            int newI = i+next.first;
            int newJ = j+next.second;
            if (newI >= 0 && newI < matrix.size() && newJ >= 0 && newJ < matrix[0].size()){
                if(matrix[newI][newJ] > matrix[i][j]){
                    visit[i][j] = max(visit[i][j], dfs(newI, newJ, matrix, visit)+1);
                }
            }
        }
        return visit[i][j];
    }
};

这里使用了一个 next 点集来建立一个点四周点的对应关系。这种思路可以学习,在很多图的题目中会用到这个技巧。

广度优先搜索 + 拓扑排序 - BFS

还是先思考朴素法,以所有点为起始点进行广度优先搜索,直到没有路可以走了。当前广度优先的层数就是最长的道路数。

朴素法是肯定会超时的,所以还是得考虑优化。广搜的话因为搜索到一个点的时候以这个点为起点的最长路径还是未知的,所以广搜没办法使用深搜那样的记忆化。

这里采用一种 拓扑排序 的思路。

首先补充一个 入度 的定义:有向图中一个点的入度数为以这个点为终点的边的个数。最直观的就是看这个点有几个箭头伸进去,它的入度就为几。

首先,最长道路起点的 入度 一定是 0 这点应该很好理解。所以我们可以将当前可能的起点先找出来,然后删除该点,注意,删除一个点后,与他连接的边都要删掉。也就是有其他的点 入度 减少了,此时我们在 入度 减少的点中寻找 入度0 的点,再次进行广搜。直到没有点 入度0 时,此时广度搜索的层数就是最长道路长度。

听起来有点绕,来看例子:

22A9QHYPO5{C~NKNHQ%Q9.png

首先找出 入度0 的点:(绿色的点)

G~2E77343UAP1U3KW{TXA6V.png

然后删除 入度0 的点,此时来到第一层:

6~75%X`AFM)852BBK5SYYGC.png

再找出 入度0 的点:(绿色的点)

0U7JJTW7U~731X_@0(A~10.png

删除 入度0 的点,此时来到第二层:

@}6_AT0)7ONF6O)2KGEC@QP.png

再找出 入度0 的点:(绿色的点)

K6XE}L_WJQD96%ML29BE.png

删除 入度0 的点,此时来到第三层:

FDG2HW}D9RRE2NP9S_`U4PF.png

再找出 入度0 的点:(绿色的点)

V6E($5KC67O8YH`)2FD2%0.png

删除 入度0 的点,此时来到第四层:

@}EF$`FR(OF8UK4M95IB.png

此时已经没有 入度0 的点了,所以最终结果是层数,也就是 4

来看动图:

GIF 2020-7-26 星期日 15-35-14.gif

讲完了思路,接下来是代码了,偶先建立一个 入度矩阵 建立点和 入度 的关系,然后就可以利用 队列 这样一种结构了,值得注意的是,队列里的值需要存三个,其中两个是当前点的坐标还有一个是当前层数。上代码:

  • 语言:C++
class Solution {

    vector<pair<int,int>> next_v = {{0,1},{0,-1},{1,0},{-1,0}};

public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return 0;
        }
        vector<vector<int>> intoDegrees(matrix.size(),vector<int>(matrix[0].size(),0));
        int plies = 0;
        queue<pair<pair<int,int>,int>> queue;
        for(int i = 0 ; i < matrix.size() ; i ++){
            for(int j = 0 ; j < matrix[0].size() ; j ++){
                int intoDegree = 0;
                for(auto next: next_v){
                    int newI = i+next.first;
                    int newJ = j+next.second;
                    if (newI >= 0 && newI < matrix.size() && newJ >= 0 && newJ < matrix[0].size()){
                        if(matrix[newI][newJ] < matrix[i][j] ){
                            intoDegree ++;
                        }
                    }
                }
                intoDegrees[i][j] = intoDegree;
            }
        }
        for(int i = 0 ; i < matrix.size() ; i ++){
            for(int j = 0 ; j < matrix[0].size() ; j ++){
                if (intoDegrees[i][j] == 0){
                    queue.push({{i,j},plies});
                }
            }
        }
        while (!queue.empty()){
            int i = queue.front().first.first;
            int j = queue.front().first.second;
            plies = queue.front().second;
            queue.pop();
            for(auto next: next_v){
                int newI = i+next.first;
                int newJ = j+next.second;
                if (newI >= 0 && newI < matrix.size() && newJ >= 0 && newJ < matrix[0].size()){
                    if(matrix[newI][newJ] > matrix[i][j] ){
                        intoDegrees[newI][newJ] --;
                        if (intoDegrees[newI][newJ] == 0){
                            queue.push({{newI,newJ},plies+1});
                        }
                    }
                }
            }
        }
        return plies+1;
    }
};

这里同样使用了 next 点集的技巧。
注意在计算 入度 的时候,是按照箭头的反方向,所以要周围的点小于该点时,该点 入度+1,而在后面广度搜索的时候,删除点后是按照箭头方向的点 入度 -1 ,所以这里是判断周围的点要大于该点。

其实这里还有一种思路,可以采用 出度 来进行拓扑排序,因为从小到大的最长路径长度也就是从大到小最长路径的长度。所以我们可以从道路终点开始 拓扑排序 ,即按照 出度,这样的好处是代码里判断大小的时候不用一会大于一会小于。不过这种应该不是问题,这里就不放出来了。

后记

相比于 广度优先搜索+记忆化深度优先搜素+拓扑排序 要更加灵活,也没有用到递归,但同时后者也更加难想出来。可以说各有千秋吧。

其实这种思路可以解决很多的问题。比如有一种修课程的问题,规定哪些课程一定要在哪些课程之前修,问你拿到最多学分的方法(每门课学分一样)。也是可以转化为类似的有向图最长路径的问题。之后有时间在整理吧。

文章目录