时间戳

首页 > 解决方案 > Leetcode 200. 岛屿数 TLE

python - Leetcode 200. 岛屿数 TLE

问题描述

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

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

示例 1：

输入：

11110
11010
11000
00000

输出：1

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

类解决方案（对象）：

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

标签： pythondepth-first-searchconnected-components

解决方案

我通过 DFS 方法在 Java 中解决了它，它简单易懂。在这里，我的代码可以帮助你：

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 方法

推荐阅读