【忍者算法】一杯咖啡时间，带你玩转LeetCode热题：LeetCode 200 岛屿数量

👋 大家好，我是忍者算法。今天我们要聊的这道题，在谷歌、微软、字节的面试中经常出现。它不只是考察代码能力，更是在测试你对搜索算法的理解深度。

🎯 从一张旧地图说起

想象一下，你正在研究一张古老的藏宝图：

• 蓝色的海水中散落着若干座岛屿
• 每座岛屿都由若干块相连的陆地组成
• 你需要数清楚到底有多少座独立的岛屿

这不就是今天要解决的算法题吗？

💡 问题的本质

LeetCode 200题"岛屿数量"是这样描述的：

输入一个由 '1'（陆地）和 '0'（水）组成的二维网格
要求计算网格中岛屿的数量（岛屿是由相邻陆地单元组成的区域）

示例：
输入：
[
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]
输出：3

🤔 看起来简单？等等，这里有几个关键点：

1. 什么算"相邻"？（上下左右四个方向）
2. 如何避免重复计算同一个岛屿？
3. 如何高效地探索整个地图？

🎨 绘画给我们的启发

想象你在给这张地图上色：

• 发现一块陆地，就用红色笔把它涂掉
• 顺着这块陆地，把所有相连的陆地都涂红
• 完成后，又发现新的未涂色的陆地，换个颜色继续...

每换一次颜色，就代表发现了一座新岛屿！这就是深度优先搜索（DFS）的思想。

⚡ 代码实现：深度优先搜索

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int islandCount = 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') {
                    islandCount++;  // 岛屿数量+1
                    exploreIsland(grid, i, j);  // 探索整座岛屿
                }
            }
        }
        
        return islandCount;
    }
    
    // 探索整座岛屿的每个角落
    private void exploreIsland(char[][] grid, int row, int col) {
        // 边界检查
        if (row < 0 || row >= grid.length || 
            col < 0 || col >= grid[0].length || 
            grid[row][col] != '1') {
            return;
        }
        
        // 标记已访问（把陆地"淹没"）
        grid[row][col] = '2';  // 或者用'0'，这里用'2'更直观
        
        // 向四个方向探索
        exploreIsland(grid, row-1, col);  // 上
        exploreIsland(grid, row+1, col);  // 下
        exploreIsland(grid, row, col-1);  // 左
        exploreIsland(grid, row, col+1);  // 右
    }
}

🔍 解法要点解析

就像探索一座未知的岛屿：

1. 发现陆地就开始探索
2. 把探索过的地方标记一下（防止迷路）
3. 向四个方向继续探索
4. 直到这座岛屿探索完毕
5. 寻找下一座未探索的岛屿

📊 复杂度分析

时间复杂度：O(M × N)

• M 和 N 是地图的行数和列数
• 每个格子最多被访问一次

空间复杂度：O(M × N)

• 最坏情况：整个地图都是陆地
• 递归调用栈的深度可能达到 M × N

🎯 面试官最爱追问

1. Q：如何处理超大地图？ A：可以考虑分块处理，或使用广度优先搜索（BFS）减少栈空间

2. Q：如果不能修改输入数组呢？ A：可以用额外的visited数组记录访问状态

3. Q：如何计算最大岛屿面积？ A：只需在DFS时统计每个岛屿的面积即可

💡 举一反三

这个解题思路还可以用在：

• 封闭岛屿的数量
• 最大岛屿面积
• 岛屿的周长
• 不同岛屿的数量

🎁 思考题

如果要求每座岛屿必须是正方形才计数，怎么修改代码？

示例：
1 1 1    这个算一座岛
1 1 1    （3×3的正方形）
1 1 1

1 1 1    这个不算
1 1 1    （非正方形）
1 1 0

如果你知道答案？请在评论区留言～

---

作者：忍者算法
公众号：忍者算法

📚 回复【刷题清单】获取完整的hot100题目系列解析
👥 回复【加群】加入算法/面试交流群，一起学习进步 🧑‍💻 回复【代码】获取GitHub完整题解项目，包含Java/Python/JavaScript/Go/C++多语言实现

#算法面试 #LeetCode #搜索算法 #面试高频题