Python 递归问题 (Leetcode 542)

Question

我想我误解了Python中的一些重要概念，而且它不是特定于 Leetcode 问题。我非常感谢深入了解 Python 的人提供的任何帮助。

Leetcode 542 是给定一个仅由 0 和 1 组成的二维数组，对于每个 1，找到到达 0 的最短距离。我有一个虚拟 DFS 解决方案：

  class Solution:
    def updateMatrix(self, matrix):
     
      dists = []
      for _ in range(len(matrix)):
          dists.append([0]*len(matrix[0]))
    
      for y in range(len(matrix)):
          for x in range(len(matrix[0])):
              if matrix[y][x] == 1:
                  self.min_dist = len(matrix)+len(matrix[0])
                  self.DFS(x, y, matrix, 0, set({}))
                  dists[y][x] = self.min_dist
                
      return dists

    def DFS(self, x, y, matrix, distance, visited):
    
      if (x, y) in visited or (matrix[y][x] == 1 and distance > self.min_dist): return
    
      if matrix[y][x] == 0:
          print (x, y, "d:", distance)
          print ('------')
          self.min_dist = min(self.min_dist, distance)
          return 
    
      print (x, y, distance)
    
      visited.add((x, y))
    
      if x > 0 and (x-1, y) not in visited: 
          self.DFS(x-1, y, matrix, distance+1, visited)
        
      if y > 0 and (x, y-1) not in visited: 
          self.DFS(x, y-1, matrix, distance+1, visited)
   
      if x < len(matrix[0])-1 and (x+1, y) not in visited: 
          self.DFS(x+1, y, matrix, distance+1, visited)
   
      if y < len(matrix)-1 and (x, y+1) not in visited: 
          self.DFS(x, y+1, matrix, distance+1, visited)

简单地DFS直到达到0。每次我们调用DFS，distance + 1。我觉得不错。但是测试用例 input = [[1,0,0],[0,1,1],[1,1,1]] 给了我 dist = [[1,0,0],[0,1,1],[1,2,3]].

如果把上面的代码matrix[y][x] == 1改成matrix[y][x] == 1 and x==2 and y==2和运行，输出就是

 2 2 0
 1 2 1
 0 2 2
 0 1 d: 3
 ------
 1 1 2
 0 1 d: 3
 ------
 1 0 d: 3
 ------
 2 1 3
 2 0 d: 4
 ------

在(x,y)=(2,1)处初始距离改为3。但在(2,1)处的初始距离应该是1。我的问题是为什么它会改变？谁能帮我指出我哪里做错了？谢谢！

Answer 1

你真的不需要递归。您可以简单地将需要更新其邻居的位置排队并保持 updating/queuing 个位置，直到不再进行更新：

def getDistances(matrix):
    rows,cols = len(matrix),len(matrix[0])
    maxDist   = rows*cols+1 # start 1's at maximum distance
    result    = [[maxDist*bit for bit in row] for row in matrix]
    more      = { (r,c) for r,row in enumerate(matrix)
                        for c,bit in enumerate(row) if bit == 0}
    while more: # process queue starting with zero positions
        r,c     = more.pop()
        newDist = result[r][c]+1 # neighbours are at distance+1 from here
        for nr,nc in [(r,c+1),(r,c-1),(r+1,c),(r-1,c)]: # 4 directions
            if nr not in range(rows): continue
            if nc not in range(cols): continue            
            if newDist >= result[nr][nc]: continue 
            result[nr][nc] = newDist  # reduce neighbour's distance
            more.add((nr,nc))         # queue neighbour to cascade updates
    return result

输出：

m = [[0,0,0,0,0,1],
     [0,1,1,0,0,0],
     [1,1,1,1,0,1],
     [1,1,1,1,1,0]]

for r in getDistances(m): print(r)
                  
[0, 0, 0, 0, 0, 1]
[0, 1, 1, 0, 0, 0]
[1, 2, 2, 1, 0, 1]
[2, 3, 3, 2, 1, 0]

Answer 2

一直在看这个。问题似乎出在 visited 集的修改方式上。我认为它是通过引用传递的，这意味着当它尝试去 (2,2) -> (2,1) 时，该集合已经包含点 (2,1)，即前面的 DFS 路径已将所有点添加到它。

我发现这篇文章很好地解释了“Python 中的按引用传递”- https://realpython.com/python-pass-by-reference/。

我让你的测试用例一直通过 visited.copy()，即 self.DFS(x-1, y, matrix, distance+1, visited.copy())。我不是 Python 专家，想象一下有更简洁的方法来处理这个问题。

Answer 3

首先我想指出的是，DFS和BFS一样，主要用于在树中搜索；实际上，您可以将您的矩阵视为一棵特定的树，但我不会为此任务走这条路，因为您不需要 search 而是 keep相对于所有邻居 parents 和 children.
追踪一段距离此外，使用 DFS，您将需要多次遍历矩阵以找到每个 1s 的最小值，这是非常低效的。

关于您的问题，如果您跟踪正在创建的堆栈，您将得到：

 2 2 0
 1 2 1
 0 2 2
 0 1 d: 3
 ------
 back to (0, 2), with distance = 2
 (1, 2) already visited
 back to (1, 2) with distance = 1
 1 1 2
 0 1 d: 3
 ------
 back to (1, 1) with distance = 2
 1 0 d: 3
 ------
 back to (1, 1) with distance = 2
 2 1 3
 2 0 d: 4

回到你的任务，因为你正在使用 python 我会使用 numpy 来解决这个任务，并寻找 1s 和 0s 使用np.where(matrix == 0)。那就是做一些微积分的问题了：

import numpy as np


class Solution:

    def update_matrix(self, matrix):
        matrix = np.array(matrix)

        x_ones, y_ones = np.where(matrix == 1)
        x_zeros, y_zeros = np.where(matrix == 0)

        for i in range(len(x_ones)):
            temp = []

            for j in range(len(x_zeros)):
                temp.append(abs(x_ones[i] - x_zeros[j]) + abs(y_ones[i] - y_zeros[j]))

            matrix[x_ones[i], y_ones[i]] = min(temp)

        return matrix.tolist()

如果您一定不要使用外部库，请按以下步骤操作：

class Solution:

    def update_matrix(self, matrix):
        x_ones, y_ones = [], []
        x_zeros, y_zeros = [], []

        # First scan to save coordinates
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 1:
                    x_ones.append(i)
                    y_ones.append(j)
                else:
                    x_zeros.append(i)
                    y_zeros.append(j)

        for i in range(len(x_ones)):
            temp = []

            for j in range(len(x_zeros)):
                temp.append(abs(x_ones[i] - x_zeros[j]) + abs(y_ones[i] - y_zeros[j]))

            matrix[x_ones[i]][y_ones[i]] = min(temp)

        return matrix

Python 递归问题 (Leetcode 542)

Python Recursion Issue (Leetcode 542)

python

recursion

depth-first-search