时间戳

首页 > 解决方案 > 循环总是从 0,0 开始 - 试图解决“矩阵中最长的增加路径”。我没看到什么？

python - 循环总是从 0,0 开始 - 试图解决“矩阵中最长的增加路径”。我没看到什么？

问题描述

我一直在努力解决这个 leetcode 问题：https ://leetcode.com/problems/longest-increasing-path-in-a-matrix/

我的代码在这里：https ://pastebin.com/QBcXrbJa

问题基本上是要求给定矩阵的最长“路径”。我已经添加了我期望的代码想要的

我们在solver()里面有一个isValid函数来检查

如果它检查出来，numPath（计算路径长度的变量）会增加，我们将节点添加到visited，并继续检查它周围的所有节点

然而....

  1. 我得到一个不正确的输出（例如，矩阵 [[9,9,4],[6,6,8],[2,1,1]] 输出 2 而不是预期的输出 4）

  2. 从我的调试代码中，我注意到前 4 个访问的始终是 (0,0)，即使我们不是从 (0, 0) 开始

例如，在 main 函数中，我们有

    for rowKey in range(0, matrixR):
        for colKey in range(0, matrixC):
            longest.append(
                solver(matrix, rowKey, colKey, matrixR, matrixC, matrix[rowKey][colKey])
            )

这应该改变代码的开始位置，但这并没有反映在调试代码中

调试输出

Row: 0 - Col: 0 - RowMax: 3 - ColMax: 3 - currVal: 9 - numPath: 0 - visited: []
Row: 1 - Col: 0 - RowMax: 3 - ColMax: 3 - currVal: 9 - numPath: 1 - visited: [(0, 0)]
Row: -1 - Col: 0 - RowMax: 3 - ColMax: 3 - currVal: 9 - numPath: 1 - visited: [(0, 0)]        
Row: 0 - Col: 1 - RowMax: 3 - ColMax: 3 - currVal: 9 - numPath: 1 - visited: [(0, 0)]
Row: 0 - Col: -1 - RowMax: 3 - ColMax: 3 - currVal: 9 - numPath: 1 - visited: [(0, 0)]        
Row: 0 - Col: 1 - RowMax: 3 - ColMax: 3 - currVal: 9 - numPath: 0 - visited: [(0, 0)]
Row: 1 - Col: 1 - RowMax: 3 - ColMax: 3 - currVal: 9 - numPath: 1 - visited: [(0, 0), (0, 1)] 
Row: -1 - Col: 1 - RowMax: 3 - ColMax: 3 - currVal: 9 - numPath: 1 - visited: [(0, 0), (0, 1)]
Row: 0 - Col: 2 - RowMax: 3 - ColMax: 3 - currVal: 9 - numPath: 1 - visited: [(0, 0), (0, 1)]
Row: 0 - Col: 0 - RowMax: 3 - ColMax: 3 - currVal: 9 - numPath: 1 - visited: [(0, 0), (0, 1)]
Row: 0 - Col: 2 - RowMax: 3 - ColMax: 3 - currVal: 4 - numPath: 0 - visited: [(0, 0), (0, 1)]
Row: 1 - Col: 2 - RowMax: 3 - ColMax: 3 - currVal: 4 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2)]
Row: 2 - Col: 2 - RowMax: 3 - ColMax: 3 - currVal: 8 - numPath: 2 - visited: [(0, 0), (0, 1), (0, 2), (1, 2)]
Row: 0 - Col: 2 - RowMax: 3 - ColMax: 3 - currVal: 8 - numPath: 2 - visited: [(0, 0), (0, 1), (0, 2), (1, 2)]
Row: 1 - Col: 3 - RowMax: 3 - ColMax: 3 - currVal: 8 - numPath: 2 - visited: [(0, 0), (0, 1), (0, 2), (1, 2)]
Row: 1 - Col: 1 - RowMax: 3 - ColMax: 3 - currVal: 8 - numPath: 2 - visited: [(0, 0), (0, 1), (0, 2), (1, 2)]
Row: -1 - Col: 2 - RowMax: 3 - ColMax: 3 - currVal: 4 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2)]
Row: 0 - Col: 3 - RowMax: 3 - ColMax: 3 - currVal: 4 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2)]
Row: 0 - Col: 1 - RowMax: 3 - ColMax: 3 - currVal: 4 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2)]
Row: 1 - Col: 0 - RowMax: 3 - ColMax: 3 - currVal: 6 - numPath: 0 - visited: [(0, 0), (0, 1), (0, 2), (1, 2)]
Row: 2 - Col: 0 - RowMax: 3 - ColMax: 3 - currVal: 6 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0)]
Row: 0 - Col: 0 - RowMax: 3 - ColMax: 3 - currVal: 6 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0)]
Row: 1 - Col: 1 - RowMax: 3 - ColMax: 3 - currVal: 6 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0)]
Row: 1 - Col: -1 - RowMax: 3 - ColMax: 3 - currVal: 6 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0)]
Row: 2 - Col: -1 - RowMax: 3 - ColMax: 3 - currVal: 8 - numPath: 2 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1)]
Row: 0 - Col: -1 - RowMax: 3 - ColMax: 3 - currVal: 8 - numPath: 2 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1)]
Row: 1 - Col: 0 - RowMax: 3 - ColMax: 3 - currVal: 8 - numPath: 2 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1)]
Row: 1 - Col: -2 - RowMax: 3 - ColMax: 3 - currVal: 8 - numPath: 2 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1)]
Row: 1 - Col: 1 - RowMax: 3 - ColMax: 3 - currVal: 6 - numPath: 0 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1)]
Row: 2 - Col: 1 - RowMax: 3 - ColMax: 3 - currVal: 6 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1)]
Row: 0 - Col: 1 - RowMax: 3 - ColMax: 3 - currVal: 6 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1)]
Row: 1 - Col: 2 - RowMax: 3 - ColMax: 3 - currVal: 6 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1)]
Row: 1 - Col: 0 - RowMax: 3 - ColMax: 3 - currVal: 6 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1)]
Row: 1 - Col: 2 - RowMax: 3 - ColMax: 3 - currVal: 8 - numPath: 0 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1)]
Row: 2 - Col: 0 - RowMax: 3 - ColMax: 3 - currVal: 2 - numPath: 0 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1)]
Row: 3 - Col: 0 - RowMax: 3 - ColMax: 3 - currVal: 2 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1), (2, 0)]
Row: 2 - Col: 1 - RowMax: 3 - ColMax: 3 - currVal: 2 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1), (2, 0)]
Row: 2 - Col: -1 - RowMax: 3 - ColMax: 3 - currVal: 2 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1), (2, 0)]
Row: 2 - Col: 1 - RowMax: 3 - ColMax: 3 - currVal: 1 - numPath: 0 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1), (2, 0)]
Row: 3 - Col: 1 - RowMax: 3 - ColMax: 3 - currVal: 1 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1), (2, 0), (2, 1)]
Row: 1 - Col: 1 - RowMax: 3 - ColMax: 3 - currVal: 1 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1), (2, 0), (2, 1)]
Row: 2 - Col: 2 - RowMax: 3 - ColMax: 3 - currVal: 1 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1), (2, 0), (2, 1)]
Row: 2 - Col: 0 - RowMax: 3 - ColMax: 3 - currVal: 1 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1), (2, 0), (2, 1)]
Row: 2 - Col: 2 - RowMax: 3 - ColMax: 3 - currVal: 1 - numPath: 0 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1), (2, 0), (2, 1)]
Row: 3 - Col: 2 - RowMax: 3 - ColMax: 3 - currVal: 1 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1), (2, 0), (2, 1), (2, 2)]
Row: 1 - Col: 2 - RowMax: 3 - ColMax: 3 - currVal: 1 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1), (2, 0), (2, 1), (2, 2)]
Row: 2 - Col: 3 - RowMax: 3 - ColMax: 3 - currVal: 1 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1), (2, 0), (2, 1), (2, 2)]
Row: 2 - Col: 1 - RowMax: 3 - ColMax: 3 - currVal: 1 - numPath: 1 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1), (1, 1), (2, 0), (2, 1), (2, 2)]
2

我的问题是什么？

标签： pythonmatrixdata-structuresdepth-first-searchmemoization

解决方案

有两个主要问题： 每次在 main 中调用求解器时，访问的坐标数组都不会重置。查看您的调试输出，访问的数组只会随着每一行变大。

isValid 函数不验证坐标是否低于矩阵。您可以在此处看到 row 和 col 值两次变为负值：

Row: 1 - Col: -2 - RowMax: 3 - ColMax: 3 - currVal: 8 - numPath: 2 - visited: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 0), (1, -1)]

推荐阅读