长大后想做什么？做回小孩！

0%

LeetCode——岛屿数量

发表于 分类于 Valine：
本文字数： 195

NO.200 岛屿数量 中等

JQ9t81.png

思路一：广搜 遍历找到一块陆地(1)就将计数器+1，并用广搜将与这块陆地相邻的所有的陆地都找到进行沉岛(都置为0)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int count = 0;//计数器
public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return count;
    //遍历
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            //找到陆地就将计数器+1，并将当前陆地所属岛屿上的所有陆地全部置为0
            if (grid[i][j] == '1') {
                //广搜
                bfs(grid, i, j);
                count++;
            }
        }
    }
    return count;
}

private void bfs(char[][] grid, int i, int j) {
    int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{i, j});
    grid[i][j] = '0';
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int k = 0; k < size; k++) {
            int[] poll = queue.poll();
            //四个方向搜索，是陆地就置为0
            for (int l = 0; l < 4; l++) {
                int diri = poll[0] + directions[l][0];
                int dirj = poll[1] + directions[l][1];
                if (diri>=0&&diri<grid.length&&
                    dirj>=0&&dirj<grid[0].length&&
                    grid[diri][dirj] == '1') {
                    grid[diri][dirj] = '0';
                    queue.add(new int[]{diri, dirj});
                }
            }
        }
    }
}

时间复杂度：O(n) 最坏情况两次遍历，主方法中找陆地遍历一次，广搜遍历一次。

思路二：深搜 和广搜的想法一样，区别是遍历找到陆地之后的沉岛过程采用深搜实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int count = 0;
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return count;
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                count++;
            }
        }
    }
    return count;
}

private void dfs(char[][] grid, int i, int j) {
    grid[i][j] = '0';
    for (int k = 0; k < 4; k++) {
        int diri = i + directions[k][0];
        int dirj = j + directions[k][1];
        if (diri >= 0 && diri < grid.length &&
            dirj >= 0 && dirj < grid[0].length &&
            grid[diri][dirj] == '1') {
            dfs(grid, diri, dirj);
        }
    }
}

时间复杂度：O(n) 最坏情况两次遍历。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github