Leetcode 岛屿数量

时间：2024-10-14 16:31:34

在这里插入图片描述

  1. 首先检查网格是否为空，如果为空，直接返回 0。
  2. 遍历网格中的每一个元素，当遇到陆地（'1'）时，计数器加 1，并且通过 DFS 将与该陆地相连的所有部分标记为已访问（即设为 '0'）。
  3. DFS 遍历过程中会检查网格的边界条件，如果越界或遇到水（'0'），直接返回。
  4. 通过递归调用，处理当前陆地的上下左右四个方向的相邻部分。

复杂度分析：

  • 时间复杂度：O(M * N)，其中 M 和 N 分别是网格的行数和列数。每个元素最多会被访问一次。
  • 空间复杂度：O(M * N)，递归调用的栈空间最坏情况下可能需要达到整个网格的大小。
class Solution {
    public int numIslands(char[][] grid) {
        //处理边界
        if(grid == null || grid.length == 0) {
            return 0;
        }

        int num_Islands = 0;
        //获取行,列
        int rows = grid.length;
        int cols = grid[0].length;


        for(int i = 0; i < rows; ++i) {
            for(int j = 0; j < cols; ++j) {
                if(grid[i][j] == '1') {
                    num_Islands++;
                }
                // grid[i][j] = '0'; 不能在这里更新标记格子
                dfs(grid, i, j);
            }
        }
        return num_Islands;
    }
    private void dfs(char[][] grid, int i, int j) {
        
        //首先提供递归出口
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') {
            return;
        }

        grid[i][j] = '0'; // 统一在dfs里置'0'标记格子,

        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
}

该算法 2 个注意点

这个算法有两个核心注意点，必须严格遵守才能保证算法的正确性：

1. 在 dfs() 中统一标记格子，而不能在进入 dfs() 之前标记格子：

  • 原因：标记格子（即将当前格子从 '1' 变为 '0'，表示它已被访问）是为了避免重复访问和无休止的递归。如果在进入 dfs() 之前就标记为 '0'，那么在 dfs() 内，递归扩展时会发现该格子已经是 '0'，导致相邻的陆地没有被正确处理，最终导致算法计算的岛屿数量错误。
  • 做法：应在 dfs() 内部执行标记操作，这样可以确保递归时只标记尚未访问的格子，并在遍历整个岛屿时正确处理相邻陆地。
private void dfs(char[][] grid, int i, int j) {
    grid[i][j] = '0'; // 统一在进入递归时标记为已访问
    // 继续向四个方向扩展
}

2. 需要根据递归出口来设计 if 判断条件，而不是在满足可以更新标记格子时作为 if 判断条件：

  • 递归出口的核心作用：递归必须有明确的终止条件，否则会陷入无限递归，导致栈溢出或程序崩溃。在这道题中，递归出口应该是非法或无效的格子（如越界或水域 '0'），这样我们可以在递归扩展时及时返回，防止无效递归。

  • 错误的做法：如果根据“满足可以更新格子”的条件来设计 if，你会导致没有明确的递归出口。递归将会继续向无效的格子（越界或水域）扩展，而没有办法终止。

  • 正确的做法：递归出口条件应该是“不满足继续递归”的条件，比如：越界或当前格子是水（'0'）。一旦遇到这些情况，立刻终止递归，并返回。这确保了递归只在有效的陆地格子上进行。

// 如果越界或遇到水域（'0'），直接返回，作为递归出口
if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == '0') {
    return;
}

综上所述：

  • 统一标记：必须在 dfs() 函数内部统一进行标记操作，而不能在调用 dfs() 之前。
  • 递归出口：if 判断条件应该根据递归出口设计（即当遇到无效格子时终止），而不是根据满足更新格子来设计。递归只有在非法或无效情况下才会终止，确保算法正常工作。

这样，整个算法能够正确地处理网格中的岛屿，计算岛屿的数量不会出现错误或陷入无限递归。

相关文章