牛客网刷题-岛屿数量_0表示海洋 1表示陆地

问题描述

给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。

示例

示例1

输入
[[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]]

输出
3

解决思路

分析

1. 遍历数组，将相邻的岛屿的置为1（可以通过dfs或bfs的方式），然后继续判断。

方法

1. dfs：从一个为1的根节点开始访问，从每个相邻1节点向下访问到顶点（周围全是水），依次访问其他相邻1节点到顶点
2. bfs：为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。直到队列为空，搜索结束。

代码实现

dfs

// 思路1
public class Solution {  
    void dfs(char[][] grid, int r, int c) {
        int len = grid.length;
        int len1 = grid[0].length;

        if (r < 0 || c < 0 || r >= len || c >= len1 || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    public int numIslandsByDFS(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int len = grid.length;
        int len1 = grid[0].length;
        int numIslands = 0;
        for (int r = 0; r < len; ++r) {
            for (int c = 0; c < len1; ++c) {
                if (grid[r][c] == '1') {
                    ++numIslands;
                    dfs(grid, r, c);
                }
            }
        }

        return numIslands;
    }
}
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

时间复杂度分析：
O(MN)：遍历二维数组

空间复杂度分析：
O(MN)：这里的空间复杂度主要是针对递归的深度，最坏的情况下，二维数组都是1，则需要一直递归完整个二维数组

bfs

// 思路2
public class Solution {  
    public int numIslandsByBFS(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int len = grid.length;
        int len1 = grid[0].length;
        int numIslands = 0;

        for (int r = 0; r < len; ++r) {
            for (int c = 0; c < len1; ++c) {
                if (grid[r][c] == '1') {
                    ++numIslands;
                    grid[r][c] = '0';
                    Queue<Integer> neighbors = new LinkedList<>();
                    neighbors.add(r * len1 + c);
                    while (!neighbors.isEmpty()) {
                        int id = neighbors.remove();
                        int row = id / len1;
                        int col = id % len1;
                        if (row - 1 >= 0 && grid[row - 1][col] == '1') {
                            neighbors.add((row - 1) * len1 + col);
                            grid[row - 1][col] = '0';
                        }
                        if (row + 1 < len && grid[row + 1][col] == '1') {
                            neighbors.add((row + 1) * len1 + col);
                            grid[row + 1][col] = '0';
                        }
                        if (col - 1 >= 0 && grid[row][col - 1] == '1') {
                            neighbors.add(row * len1 + col - 1);
                            grid[row][col - 1] = '0';
                        }
                        if (col + 1 < len1 && grid[row][col + 1] == '1') {
                            neighbors.add(row * len1 + col + 1);
                            grid[row][col + 1] = '0';
                        }
                    }
                }
            }
        }

        return numIslands;
    }
} 
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
41
42
43
44
45
46

时间复杂度分析：
O(MN)：遍历二维数组

空间复杂度分析：
O(min(M,N))：在最坏情况下，整个网格均为陆地，队列的大小可以达到 min(M,N)。

小伙伴如果想测试的话，可以直接到牛客网这个链接做测试

岛屿数量-牛客网