LeetCode刷题之HOT100之岛屿数量

2024 6/27 酷暑难耐，天气热了，似乎更容易午睡了。上午上了cnn最后一节课。睡一觉买一杯蜜雪冰城，坐在舒适的实验室敲击键盘，做题！

1、题目描述

2、逻辑分析

是的，又是直奔题解的一天哈！题解给出三种求解方案：深度优先搜索、广度优先搜索以及并查集。我们只看DFS就可以啦。
算法思想主要是利用了深度优先搜索（DFS）来遍历二维网格，并找出所有的“岛屿”（由 ‘1’ 组成的连续区域）。算法的基本步骤如下：
初始化：
定义一个二维字符数组 grid，其中 ‘1’ 表示陆地（或岛屿的一部分），‘0’ 表示水域。
初始化一个计数器 num_islands 为 0，用于记录岛屿的数量。
遍历网格：
使用两个嵌套的循环遍历整个网格 grid。
在遍历过程中，如果当前位置是 ‘1’（即陆地），则表示找到了一个新的岛屿。
深度优先搜索（DFS）：
当找到一个新的岛屿（即 ‘1’）时，调用 dfs 函数进行深度优先搜索。
dfs 函数会首先将当前位置的陆地标记为水域（即改为 ‘0’），以避免重复访问。
然后，它会递归地调用自身，搜索当前位置的上、下、左、右四个方向，继续寻找与该岛屿相连的其他陆地。
递归调用会持续进行，直到所有与该岛屿相连的陆地都被标记为水域。
计数：
在每次找到一个新的岛屿（即 ‘1’）时，将 num_islands 计数器加 1。
由于 dfs 函数会确保一个岛屿的所有陆地都被标记为水域，因此同一个岛屿不会被重复计数。
返回结果：
遍历完整个网格后，返回 num_islands 的值，即岛屿的数量。

3、代码演示

// 深度优先搜索函数，用于标记和遍历一个岛屿的所有陆地  
    void dfs(char[][] grid, int i, int j){
        // 获取网格的行数和列数
        int nr = grid.length, nc = grid[0].length;
        // 如果当前位置超出网格边界或者已经是水域（'0'），则直接返回 
        if(i < 0 || j < 0 || i >= nr || j >= nc || grid[i][j] == '0'){
            return ;
        }

        // 将当前位置的陆地标记为水域（'0'），表示已经访问过 
        grid[i][j] = '0';
        // 递归地访问当前位置的上方、下方、左方和右方，继续深度优先搜索
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);

    }

    // 主函数，用于计算岛屿的数量
    public int numIslands(char[][] grid) {
        // 如果网格为空或者没有行，则直接返回0
        if(grid == null || grid.length == 0){
            return 0;
        }

        // 获取网格的行数和列数
        int nr = grid.length, nc = grid[0].length;
        int num_islands = 0;
        // 遍历网格的每一个位置
        for(int i = 0; i < nr; i++){
            for(int j = 0; j < nc; j++){
                // 如果当前位置是陆地（'1'）
                if(grid[i][j] == '1'){
                    // 岛屿数量加1
                    num_islands++;
                    // 使用深度优先搜索遍历并标记当前岛屿的所有陆地 
                    dfs(grid, i, j);
                }

            }
        }
        // 返回岛屿数量
        return num_islands;
        
    }

4、复杂度分析

• 时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。
• 空间复杂度：O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN。

ok，做完啦，还有广度优先搜索和并查集就不做啦，看看就好！拜拜，又要去上课了。