企业官网建设流程全解析

说起 LeetCode 上那些“刷题必遇”的经典题，200. 岛屿数量绝对排得上前五。不管你是准备实习、秋招、春招，还是单纯想把手里的 DFS、BFS 底子打牢，这道题都绕不开。它在 LeetCode 热门 100 题里稳稳占了一个位置，也是各大厂面试里出现频率极高的网格搜索题。

这道题最妙的地方在于：它不考什么高级技巧，也不需要复杂的数学推导，只要你理解“连通分量”这个概念，会写最基础的深度优先或广度优先搜索，就能给出一个面试官认可的标准答案。但反过来，它考察的细节非常多——字符和数字的区分、边界检查的顺序、递归深度带来的栈溢出风险、要不要修改原始数据……每个点都能展开聊一聊。这篇文章我就以自己做这道题的实际经验为主线，把 DFS、BFS、并查集三种思路都拆开揉碎了讲一遍，再把平时容易被忽略的坑全部列出来。

1. 题目本质与破题思路

1.1 题面到底在说什么

题目给你一个二维网格，里面只有两种字符：'1'代表陆地，'0'代表水。岛屿的定义是“被水包围的、连续相邻的陆地区域”。

这里的“相邻”有明确限定：只能是上下左右四个方向，斜对角不算。也就是说，上面是 1、下面是 1、左边是 1、右边是 1 这样连成一片的才叫同一块岛屿。如果只是斜着碰到，算两块独立的岛。

举个最经典的例子，网格是：

11110 11010 11000 00000

左上角那五块 1 全部连在一起，构成一个岛屿。虽然中间有个 0，但 0 只是把右上角的 1 隔开了。右下角的 1 没有与任何其他 1 四方向相邻，所以它是独立的一个岛屿。于是答案就是 2。

另一个例子更直观：

11000 11000 00100 00011

三块互不相连的陆地，答案 3。核心就一句话：数一数整个网格里有几个连通的陆地集团。

1.2 破题核心：把问题转化为连通分量计数

如果你以前接触过图论，其实一眼就能看出来——这个二维网格本质上就是一张图，每个格子是一个节点，上下左右相邻的格子之间有一条边。而岛屿的数量，就是这张图中“值为 1 的节点”构成的连通分量的个数。

连通分量的定义很简单：在一个无向图里，如果若干个节点彼此之间能通过边到达，它们就在同一个连通分量里；互相到不了的，就是不同的分量。放到这个题目里，同一座岛就是同一个连通分量。

所以解题思路就变得很清晰：遍历整个网格，每次遇到一个没访问过的'1'，就说明发现了一个新岛屿，计数器加 1，然后从它出发，把所有跟它相连的'1'全部标记为“已访问”。这样下次遍历到它们时就不会再重复计数。

这个“标记已访问”的动作，可以用深度优先搜索（DFS）做，可以用广度优先搜索（BFS）做，也可以用并查集把所有相邻的 1 合并起来，最后数一数有几个集合。三种方案殊途同归，但各有各的适用场景。

1.3 为什么它是 LeetCode 热搜榜单的常客

说点刷题圈子里大家心照不宣的事：LeetCode 热门 100 题里的题目，几乎每道都对应着一类核心算法范式。像 073 爱吃香蕉的狒狒是二分答案的经典，基本计算器是栈和表达式解析的经典，而 200 岛屿数量就是图论搜索的入门必刷题。

这道题能火这么多年，我真的一点都不意外。它表面上是一道题，实际上承担了三个功能：第一，它是你理解网格类 DFS/BFS 的敲门砖，以后的扫雷游戏、迷宫寻路、腐烂的橘子全都从这个模板延伸出去；第二，它在面试里特别好使，一个候选人会不会写边界检查、能不能分析递归栈、有没有意识到数据污染问题，两三分钟就能看出来；第三，它跟真实世界的很多问题直接挂钩——图像处理里的连通域标记、地图上的湖泊岛屿统计、社交网络里的群组划分，核心都是同一套逻辑。

所以别觉得这题简单就不认真对待，把它的每一个细节吃透，后面的网格题你会走得很顺。

2. DFS：直觉解法的两种实现

2.1 递归写法：三句话搞定主逻辑

DFS 是大多数人看到这道题的第一反应，因为思路最贴合直觉：发现一个岛，就往四面八方扎进去，把能走到的陆地全走一遍，走不动了再回来。

先看完整的 Java 递归解法：

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 count = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == '1') { count++; dfs(grid, i, j); } } } return count; } private void dfs(char[][] grid, int i, int j) { int rows = grid.length; int cols = grid[0].length; if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == '0') { return; } grid[i][j] = '0'; dfs(grid, i - 1, j); dfs(grid, i + 1, j); dfs(grid, i, j - 1); dfs(grid, i, j + 1); } }

主函数里套一个双层循环，碰到'1'就计数加 1，然后调用dfs把这座岛“淹没”。这里的淹没就是把'1'改成'0'，相当于标记已访问。

dfs里的逻辑也简单：先判断越界和当前格子是不是水，如果是就返回；如果当前格子是陆地，立刻把它改成'0'，再往上下左右四个方向递归。

这里有几个细节我必须强调一下。第一，边界检查的顺序很有讲究，i < 0 || i >= rows || j < 0 || j >= cols这个判断必须放在最前面，避免数组越界访问。第二，判断必须是grid[i][j] == '0'而不是grid[i][j] != '1'，虽然在这个题里结果一样，但如果你把输入数据当成整数数组来做就会踩坑，这个我后面专门讲。第三，把当前格子改成'0'一定要在递归之前，这叫“先标记后扩散”，防止在递归过程中重复访问同一个格子，否则会产生死循环。

如果换用 Python，代码更短，核心思路完全一致：

class Solution: def numIslands(self, grid: List[List[str]]) -> int: if not grid: return 0 m, n = len(grid), len(grid[0]) def dfs(i, j): if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == '0': return grid[i][j] = '0' dfs(i - 1, j) dfs(i + 1, j) dfs(i, j - 1) dfs(i, j + 1) ans = 0 for i in range(m): for j in range(n): if grid[i][j] == '1': ans += 1 dfs(i, j) return ans

2.2 递归深度风险：什么情况下必须换显式栈

递归版本够简单，但我要泼一盆冷水：当你真正在刷题平台上提交，或者在实际项目里遇到超大网格时，递归深度可能成为最大的隐患。

这道题目的输入约束通常是 300 × 300 以内，理论上递归深度最多 90000 层。但 Java 默认的虚拟机栈深度通常只有几千到一万多层，Python 的默认递归深度更是只有 1000 层。一旦网格全部是'1'，DFS 一路扎进去可能直接触发StackOverflowError或RecursionError。

我第一次在本地用 Python 跑一个 200 × 200 的全 1 网格时，就遇到了递归深度超限。当时我还以为是代码写错了，排查了半天才发现是递归层数的问题。

所以在面试场景里，如果你主动跟面试官讨论这个问题，说“递归版本思路清晰但存在栈溢出风险，我可以改成显式栈”，这绝对是个加分项。显式栈版本是这样写的：

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 count = 0; int[][] dirs = {{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') { count++; Deque<int[]> stack = new ArrayDeque<>(); stack.push(new int[]{i, j}); grid[i][j] = '0'; while (!stack.isEmpty()) { int[] cur = stack.pop(); for (int[] d : dirs) { int ni = cur[0] + d[0]; int nj = cur[1] + d[1]; if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && grid[ni][nj] == '1') { grid[ni][nj] = '0'; stack.push(new int[]{ni, nj}); } } } } } } return count; } }

注意几个细节：用ArrayDeque当栈比Stack类性能好；每次把新节点压栈前就立刻标记为'0'，而不是弹出时才标记，这是避免重复入栈的关键；方向数组dirs让四个方向的扩展代码变得非常简洁。

实测下来，显式栈在超大网格上的稳定性比递归好得多，代码量增加的也有限。如果你在 LeetCode 上做题，我建议至少动手写一遍这个版本，因为它能帮你真正理解 DFS 的本质——显式栈模拟了系统递归栈的行为。

3. BFS 与变形题实战

3.1 标准 BFS：一层一层地“感染”

DFS 是“一条路走到黑”，BFS 则是“一圈一圈往外扩”。思路同样直接：发现一个陆地'1'，把它作为起点放进队列，然后一层一层地把周围的 1 全部感染成 0，直到队列为空，说明这一整座岛都被处理完了。

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 count = 0; int[][] dirs = {{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') { count++; Queue<int[]> queue = new ArrayDeque<>(); queue.offer(new int[]{i, j}); grid[i][j] = '0'; while (!queue.isEmpty()) { int[] cur = queue.poll(); for (int[] d : dirs) { int ni = cur[0] + d[0]; int nj = cur[1] + d[1]; if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && grid[ni][nj] == '1') { grid[ni][nj] = '0'; queue.offer(new int[]{ni, nj}); } } } } } } return count; } }

从代码结构上看，BFS 版本和显式栈 DFS 版本几乎一模一样，唯一的区别就是把栈换成了队列，把push/pop换成了offer/poll。这一点非常有意思——在网格搜索里，DFS 和 BFS 的骨架是通用的，区别只在于用哪种数据结构来控制遍历顺序。

从性能上说，BFS 不会遇到递归栈溢出问题，而且寻找最短路径类的问题它也更合适。这道题不存在“最短”的概念，所以 DFS 和 BFS 都可，但如果你后续要做 LeetCode 994 腐烂的橘子那种需要计算扩散时间的题，BFS 几乎是标准答案。

3.2 与 994 腐烂的橘子对比：网格 BFS 的通用模板

LeetCode 994 腐烂的橘子跟岛屿数量一样，都属于网格 BFS 的范畴。我把两题放在一起对比，是因为它们解题骨架几乎相同，但有两个关键差异：起始点数量和层数统计方式。

在 994 题里，一开始可能有好几个腐烂的橘子，它们会同时向四周扩散，这叫“多源 BFS”。实现时你需要先遍历一遍整个网格，把所有腐烂的橘子初始状态一次性入队，而不是碰到一个就启动一次搜索。而在 200 题里，每遇到一个未访问的 1 才启动一次 BFS，每次 BFS 对应一座岛屿。

另外 994 题要统计“多少分钟后所有橘子都腐烂”，所以你需要在 BFS 过程中记录层数。常用做法是每次循环时先取size = queue.size()，然后只处理这一层的节点，处理完一层minutes++。这个按层遍历的技巧，后来在二叉树层序遍历、迷宫最短路径等很多题目里都会用到。

这里我整理了一个简表，方便你对照记忆：

把这两道题连着刷一遍，网格 BFS 的底子就非常扎实了。很多刷题指南里把它们排在前后脚，不是没有道理的。

4. 并查集与优化细节

4.1 并查集思路：合并相邻陆地，统计根的数量

DFS 和 BFS 是“染色”的思路，并查集则是“合并”的思路：把所有相邻的'1'通过union操作合并到同一个集合里，最后数一数有多少个集合，答案就是岛屿数量。

我第一次看到并查集解法时，觉得这个思路非常优雅——它不通过搜索去遍历整座岛，而是通过“撮合邻居”的方式把陆地慢慢聚成团。并查集天然支持动态合并，如果以后网格数据是持续更新的，这种方案的优势会非常明显。

实现步骤分三步。第一步，二维坐标转一维编号：index = row * cols + col。第二步，统计网格中'1'的个数作为并查集的初始集合数count。第三步，遍历每个'1'，只看向右边和下面两个邻居（避免重复合并），如果邻居也是'1'就执行union，合并成功则count--。最后返回count。

这里为什么要设置一个虚拟的“水节点”？我先说结论：可以不设，直接统计初始的 1 的数量，然后每成功合并一次就减一。但为了思路统一，很多并查集题解会把所有'0'归到一个虚拟节点上，这样最后统计根节点数量时，忽略虚拟节点即可。不过对于这个题，直接维护count更简洁。

Java 实现如下：

class Solution { private int[] parent; private int[] rank; public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) { return 0; } int rows = grid.length; int cols = grid[0].length; parent = new int[rows * cols]; rank = new int[rows * cols]; int count = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == '1') { int idx = i * cols + j; parent[idx] = idx; count++; } } } for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == '1') { int idx = i * cols + j; if (i + 1 < rows && grid[i + 1][j] == '1') { if (union(idx, (i + 1) * cols + j)) { count--; } } if (j + 1 < cols && grid[i][j + 1] == '1') { if (union(idx, i * cols + j + 1)) { count--; } } } } } return count; } private int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } private boolean union(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) { return false; } if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; } return true; } }

并查集里两个关键操作：find负责查找根节点，这里用了路径压缩，在递归返回时把沿途节点直接指向根，后续查找会越来越快；union负责合并两个集合，这里用了按秩合并，把小树接到大树下，控制整棵树的高度。路径压缩加按秩合并，能让单次操作的时间复杂度降到接近常数级别，整体复杂度可以认为是 O(mn × α(mn))，α是反阿克曼函数，在实际场景中不会超过 4。

空间上需要开两个一维数组，parent和rank，总长度是rows * cols，所以空间复杂度 O(mn)。比 DFS/BFS 多了一些内存，但换来了动态扩展能力。

4.2 空间优化与一个容易被追问的面试细节

这里我想单独聊一个面试里几乎必被追问的点：如果你直接修改了输入网格，把'1'改成'0'，省下了一个visited数组，空间复杂度从 O(mn) 降到了 O(1)，这事到底好不好？

先说结论。在 LeetCode 上这么写完全没问题，还能让代码更简洁。但到了工程环境，直接修改入参往往是大忌——这份网格数据可能是一个地图服务里共享的数据，还有其他模块要读，你为了算岛屿数量把它改空了，别人拿到手的数据就坏了。

所以在面试时我建议你主动说清楚：“我默认允许修改输入，所以直接原地标记。如果业务上不允许污染原始数据，我可以加一个visited布尔数组，区别只是空间换时间。”

这一句话透露出的工程意识，在很多面试官眼里比代码本身还值钱。我在实际项目里处理过类似的数据清洗问题，深知“入参只读不写”这条潜规则有多重要，所以即使在刷题阶段，也建议你养成这个习惯——先把两种方案都说清楚，再根据场景选择。

5. 常见问题与排查技巧实录

5.1 我踩过的五个坑，一次性给你列全

这道题我做过的次数绝对不少了，但每次重新写，还是能在评论区看到有人踩这些坑。我把自己踩过的和看到别人踩过的问题整理成一个速查表，每个都写了排查思路。

第一个坑真的是经典中的经典。LeetCode 给的输入是char[][]，字符'1'的底层 ASCII 码是 49，如果你写成grid[i][j] == 1，它会拿 49 和 1 比，永远不相等，结果整个程序一个岛屿都找不到。我当年第一次用 C++ 刷题时就栽在这上面，排查了快二十分钟才发现是引号的问题。

第五个坑也比较隐蔽。很多人在本地跑小规模测试没问题，一提交就报栈溢出，还以为是 LeetCode 判题系统的问题。其实纯粹就是递归深度超过了语言默认限制。Python 里可以用sys.setrecursionlimit()临时调大，但这属于治标不治本，真正稳妥的还是迭代写法。

5.2 面试现场怎么答才加分

如果说前面讲的是“把题做对”，那这一节讲的就是“把题讲好”。面试跟刷题是两码事，LeetCode 题解里你只要把代码贴出来跑通就行，但面试官需要看到你的思考过程。

开场先说题目本质：把二维网格看作图，岛屿数量就是连通分量数量，所以核心任务变成了“标记已访问”。然后给复杂度分析：时间 O(mn)，因为每个格子最多被访问常数次；空间的话，递归 DFS 最坏 O(mn) 递归栈，BFS 最坏队列也可能到 O(mn)，但如果原地改数组，辅助空间可以做到 O(1)（递归栈除外）。

说完思路以后，主动补充边界情况：空网格返回 0，只有单个格子的网格看它是陆地还是水。再主动提一句“这道题和 994 腐烂的橘子很像，那题是多源 BFS，需要统计层数”，面试官往往就会顺着你的思路追问，这时候你就掌握了对话节奏。

最后一招：用实际场景解释这个算法的意义。图像处理里的连通域标记，就是把每个像素当成格子，统计有多少块颜色相同的区域；地图应用里计算一个湖泊被多少块陆地包围，本质也是网格搜索。能把算法跟真实世界连接起来，说明你是真的理解，而不是背模板。

写在最后：这道题值得做的三个理由

我个人刷题有个习惯，一道题做完之后会问自己：这题值不值得我花时间做第二遍？200 岛屿数量答案是值得，而且我建议你三刷。

第一遍用递归 DFS 建立直觉，第二遍用 BFS 和显式栈 DFS 理解遍历顺序的本质差别，第三遍试试并查集，体会“合并不搜索”的新思路。三遍下来，你不只是会这一道题，而是把网格搜索这一类题的基础彻底打牢了。

另外再分享一个小技巧：做这种网格题，先把方向数组{{1,0},{-1,0},{0,1},{0,-1}}写在最上面，能省掉大量重复的坐标加减代码。我在后来的扫雷、单词搜索、腐烂的橘子、迷宫问题里，都用到了这个习惯，实测下来代码整洁度和出错率都明显改善。

刷题这条路没有捷径，但把经典题吃透，绝对是最省时间的捷径。