Leetcode BFS 集合插入给出 TLE（200。岛屿数量）

Question

我正在尝试解决问题：Leetcode 上使用 BFS 遍历的岛屿数量 当我尝试在循环中首先在访问集中添加 (r,c) 对时，它在 Leetcode 中给出了 TLE。

上述代码：

def numIslands(self, grid: List[List[str]]) -> int:
        islands = 0
        rows, cols = len(grid), len(grid[0])
        visited = set()

        def bfs(r, c):
            q = [(r,c)]
            while q:
                row, col = q.pop(0)
                visited.add((row, col))  ## This line causes TLE
                directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
                for dr, dc in directions:
                    r = row + dr
                    c = col + dc
                    if (r in range(rows) and
                        c in range(cols) and
                        grid[r][c] == "1" and
                        (r,c) not in visited):
                        q.append((r,c))

        for r in range(rows):
            for c in range(cols):
                if (r,c) not in visited and grid[r][c] == "1":
                    bfs(r,c)
                    islands += 1
        return islands

如果我在循环的 if 块中添加 (r,c)，代码就会通过。

def numIslands(self, grid: List[List[str]]) -> int:
        islands = 0
        rows, cols = len(grid), len(grid[0])
        visited = set()

        def bfs(r, c):
            q = [(r,c)]
            visited.add((r, c)) #Visited the current (r,c)
            while q:
                row, col = q.pop(0)
                # visited.add((row, col)) ## Commented this out
                directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
                for dr, dc in directions:
                    r = row + dr
                    c = col + dc
                    if (r in range(rows) and
                        c in range(cols) and
                        grid[r][c] == "1" and
                        (r,c) not in visited):
                        q.append((r,c))
                        visited.add((r, c)) ## visited in the if-block

        for r in range(rows):
            for c in range(cols):
                if (r,c) not in visited and grid[r][c] == "1":
                    bfs(r,c)
                    islands += 1
        return islands

我不明白，为什么第二个版本的代码正在通过并且更加优化，队列无论如何都会有 grid[r][c] == "1" 的元素，或者队列只会有陆地元素。

Answer 1

在代码的第一个版本中，单元格仅在从队列中弹出后才被标记为已访问。这可能会导致在弹出第一次出现的同一单元格之前，将其许多副本添加到队列中。这会导致更多的浪费迭代。

另一方面，代码的第二个版本更加惯用，并且在第一次到达单元格时将其标记为已访问并将其添加到队列中。这确保了到同一单元的其他路径不会将该单元的无用副本添加到队列中。

还要注意，删除列表的第一个元素很慢；您不应该使用列表来替代实际的队列数据结构。使用

collections.deque

，您的第一个解决方案也应该通过。