使用Javascript做算法题（四）Longest Increasing Path in a Matrix

发表于 | 分类于

前言

  • 最近在LeetCode上做出了第一道难度为hard的题：) 觉得这题中规中矩挺不错的，mark一下：题目地址

题目描述

  • 给出一个正整数矩阵，找出其中最长的递增路径的长度。只能上下左右移动，不能走对角线，不能环绕重复路线，不能超越边距。
    1
    2
    3
    4
    5
    6
    7
    8
    举例：
    输入:
    nums = [
      [9,9,4],
      [6,6,8],
      [2,1,1]
    ]
    返回 最长路径为4 路径为：1->2->6->9

解题思路

  • 基本思路分以下几个点：
  • 0.依次遍历输入的矩阵(二维数组)，找出每个点作为起点时的最长递归路径长度，然后返回其中的最大值
  • 1.使用dfs递归方法去遍历查找各个方向，建立一个表示移动方向的数组，每次dfs查找一个新的节点是遍历这个数组，得出最大值作为这个点为起点的最长路径，保存到dp中
  • 2.新建一个二维数组作为dp数组，每次得到一个坐标点为起点的最大长度时存入dp数组相应位置，以后再查找到这个坐标点时直接返回之前保存的值避免重复运算
  • 上面可能说的有点乱，大概就是dfs遍历和dp数组结合，难度其实并不算大，但是可以优化的细节还是挺多的，下面代码附有具体注释

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * @param {number[][]} matrix
 * @return {number}
 */
var longestIncreasingPath = function(matrix) {
    if (!matrix || matrix.length === 0) {
        return 0
    }
          
    var direct = [[0, -1], [0, 1], [-1, 0], [1, 0]] // 方向数组
    var max = 1 // 全局最大值
    var dp = new Array() // dp二维数组，保存每个点作为起点的最大路径长度
    var width = matrix[0].length
    var deep = matrix.length
    while (deep) { 
        dp.push(new Array(width).fill(0)) // 每个点初始长度为0，dfs遍历到不为0的情况直接返回她的值(因为是之前已经得到了)
        deep--
    }
    deep = matrix.length
    
    var dfs = function (i, j) {
        if (dp[i][j] > 0) return dp[i][j];
        var mx = 1
        for (var k = 0; k < direct.length; k++) {
            var x = i + direct[k][0]
            var y = j + direct[k][1]
            if (x < 0 || x >= deep || y < 0 || y >=width) { // 超过范围跳过
                continue
            }
            if (matrix[x][y] <= matrix[i][j]) {// 不是递增跳过
                continue
            }
            var len = dfs(x, y) + 1
            mx = Math.max(mx, len)
        }
        dp[i][j] = mx
        return mx
    }
    for (var i = 0; i < deep; i++) {
        for (var j = 0; j < width; j++) {
            max = Math.max(max, dfs(i, j))
        }
    }
    return max
};