Leetcode 200. 岛屿数量 TLE

Question

Link 问题：https://leetcode.com/problems/number-of-islands/

给定“1”（陆地）和“0”（水）的二维网格地图，计算岛屿的数量。岛屿四面环水，由相邻陆地水平或垂直连接而成。您可以假设网格的所有四个边缘都被水包围。

示例 1：

输入：

输出：1

我的逻辑是简单地从每个节点执行 dfs 并跟踪连接的组件。第 46 个测试用例超出时间限制 (TLE)，有人可以帮我优化这段代码吗？

class 解决方案（对象）：

def numIslands(self, grid):

    def in_grid(x, y):
        return 0 <= x < len(grid) and 0 <= y < len(grid[0])

    def neighbours(node):
        p, q = node
        dir = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        return [(x, y) for x, y in [(p + i, q + j) for i, j in dir] if in_grid(x, y)]

    def dfs(node):
        visited.append(node)
        for v in neighbours(node):
            if grid[v[0]][v[1]]== "1" and v not in visited:
                dfs(v)

    components = 0
    visited = []
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            node = (i, j)
            if grid[i][j] == "1" and node not in visited:
                components += 1
                dfs(node)

    return components

Answer 1

我认为你的做法是正确的。但是，您将 visited 用作 list，它需要 O(n) 来搜索值。所以它的整体时间复杂度是O(N^2)。我建议使用 set 而不是 list 这是一个散列 table.

只有两部分需要修改：

visited = [] -> visited = set()
visited.append(node) ->visited.add(node)

我确认接受了。现在 node not in visited 需要 O(1) 所以总的时间复杂度是 O(N).

% 与大多数其他 LeetCode 问题一样，问题陈述不提供有关输入数据的任何信息。但是由于您的代码是 TLE，因此我们可以假设我们无法用时间复杂度 O(n^2).

来解决它

Answer 2

您获得 TLE 的原因是您使用列表来跟踪访问的节点。在最坏的情况下，在列表中搜索一个值需要 O(n) 时间。

最好将 visited/non-visited 节点的索引状态保持为包含布尔值或 O/1 整数值的二维矩阵。这导致访问时间 O(1) 不变以查找节点的 visited/non-visited 状态。

class Solution {

    boolean isSafe(char[][] grid, int[][] visited, int i, int j)
    {
        int n = grid.length;
        int m = grid[0].length;

        if((i<0 || i>n-1) || (j<0 || j>m-1))
            return false;

        return visited[i][j] == 0 && grid[i][j] == '1';
    }

    void DFS(char[][] grid, int[][] visited, int i, int j)
    {
        visited[i][j] = 1; //marked visited

        int[] row = {-1, 0, 1, 0};
        int[] column = {0, 1, 0, -1};

        for(int k = 0; k<4; k++)
        {
            if(isSafe(grid, visited, i+row[k], j+column[k]))
            {
                DFS(grid, visited, i+row[k], j+column[k]);
            }
        }
    }

    int DFSUtil(char[][] grid)
    {
        int count = 0;

        if(grid == null || grid.length == 0)
            return count;

        int n = grid.length; //rows
        int m = grid[0].length; //columns

        int[][] visited = new int[n][m];

        for(int i = 0; i<n; i++)
            for(int j = 0; j<m; j++)
            {
                if(grid[i][j]=='1' && visited[i][j] == 0)
                {
                    DFS(grid, visited, i, j);
                    count++;
                }
            }

        return count;
    }

    public int numIslands(char[][] grid) {

        int result = DFSUtil(grid);

        return result;
    }
}

Answer 3

我在Java中用DFS的方法解决了，简单易懂。在这里，我的代码可能会对您有所帮助：

public static int numIslands(char[][] grid) {

    int countOfIslands = 0 ;
    for (int i = 0; i <grid.length ; i++) {
        for (int j = 0; j <grid[i].length ; j++) {
            if(grid[i][j] == '1'){
                DFS(grid,i,j);
                countOfIslands++;
            }
        }
    }

    return countOfIslands;

}

public static void DFS(char[][] grid , int row , int col){

    if(grid[row][col] == '0')
        return;

    grid[row][col] = '0';
     //   System.out.println("grid = " + Arrays.deepToString(grid) + ", row = " + row + ", col = " + col);
    if(row+1 < grid.length)
        DFS(grid,row+1,col);
    if(row-1 >=0)
        DFS(grid,row-1,col);
    if(col+1 <grid[0].length)
        DFS(grid,row,col+1);
    if(col-1 >= 0)
        DFS(grid,row,col-1);

}

如果这是您第一次听说图表的 DFS，请参考： DFS Approach

Answer 4

修改后的简单 DFS 解决方案

class Solution {
public int numIslands(char[][] grid) {
    int count = 0;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[i].length; j++) {
            if (grid[i][j] != '0') {
                count++;
                shrink(grid, i, j);
            }
        }
    }
    return count;
}

private void shrink(char[][] grid, int i, int j) {

if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 
'0')
        return;
    
    grid[i][j] = '0';
    shrink(grid, i, j+1);
    shrink(grid, i, j-1);
    shrink(grid, i+1, j);
    shrink(grid, i-1, j);
}
}

Leetcode 200. 岛屿数量 TLE

Leetcode 200. Number of Islands TLE

python

depth-first-search

connected-components