在 LeetCode 问题上获得 Enclave 数量的 TLE

Question

我遇到了LeetCode问题1020。飞地数量：

给你一个mx n二进制矩阵grid， 其中0代表海洋单元，1代表陆地单元。 移动包括从一个陆地单元步行到另一个相邻的单元 （4 向）陆地单元或走出网格的边界。

返回网格中我们无法行走的陆地单元的数量 在任意次数的移动中离开网格边界。

示例 1：

输入： grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0 ,0,0,0]]
输出： 3
解释：有 3 个 1 被 0 包围， 和一个未封闭的 1，因为它位于边界上。

示例 2：

输入： grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0 ,0,0,0]]
输出： 0
解释：所有 1 要么在边界上，要么可以到达 边界。

我使用 BFS 构建了以下解决方案

class Solution(object):
    def numEnclaves(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """

        stack = []
        visited = set()
    
        row_0 = grid[0]
        row_n = grid[-1]
        col_0 = [row[0] for row in grid]
        col_n = [row[-1] for row in grid]
    
        num_rows = len(grid)
        num_cols = len(grid[0])
    
        for col, val in enumerate(row_0):
            if val == 1:
                stack.append([0, col])
                visited.add((0, col))
            
        for col,val in enumerate(row_n):
            if val == 1:
                stack.append([num_rows-1, col])
                visited.add((num_rows-1, col))
    
        for row, val in enumerate(col_0):
            if val == 1:
                stack.append([row, 0])
                visited.add((row, 0))
    
        for row, val in enumerate(col_n):
            if val == 1:
                stack.append([row, num_cols -1])
                visited.add((row, num_cols -1))
           
        while stack:
            row, col = stack.pop(0)
            visited.add((row, col))
        
            steps = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        
            for _row, _col in steps:
                _row += row
                _col += col
            
                if _row <0 or _row > num_rows -1:
                    continue
                
                if _col <0 or _col > num_cols -1:
                    continue
            
                if (_row, _col) in visited:
                    continue
                
                if grid[_row][_col] == 1:
                    stack.append([_row, _col])
    
        result = 0
        for row in range(1, num_rows-1):
            for col in range(1, num_cols -1):
                if grid[row][col] == 1 and (row,col) not in visited:
                    result += 1
            
        return result
        

我的解决方案对于较小的输入工作正常，但对于较大的值（例如：大小为 200x200 的网格）则失败。我无法理解解决方案中可能导致 TLE 的原因，或者如何进一步优化它？

Answer 1

您的解决方案是使用一个集合来查找节点是否被访问过 - 但这不是必需的，因为您可以简单地在节点上放置一个标记来表示您访问过它。例如，假设 2 代表从现在开始访问：

class Solution2(object):
    def numEnclaves(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """

        stack = []

        num_rows = len(grid)
        num_cols = len(grid[0])

        for row in range(len(grid)):
            if grid[row][0] == 1:
                stack.append((row, 0))
                # 2 means visited from now on
                grid[row][0] = 2

            if grid[row][num_cols - 1] == 1:
                stack.append((row, 0))
                grid[row][num_cols - 1] = 2

        for col in range(len(grid[0])):
            if grid[0][col] == 1:
                stack.append((0, col))
                grid[0][col] = 2

            if grid[num_rows - 1][col] == 1:
                stack.append((0, col))
                grid[num_rows - 1][col] = 2

        while len(stack) != 0:
            row, col = stack.pop(0)

            steps = [[1, 0], [-1, 0], [0, 1], [0, -1]]

            for _row, _col in steps:
                _row += row
                _col += col

                if _row < 0 or _row > num_rows - 1:
                    continue

                if _col < 0 or _col > num_cols - 1:
                    continue

                if grid[_row][_col] == 2:
                    continue

                if grid[_row][_col] == 1:
                    stack.append((_row, _col))
                    grid[_row][_col] = 2

        result = 0
        for row in range(1, num_rows - 1):
            for col in range(1, num_cols - 1):
                if grid[row][col] == 1:
                    result += 1

        return result

时间急剧下降，并且您在问题中给出的测试仍然通过。您应该知道，如果集合大小非常大，则集合访问实际上并不是O(1)。

Answer 2

主要问题是，当您将单元格放入堆栈（实际上是一个队列）时，您不会将单元格标记为已访问。这意味着堆栈将具有重复的单元，从而减慢该过程。

正如其他人提到的，您可以使用网格本身将单元格标记为已访问，但我只会删除您访问的 1（为 0）。最后，您只需对所有单元格值进行求和即可。

其他一些事情：

• 仅定义steps一次，不在循环内；
• 使用sum得到最终的计数；
• 避免在初始队列上放置两次角单元
• 使用运算符链接来检查行和列是否在范围内

建议的代码：

class Solution(object):
    def numEnclaves(self, grid):
        num_rows = len(grid)
        num_cols = len(grid[0])
    
        queue = [
            (0, col) for col, val in enumerate(grid[0]) if val == 1
        ] + [
            (num_rows-1, col) for col,val in enumerate(grid[-1]) if val == 1
        ] + [
            (row+1, 0) for row, val in enumerate(grid[1:-1]) if val[0] == 1
        ] + [
            (row+1, num_cols-1) for row, val in enumerate(grid[1:-1]) if val[-1] == 1
        ]
        for row, col in queue:
            grid[row][col] = 0
        steps = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        while queue:
            row, col = queue.pop(0)        
            for _row, _col in steps:
                _row += row
                _col += col
                if 0 <= _row < num_rows and 0 <= _col < num_cols and grid[_row][_col] == 1:
                    grid[_row][_col] = 0
                    queue.append((_row, _col))

        return sum(sum(grid[row]) for row in range(1, num_rows-1))