[leetcode 329]Longest Increasing Path in a Matrix 原创解法

发表于 更新于

题目概述

原题链接

Given an integer matrix, find the length of the longest increasing path 
From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

example:
nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]
return 4

回溯法

首先想到的就是回溯法(backtracking)。思路也很简单，就是遍历每个位置， 并以此位置的数字作为开始，向四个方向进行回溯遍历。最终找到最长的序列。 以下代码的36行和38行进行回溯。不过毫无疑问超时了。在这个基础上还可以 进一步优化，比如只对in-degree为0的位置的数字进行考察。但是还是不行。

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
47
48
class Solution(object):
    def longestIncreasingPath(self, matrix):
        """
        回溯法解法。
        :type matrix: List[List[int]]
        :rtype: int
        """

        if matrix:
            hight = len(matrix)
            width = len(matrix[0])

            s = set((u, v) for u in range(hight) for v in range(width))

            result = [0]
            for item in s:
                p = [item]
                self.find(matrix, item, p, result, s)

            return result[0]

        else:
            return 0

    def find(self, matrix, item, p, result, s):
        if self.has_no_choice(matrix, item, p, s):
            if (len(p) > result[0]):
                result[0] = len(p)
        else:
            u, v = item
            four = [(u + 1, v), (u - 1, v), (u, v + 1), (u, v - 1)]
            for one in four:
                x, y = one
                if (x, y) in s and (x, y) not in p and matrix[x][y] < matrix[u][v]:
                    p.append((x, y))
                    self.find(matrix, (x, y), p, result, s)
                    p.pop()

    def has_no_choice(self, matrix, item, p, s):
        u, v = item
        four = [(u + 1, v), (u - 1, v), (u, v + 1), (u, v - 1)]

        for one in four:
            x, y = one
            if one in s and one not in p and matrix[x][y] < matrix[u][v]:
                return False

        return True

拓扑排序和记忆体

看看leetcode会给我们什么提示呢？点开show tags可以看到这个问题的标签， Topological Sort和Memoization。既然使用topsort那么肯定要把这个问题 转化为DAG问题了。如此一来，令人想到，可以先把矩阵数字使用topsort排成 一排，然后再利用曾经遇到的求解最长递增子序列的动态规划算法进行求解。 以下是实现的代码，拓扑排序加动态规划。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class Solution(object):
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """

        if matrix:
            hight = len(matrix)
            width = len(matrix[0])

            s = set((u, v) for u in range(hight) for v in range(width))
            G = self.create_graph(matrix, s)
            topsort_list = self.topsort(G)
            result = self.find_longest_path(G, topsort_list)
            return result

        else:
            return 0

    def create_graph(self, matrix, s):
        G = {}
        for item in s:
            u, v = item
            G[item] = set()
            center = matrix[u][v]
            four = [(u + 1, v), (u - 1, v), (u, v + 1), (u, v - 1)]
            for one in four:
                if one in s:
                    x, y = one
                    adjacent = matrix[x][y]
                    if center > adjacent:
                        G[item].add(one)
        return G

    def tr(self, G):
        H = {}
        for u in G:
            H[u] = 0

        for u in G:
            for v in G[u]:
                H[v] += 1
        return H

    def topsort(self, G):

        H = self.tr(G)
        q = deque()
        sorted_list = []
        for u in H :
            if H[u] == 0 :
                q.append(u)
        while q:
            u = q.popleft()
            sorted_list.append(u)
            for v in G[u]:
                H[v] -= 1
                if H[v] == 0 :
                    q.append(v)

        return sorted_list

    def find_longest_path(self, G, topsort_list):
        n = len(topsort_list)

        memo = [1] * n
        for i in range(1, n):
            node = topsort_list[i]
            value = 0
            for pre in range(0, i):
                pre_node = topsort_list[pre]
                if node in G[pre_node]:
                    value = max(value, memo[pre] + 1)
                else:
                    value = max(value, memo[pre])
            memo[i] = value

        result = max(memo)
        #print(memo)
        return result

进一步优化

上边的解法还是超时了，时间不会消耗在topsort上，因为这个方法是O(|V|+|E|)的。 主要的时间花在了动态规划上，因为这是一个O(N^2)的算法。 我们仔细看看第72到76行这个内循环，发现遍历所有当前节点之前的节点是无效的。 因为可以进入当前节点的节点不会超过４个。所以我们可以修改一下这个内循环。

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
def tr2(self, G):
    H = {}
    for u in G:
        H[u] = set()

    for u in G:
        for v in G[u]:
            H[v].add(u)
    return H

def find_longest_path(self, G, topsort_list):
    n = len(topsort_list)

    dic = { node : 1 for node in topsort_list }
    H = self.tr2(G)

    s = {topsort_list[0]}
    for i in range(1, n):
        node = topsort_list[i]
        s.add(node)
        value = 1
        for pre_node in H[node] :
            if pre_node in s :
                value = max(value, dic[pre_node] + 1)
        dic[node] = value

    result = max(dic.values())
    return result

这里我们在１６行使用一个dict来代替之前的memo， 这样就可以把一个O(N^2)改成一个O(N)的了。 测试一下，幸运的通过了。不过只打败了1.7%。