岛屿数量

1. 问题描述和示例

问题描述

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1
解释：左上角的连通区域形成一个岛屿

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3
解释：有三个独立的岛屿

示例 3：

输入：grid = [
  ["1","0","1","1","1"],
  ["1","0","1","0","1"],
  ["1","1","1","0","1"]
]
输出：1
解释：所有的'1'通过某种路径相连，形成一个岛屿

2. 核心难点分析

主要难点

1. 连通性判断：如何判断相邻的陆地属于同一个岛屿
2. 避免重复计算：已经访问过的陆地不能重复计算
3. 边界处理：处理网格边界，避免数组越界
4. 遍历策略：选择合适的遍历方法（DFS/BFS/并查集）

关键要点

• 岛屿由相邻的'1'组成（上下左右四个方向）
• 需要标记已访问的节点避免重复计算
• 每找到一个未访问的'1'就开始一次完整的岛屿探索
• 探索过程中将整个岛屿的所有'1'都标记为已访问

3. 多种解法对比

解法一：深度优先搜索（DFS）

• 思路：遇到'1'就开始DFS，将整个岛屿标记为已访问
• 优点：代码简洁，容易理解
• 缺点：递归深度可能很大，存在栈溢出风险

解法二：广度优先搜索（BFS）

• 思路：使用队列进行层次遍历，逐层扩展岛屿
• 优点：避免栈溢出，空间使用更可控
• 缺点：需要额外的队列空间

解法三：并查集（Union-Find）

• 思路：将相邻的'1'合并到同一个集合中
• 优点：适合动态添加/删除操作
• 缺点：实现复杂，对于静态问题有些过度设计

4. 详细Java代码实现

解法一：深度优先搜索（DFS）

public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int rows = grid.length;
        int cols = grid[0].length;
        int numIslands = 0;
        
        // 遍历整个网格
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 发现未访问的陆地，开始DFS
                if (grid[i][j] == '1') {
                    numIslands++;
                    dfs(grid, i, j);
                }
            }
        }
        
        return numIslands;
    }
    
    /**
     * 深度优先搜索，将整个岛屿标记为已访问
     * @param grid 网格
     * @param row 当前行
     * @param col 当前列
     */
    private void dfs(char[][] grid, int row, int col) {
        int rows = grid.length;
        int cols = grid[0].length;
        
        // 边界检查和访问检查
        if (row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] != '1') {
            return;
        }
        
        // 标记当前节点为已访问
        grid[row][col] = '0';
        
        // 递归访问四个方向的相邻节点
        dfs(grid, row - 1, col); // 上
        dfs(grid, row + 1, col); // 下
        dfs(grid, row, col - 1); // 左
        dfs(grid, row, col + 1); // 右
    }
}

解法二：广度优先搜索（BFS）

import java.util.*;

public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int rows = grid.length;
        int cols = grid[0].length;
        int numIslands = 0;
        
        // 四个方向的偏移量
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    numIslands++;
                    
                    // BFS遍历整个岛屿
                    Queue<int[]> queue = new LinkedList<>();
                    queue.offer(new int[]{i, j});
                    grid[i][j] = '0'; // 标记为已访问
                    
                    while (!queue.isEmpty()) {
                        int[] current = queue.poll();
                        int row = current[0];
                        int col = current[1];
                        
                        // 检查四个方向
                        for (int[] dir : directions) {
                            int newRow = row + dir[0];
                            int newCol = col + dir[1];
                            
                            // 边界检查和访问检查
                            if (newRow >= 0 && newRow < rows && 
                                newCol >= 0 && newCol < cols && 
                                grid[newRow][newCol] == '1') {
                                
                                queue.offer(new int[]{newRow, newCol});
                                grid[newRow][newCol] = '0'; // 标记为已访问
                            }
                        }
                    }
                }
            }
        }
        
        return numIslands;
    }
}

解法三：并查集（Union-Find）

public class Solution {
    class UnionFind {
        int count;
        int[] parent;
        int[] rank;
        
        public UnionFind(char[][] grid) {
            count = 0;
            int m = grid.length;
            int n = grid[0].length;
            parent = new int[m * n];
            rank = new int[m * n];
            
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == '1') {
                        parent[i * n + j] = i * n + j;
                        ++count;
                    }
                    rank[i * n + j] = 0;
                }
            }
        }
        
        public int find(int i) {
            if (parent[i] != i) {
                parent[i] = find(parent[i]); // 路径压缩
            }
            return parent[i];
        }
        
        public void union(int x, int y) {
            int rootx = find(x);
            int rooty = find(y);
            if (rootx != rooty) {
                // 按秩合并
                if (rank[rootx] > rank[rooty]) {
                    parent[rooty] = rootx;
                } else if (rank[rootx] < rank[rooty]) {
                    parent[rootx] = rooty;
                } else {
                    parent[rooty] = rootx;
                    rank[rootx] += 1;
                }
                --count;
            }
        }
        
        public int getCount() {
            return count;
        }
    }
    
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int rows = grid.length;
        int cols = grid[0].length;
        UnionFind uf = new UnionFind(grid);
        
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == '1') {
                    for (int[] dir : directions) {
                        int newRow = i + dir[0];
                        int newCol = j + dir[1];
                        if (newRow >= 0 && newRow < rows && 
                            newCol >= 0 && newCol < cols && 
                            grid[newRow][newCol] == '1') {
                            uf.union(i * cols + j, newRow * cols + newCol);
                        }
                    }
                }
            }
        }
        
        return uf.getCount();
    }
}

5. 测试用例和预期结果

测试用例

public class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        // 测试用例1：单个大岛屿
        char[][] grid1 = {
            {'1','1','1','1','0'},
            {'1','1','0','1','0'},
            {'1','1','0','0','0'},
            {'0','0','0','0','0'}
        };
        System.out.println("测试用例1结果: " + solution.numIslands(grid1)); // 预期输出：1
        
        // 测试用例2：多个独立岛屿
        char[][] grid2 = {
            {'1','1','0','0','0'},
            {'1','1','0','0','0'},
            {'0','0','1','0','0'},
            {'0','0','0','1','1'}
        };
        System.out.println("测试用例2结果: " + solution.numIslands(grid2)); // 预期输出：3
        
        // 测试用例3：全是水
        char[][] grid3 = {
            {'0','0','0'},
            {'0','0','0'},
            {'0','0','0'}
        };
        System.out.println("测试用例3结果: " + solution.numIslands(grid3)); // 预期输出：0
        
        // 测试用例4：全是陆地
        char[][] grid4 = {
            {'1','1','1'},
            {'1','1','1'},
            {'1','1','1'}
        };
        System.out.println("测试用例4结果: " + solution.numIslands(grid4)); // 预期输出：1
        
        // 测试用例5：单行单列
        char[][] grid5 = {{'1'}};
        System.out.println("测试用例5结果: " + solution.numIslands(grid5)); // 预期输出：1
        
        // 测试用例6：复杂形状
        char[][] grid6 = {
            {'1','0','1','1','1'},
            {'1','0','1','0','1'},
            {'1','1','1','0','1'}
        };
        System.out.println("测试用例6结果: " + solution.numIslands(grid6)); // 预期输出：1
    }
}

6. 边界情况处理

关键边界情况

1. 空网格：grid为null或长度为0
2. 全是水：网格中没有'1'
3. 全是陆地：整个网格都是'1'
4. 单个元素：1x1的网格
5. 单行或单列：特殊形状的网格
6. 边界岛屿：位于网格边缘的岛屿

边界处理技巧

// 输入验证
if (grid == null || grid.length == 0) {
    return 0;
}

// 边界检查函数
private boolean isValid(char[][] grid, int row, int col) {
    return row >= 0 && row < grid.length && 
           col >= 0 && col < grid[0].length && 
           grid[row][col] == '1';
}

7. 相关题目

类似题目

1. 695. 岛屿的最大面积：求最大岛屿的面积
2. 463. 岛屿的周长：计算岛屿的周长
3. 130. 被围绕的区域：处理被包围的区域
4. 417. 太平洋大西洋水流问题：水流问题的变种
5. 1020. 飞地的数量：统计无法到达边界的陆地
6. 1254. 统计封闭岛屿的数目：统计完全被水包围的岛屿

题目关联

• 都属于图的连通性问题
• 都可以用DFS/BFS/并查集解决
• 都涉及二维网格的遍历
• 岛屿数量是这类问题的基础

8. 复杂度分析

时间复杂度

• DFS方法：O(M×N)，其中M和N分别是网格的行数和列数
• BFS方法：O(M×N)，每个节点最多访问一次
• 并查集方法：O(M×N×α(M×N))，α是阿克曼函数的反函数

空间复杂度

• DFS方法：O(M×N)，最坏情况下递归栈深度为M×N
• BFS方法：O(min(M,N))，队列中最多存储min(M,N)个元素
• 并查集方法：O(M×N)，需要额外的parent和rank数组

最优解选择

推荐使用DFS方法，因为：

• 代码最简洁
• 时间复杂度最优
• 空间复杂度在平均情况下较好
• 最容易理解和实现

9. 面试要点总结

核心考点

1. 图的遍历：DFS和BFS的应用
2. 连通性问题：如何判断和处理连通区域
3. 状态标记：如何避免重复访问
4. 边界处理：数组越界的预防

面试回答要点

1. 问题分析：这是一个典型的连通性问题
2. 方法选择：推荐DFS，简单高效
3. 算法步骤：遍历网格，遇到'1'就DFS标记整个岛屿
4. 优化考虑：可以考虑原地修改避免额外空间
5. 扩展思考：讨论相关的变种问题

常见面试问题

• 为什么选择DFS而不是BFS？
• 如何避免栈溢出？
• 能否不修改原数组？
• 如何处理动态添加/删除操作？

10. 性能优化技巧

优化策略

1. 原地修改：直接修改原数组，节省空间
2. 提前终止：在某些情况下可以提前结束
3. 方向数组：使用方向数组简化代码
4. 迭代DFS：使用栈实现DFS避免递归

迭代DFS实现

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    
    int rows = grid.length, cols = grid[0].length;
    int count = 0;
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == '1') {
                count++;
                
                // 使用栈实现迭代DFS
                Stack<int[]> stack = new Stack<>();
                stack.push(new int[]{i, j});
                
                while (!stack.isEmpty()) {
                    int[] curr = stack.pop();
                    int row = curr[0], col = curr[1];
                    
                    if (row < 0 || row >= rows || col < 0 || col >= cols || 
                        grid[row][col] != '1') {
                        continue;
                    }
                    
                    grid[row][col] = '0';
                    
                    // 添加四个方向的邻居
                    stack.push(new int[]{row-1, col});
                    stack.push(new int[]{row+1, col});
                    stack.push(new int[]{row, col-1});
                    stack.push(new int[]{row, col+1});
                }
            }
        }
    }
    
    return count;
}

性能对比

方法	时间复杂度	空间复杂度	代码复杂度	推荐度
递归DFS	O(M×N)	O(M×N)	简单	⭐⭐⭐⭐⭐
迭代DFS	O(M×N)	O(M×N)	中等	⭐⭐⭐⭐
BFS	O(M×N)	O(min(M,N))	中等	⭐⭐⭐⭐
并查集	O(M×N×α)	O(M×N)	复杂	⭐⭐⭐

总结

岛屿数量是图论中连通性问题的经典代表，核心在于：

1. 理解连通性的概念
2. 掌握DFS/BFS遍历技巧
3. 正确处理边界和重复访问
4. 选择合适的算法实现

这道题是很多图论问题的基础，掌握了岛屿数量的解法，就能轻松应对相关的变种问题。建议重点掌握DFS解法，并理解其他方法的优缺点。