每次机考刷题到“图论/搜索”这一块LeetCode 200“岛屿数量”基本是绕不开的题目。很多人看到“岛屿数量”觉得简单DFS一套就完事实际上机考环境下翻车的比例相当高。我见过不少候选人代码思路是对的但一跑测试就出问题重复计数、死循环、数组越界、甚至输入读取都出错。这篇文章把这道题彻底拆开从三种解法到机考细节再到变体题和面试追问尽量一次讲透。不管你是刷题计划排在第10天还是第100天遇到它这篇都能帮你少走几个弯路。1. 看懂题目之前先把两个容易错的理解纠正过来1.1 二维网格里的“连接”到底怎么定义题目给的输入是一个m x n的二维字符数组里面只有1陆地和0水。要统计的是“岛屿数量”所谓岛屿就是上下左右四个方向连在一起的1组成的连通块。需要特别注意斜对角方向不算连接。比如下面这个 2x2 网格1 0 0 1这里有两个岛屿而不是一个。很多人在白板上画图时会习惯性把对角也连起来这就是第一处容易出错的地方。面试或者机考时如果题目里没有明确说明“四连通”一定要开口确认一句或者自己在代码注释里写清楚“上下左右四个方向”。1.2 题目的核心考点不是“搜索”而是“标记”这道题的搜索本身很简单——遍历每一个格子遇到一个没访问过的1就把整块连通区域全部找出来计数器加一。真正的难点在于怎么保证同一个岛屿不会被重复计数。解决思路有两个方向一是额外开一个visited二维数组走过就标记二是直接在原数组上把访问过的陆地改成0这种“走一个沉一个”的做法有个形象的说法叫“沉没法”。我推荐机考时用沉没法因为它省掉了visited数组的初始化、判断和内存开销代码也更短。所以这道题的本质可以概括成一句话遍历 标记二者缺一不可。只遍历不标记同一个1会被重复遍历无数次直接死循环。2. DFS解法机考时的首选写法以及四个一次过的细节2.1 思路讲给面试官听的一分钟版本DFS深度优先搜索是最直观的解法。给面试官讲思路时我会用这个版本我遍历整个网格每当遇到一个没有被访问过的1我就认为发现了一个新岛屿然后把岛屿数量加一。接下来从这个格子的四个方向递归搜索把所有相邻的1全部标记成已访问避免后续重复计数。这段表述里有三个关键词遍历所有格子、遇到1就计数、递归标记连通区域。把这三句话说清楚面试官就知道你理解到位了。复杂度方面每个格子最多被访问一次所以时间复杂度是O(m * n)。空间复杂度是递归栈的深度最坏情况下整个网格都是陆地递归深度会达到m * n所以最坏是O(m * n)。2.2 Java版本的DFS实现我直接给出一个可以一次通过的版本class Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0 || grid[0].length 0) { return 0; } int m grid.length; int n grid[0].length; int count 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); } } } return count; } 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(grid, i - 1, j); dfs(grid, i 1, j); dfs(grid, i, j - 1); dfs(grid, i, j 1); } }很多人的写法和我这个很像但细节上有几个差异。注意我的边界判断是放在递归函数开头而且先判断越界再访问数组元素。如果把grid[i][j] 0写在前面i 已经越界时就会抛出数组下标异常。这个顺序问题在笔试里特别常见。2.3 四个细节决定你能不能一次过第一个细节字符别写错。判断的是1和0这是字符 char 类型不是数字 1 和 0。写grid[i][j] 1不会报编译错误但永远匹配不上最终结果会是 0。这个坑看似低级但机考紧张时真的有人会犯。第二个细节沉没操作的时机。grid[i][j] 0要在进入递归之前就执行也就是在 dfs 函数体的开头。如果你先递归四个方向最后再置为0递归过程中相邻格子还会反向访问回当前格子造成重复遍历极端情况下会栈溢出。正确的做法是“先沉没再扩散”。第三个细节空输入判断。有的测试用例会给你grid []如果没做判空grid[0]这行代码会直接抛异常。我习惯写grid null || grid.length 0 || grid[0].length 0三道保险全部加上宁可多判断也不要少判断。第四个细节递归深度问题。如果你用的是 Java、C递归默认栈空间通常够用。但如果用 Python默认递归深度只有 1000 层左右遇到 1000x1000 全1的极端用例DFS 很容易 RecursionError。这种情况就要考虑下一节的 BFS 解法了。3. BFS解法不依赖递归矩阵很大时的稳妥退路3.1 什么时候应该换BFS面试官追问“如果网格特别大DFS 会不会爆栈”时你如果能立刻给出 BFS 方案会是明显的加分项。BFS广度优先搜索用队列代替调用栈没有递归深度限制。当矩阵达到几百乘几百甚至更大且陆地连通区域很大时BFS 更安全。另外有些机考的平台对递归不友好比如某些 Python 环境、某些嵌入式方向的在线笔试递归嵌套过深会直接被判运行时错误。所以 BFS 不是一个备胎而是一个必须掌握的保底方案。BFS 的核心流程遇到一个新的1时把它入队然后立马标记为0。队列不是空时就弹出队首元素检查它的四个邻居只要是1就入队并标记。每完成一次这样的过程就说明发现了一个完整岛屿。3.2 Java版本的BFS实现class Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0 || grid[0].length 0) { return 0; } int m grid.length; int n grid[0].length; int count 0; int[][] directions {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; grid[i][j] 0; QueueInteger queue new LinkedList(); queue.offer(i * n j); while (!queue.isEmpty()) { int code queue.poll(); int x code / n; int y code % n; for (int[] dir : directions) { int nx x dir[0]; int ny y dir[1]; if (nx 0 nx m ny 0 ny n grid[nx][ny] 1) { grid[nx][ny] 0; queue.offer(nx * n ny); } } } } } } return count; } }这里我用了一个小技巧队列里不存int[]{x, y}而是用一个整数i * n j把二维坐标编码成一维。好处是两个一是QueueInteger比Queueint[]省内存和对象创建开销二是入队时不需要额外创建数组对象机考环境下性能更稳。解码也很简单x code / ny code % n。3.3 BFS操作里最容易踩的坑入队时必须立刻标记这个坑我必须单独拿出来说因为它非常隐蔽。很多人的 BFS 写法是“出队时再标记已访问”也就是下面这样int code queue.poll(); int x code / n; int y code % n; grid[x][y] 0; // 错误示范出队时才标记这样写的问题在于同一个格子可能被它的多个邻居重复入队。举个简单的例子格子 A 和格子 B 都紧挨着格子 CA 先入队了 CB 入队时发现 C 还是1也把 C 入队。结果队列里就出现两个 C虽然最终结果可能碰巧还是对的但会造成大量重复计算极端情况下队列膨胀得很厉害。正确的做法是模拟“扩散”的过程一个格子一旦被入队它就已经是被发现和认领的状态必须立即在入队那一刻把grid改成0。这有点像你报名参加活动一旦登记成功名单上立刻划掉你的名字而不是等活动当天再划。4. 并查集解法把网格变成集合合并问题4.1 为什么还要学第三种解法面试时如果面试官问“除了 DFS 和 BFS这道题还能怎么做”你如果能说出并查集Union-Find印象分又会不一样。这道题本质上是在统计“连通分量”的个数而并查集恰好就是专门解决连通性问题的数据结构。并查集的思路是一开始把每个是陆地的格子都看成独立的集合然后检查相邻格子如果两个相邻格子都是陆地就把它们合并到同一个集合里。每合并一次集合总数减一。最后剩下的集合数量就是岛屿数量。4.2 二维坐标的一维编码并查集里需要给每个格子一个唯一的 ID。最常用的做法还是id i * n j。这样整个m * n的网格就被映射成了一个长度m * n的一维数组。我在并查集的初始化阶段只对1的格子做初始化每个陆地的parent指向自己count加一。水格子的parent保持默认值不参与统计。4.3 Java版本的并查集实现class Solution { private class UnionFind { int[] parent; int[] rank; int count; public UnionFind(char[][] grid, int m, int n) { 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) { int id i * n j; parent[id] id; count; } } } } public int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 路径压缩 } return parent[x]; } public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { return; } // 按秩合并尽量让树更矮 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } count--; } } public int numIslands(char[][] grid) { if (grid null || grid.length 0 || grid[0].length 0) { return 0; } int m grid.length; int n grid[0].length; UnionFind uf new UnionFind(grid, m, n); for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { int id i * n j; // 只需要检查右边和下边避免重复合并 if (i 1 m grid[i 1][j] 1) { uf.union(id, (i 1) * n j); } if (j 1 n grid[i][j 1] 1) { uf.union(id, i * n j 1); } } } } return uf.count; } }这里有两个细节值得说。一是只需要检查右边和下边。因为遍历顺序是从左上到右下当前格子的左边和上边其实已经在之前的格子里检查过了。如果四个方向都检查合并操作会重复执行虽然 union 里有rootX rootY的早退逻辑不会出错但白白浪费时间。二是路径压缩和按秩合并都做了这是在面试中展示你对算法有体系化理解的加分点。复杂度方面并查集操作近似常数级整体时间复杂度约O(m * n * α(m * n))其中α是反阿克曼函数可以近似理解为常数。空间复杂度O(m * n)。4.4 面试里什么时候掏出并查集我的建议是机考笔试时优先写 DFS 或 BFS因为代码短不易出错。面试聊天环节如果面试官主动问“还有更好的办法吗”或者追问“如果这个地图是动态变化的陆地会不断新增你怎么办”这时候再引入并查集。动态场景是并查集的真正用武之地。比如你维护一个实时地图每次新增一块陆地就更新岛屿数量DFS 和 BFS 每次都要重新全图扫描而并查集可以在新增陆地时只做局部合并非常高效。这也是为什么很多进阶题比如“岛屿数量 II”、“连通网络的操作次数”本质都在考并查集。5. 机考输入的差异与现场排查清单5.1 LeetCode风格和ACM风格的差异LeetCode 风格的题目已经帮你封装好了方法签名你只需要写public int numIslands(char[][] grid)。但不少公司的机考平台是 ACM 风格需要自己从标准输入读取数据。这个差异是很多只刷 LeetCode 的人翻车的重灾区。ACM 风格的 Java 模板可以参考import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int m sc.nextInt(); int n sc.nextInt(); sc.nextLine(); // 吃掉第一行末尾的换行符 char[][] grid new char[m][n]; for (int i 0; i m; i) { String line sc.nextLine(); grid[i] line.toCharArray(); } System.out.println(new Solution().numIslands(grid)); } }这里有个细节nextInt()读完 m 和 n 之后输入流里还留着一个换行符如果不加sc.nextLine()吃掉它接下来nextLine()读到的会是空字符串。这个坑我见过太多次了几乎每场 ACM 风格笔试都有人栽在这里。Python 风格类似import sys def main(): data sys.stdin.read().strip().split() if not data: return m, n int(data[0]), int(data[1]) grid [] idx 2 for _ in range(m): grid.append(list(data[idx])) idx 1 print(numIslands(grid))推荐用sys.stdin.read()一次性读入再 split比一行一行input()要快面对大输入时也更稳。5.2 我自己遇到过的五个现场问题第一个是把1写成了1。这个连编译都不报错结果返回 0很难排查。第二个是空数组判断不够。只判断了grid null忘了处理grid.length 0结果遇到空网格直接数组越界。第三个是修改了原始数组但面试官不允许。有的面试官会强调“不要改动输入数据”这时候就不能用沉没法得额外开一个visited数组。我的建议是写代码前先问一句“我可以直接修改传入的 grid 吗”这个提问本身也是加分项说明你有工程意识。第四个是方向数组写错。BFS 里四个方向写成{{-1,0},{1,0},{0,-1},{0,1}}少写一个或者正负号写反都会导致漏掉一部分岛屿。第五个是递归边界顺序写反。先访问数组再判断越界导致越界异常。记住先判边界再取元素。5.3 一个简单的现场验证方法机考写完代码后别急着提交。我会在草稿纸上或者心里快速跑三个用例最小用例[[1]]期望结果是 1。空网格[]期望结果是 0。一个稍微复杂点的用例1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1这个图有三个岛屿左上角的 2x2 方块算一个第三行第三列单独一个右下角两个连在一起一个。如果代码输出 3基本就对了。手算用例比直接提交再等结果要快得多也能帮你提前发现逻辑错误。另外一个必查点测试完是否不小心把grid[i][j] 1写成了赋值。这种低级错误很尴尬却真实发生过多次。6. 变体题与面试追问把一道题变成一类题6.1 三个最常见的变体题面试官不会总满足于考原题。“岛屿数量”最常见的三个变体是最大岛屿面积DFS/BFS 过程中统计连通区域包含多少个1取最大值。岛屿周长遍历每个陆地格子如果它的某个方向是水或者越界周长就加一。闭合岛屿数量边界上的岛屿不算岛屿只统计完全被水包围的岛屿。解决思路是先从四条边界 DFS 把所有和边界相连的陆地淹没再按原题方法统计。这三个变体的代码改动都不大核心还是“遍历 标记”框架。我面试时会主动提一句“这道题考的是连通分量计数常见的变体有求最大面积和求周长基本思路一样。”这句话往往能引导面试官顺着你熟悉的方向提问。6.2 面试追问的几点应对思路如果面试官继续加压可能会问“如果矩阵特别大内存放不下怎么办”答案是分块处理同时只保留相邻块的边界信息类似外部排序的思维。“如果网格里的陆地是动态增加的怎么办”答案就是前面提到的并查集。“如果需求是计算岛屿数量还要标出每个岛屿里的所有坐标点呢”这就是在做连通区域标记在图像处理里叫“连通域标记”可以扩展到图像分割场景。我个人体会是这道题的价值不在于背答案而在于它串起来的几个核心能力二维数组的遍历、递归与非递归的选择、连通性建模、还有从静态问题扩展到动态问题的迁移能力。把这些想明白了这道题就不再是一道孤立的题目而是一整个搜索类问题的地基。最后分享一个我自己的小习惯。刷完这道题之后我会强迫自己不看任何参考分别把 DFS、BFS、并查集三种写法各写一遍写到无脑完成的程度。因为机考现场根本没有时间让你现场推演逻辑能做到不用过脑子就写出框架遇到这道题才是真的稳。希望这篇把细节拆透的文章能让你在这个题上一次过、不返工。 
长河君 · 2026/10/14 9:24:57 · 阅读 1.2k LeetCode 200岛屿数量全解：DFS、BFS、并查集三种解法与机考避坑指南
每次机考刷题到“图论/搜索”这一块LeetCode 200“岛屿数量”基本是绕不开的题目。很多人看到“岛屿数量”觉得简单DFS一套就完事实际上机考环境下翻车的比例相当高。我见过不少候选人代码思路是对的但一跑测试就出问题重复计数、死循环、数组越界、甚至输入读取都出错。这篇文章把这道题彻底拆开从三种解法到机考细节再到变体题和面试追问尽量一次讲透。不管你是刷题计划排在第10天还是第100天遇到它这篇都能帮你少走几个弯路。1. 看懂题目之前先把两个容易错的理解纠正过来1.1 二维网格里的“连接”到底怎么定义题目给的输入是一个m x n的二维字符数组里面只有1陆地和0水。要统计的是“岛屿数量”所谓岛屿就是上下左右四个方向连在一起的1组成的连通块。需要特别注意斜对角方向不算连接。比如下面这个 2x2 网格1 0 0 1这里有两个岛屿而不是一个。很多人在白板上画图时会习惯性把对角也连起来这就是第一处容易出错的地方。面试或者机考时如果题目里没有明确说明“四连通”一定要开口确认一句或者自己在代码注释里写清楚“上下左右四个方向”。1.2 题目的核心考点不是“搜索”而是“标记”这道题的搜索本身很简单——遍历每一个格子遇到一个没访问过的1就把整块连通区域全部找出来计数器加一。真正的难点在于怎么保证同一个岛屿不会被重复计数。解决思路有两个方向一是额外开一个visited二维数组走过就标记二是直接在原数组上把访问过的陆地改成0这种“走一个沉一个”的做法有个形象的说法叫“沉没法”。我推荐机考时用沉没法因为它省掉了visited数组的初始化、判断和内存开销代码也更短。所以这道题的本质可以概括成一句话遍历 标记二者缺一不可。只遍历不标记同一个1会被重复遍历无数次直接死循环。2. DFS解法机考时的首选写法以及四个一次过的细节2.1 思路讲给面试官听的一分钟版本DFS深度优先搜索是最直观的解法。给面试官讲思路时我会用这个版本我遍历整个网格每当遇到一个没有被访问过的1我就认为发现了一个新岛屿然后把岛屿数量加一。接下来从这个格子的四个方向递归搜索把所有相邻的1全部标记成已访问避免后续重复计数。这段表述里有三个关键词遍历所有格子、遇到1就计数、递归标记连通区域。把这三句话说清楚面试官就知道你理解到位了。复杂度方面每个格子最多被访问一次所以时间复杂度是O(m * n)。空间复杂度是递归栈的深度最坏情况下整个网格都是陆地递归深度会达到m * n所以最坏是O(m * n)。2.2 Java版本的DFS实现我直接给出一个可以一次通过的版本class Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0 || grid[0].length 0) { return 0; } int m grid.length; int n grid[0].length; int count 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); } } } return count; } 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(grid, i - 1, j); dfs(grid, i 1, j); dfs(grid, i, j - 1); dfs(grid, i, j 1); } }很多人的写法和我这个很像但细节上有几个差异。注意我的边界判断是放在递归函数开头而且先判断越界再访问数组元素。如果把grid[i][j] 0写在前面i 已经越界时就会抛出数组下标异常。这个顺序问题在笔试里特别常见。2.3 四个细节决定你能不能一次过第一个细节字符别写错。判断的是1和0这是字符 char 类型不是数字 1 和 0。写grid[i][j] 1不会报编译错误但永远匹配不上最终结果会是 0。这个坑看似低级但机考紧张时真的有人会犯。第二个细节沉没操作的时机。grid[i][j] 0要在进入递归之前就执行也就是在 dfs 函数体的开头。如果你先递归四个方向最后再置为0递归过程中相邻格子还会反向访问回当前格子造成重复遍历极端情况下会栈溢出。正确的做法是“先沉没再扩散”。第三个细节空输入判断。有的测试用例会给你grid []如果没做判空grid[0]这行代码会直接抛异常。我习惯写grid null || grid.length 0 || grid[0].length 0三道保险全部加上宁可多判断也不要少判断。第四个细节递归深度问题。如果你用的是 Java、C递归默认栈空间通常够用。但如果用 Python默认递归深度只有 1000 层左右遇到 1000x1000 全1的极端用例DFS 很容易 RecursionError。这种情况就要考虑下一节的 BFS 解法了。3. BFS解法不依赖递归矩阵很大时的稳妥退路3.1 什么时候应该换BFS面试官追问“如果网格特别大DFS 会不会爆栈”时你如果能立刻给出 BFS 方案会是明显的加分项。BFS广度优先搜索用队列代替调用栈没有递归深度限制。当矩阵达到几百乘几百甚至更大且陆地连通区域很大时BFS 更安全。另外有些机考的平台对递归不友好比如某些 Python 环境、某些嵌入式方向的在线笔试递归嵌套过深会直接被判运行时错误。所以 BFS 不是一个备胎而是一个必须掌握的保底方案。BFS 的核心流程遇到一个新的1时把它入队然后立马标记为0。队列不是空时就弹出队首元素检查它的四个邻居只要是1就入队并标记。每完成一次这样的过程就说明发现了一个完整岛屿。3.2 Java版本的BFS实现class Solution { public int numIslands(char[][] grid) { if (grid null || grid.length 0 || grid[0].length 0) { return 0; } int m grid.length; int n grid[0].length; int count 0; int[][] directions {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; grid[i][j] 0; QueueInteger queue new LinkedList(); queue.offer(i * n j); while (!queue.isEmpty()) { int code queue.poll(); int x code / n; int y code % n; for (int[] dir : directions) { int nx x dir[0]; int ny y dir[1]; if (nx 0 nx m ny 0 ny n grid[nx][ny] 1) { grid[nx][ny] 0; queue.offer(nx * n ny); } } } } } } return count; } }这里我用了一个小技巧队列里不存int[]{x, y}而是用一个整数i * n j把二维坐标编码成一维。好处是两个一是QueueInteger比Queueint[]省内存和对象创建开销二是入队时不需要额外创建数组对象机考环境下性能更稳。解码也很简单x code / ny code % n。3.3 BFS操作里最容易踩的坑入队时必须立刻标记这个坑我必须单独拿出来说因为它非常隐蔽。很多人的 BFS 写法是“出队时再标记已访问”也就是下面这样int code queue.poll(); int x code / n; int y code % n; grid[x][y] 0; // 错误示范出队时才标记这样写的问题在于同一个格子可能被它的多个邻居重复入队。举个简单的例子格子 A 和格子 B 都紧挨着格子 CA 先入队了 CB 入队时发现 C 还是1也把 C 入队。结果队列里就出现两个 C虽然最终结果可能碰巧还是对的但会造成大量重复计算极端情况下队列膨胀得很厉害。正确的做法是模拟“扩散”的过程一个格子一旦被入队它就已经是被发现和认领的状态必须立即在入队那一刻把grid改成0。这有点像你报名参加活动一旦登记成功名单上立刻划掉你的名字而不是等活动当天再划。4. 并查集解法把网格变成集合合并问题4.1 为什么还要学第三种解法面试时如果面试官问“除了 DFS 和 BFS这道题还能怎么做”你如果能说出并查集Union-Find印象分又会不一样。这道题本质上是在统计“连通分量”的个数而并查集恰好就是专门解决连通性问题的数据结构。并查集的思路是一开始把每个是陆地的格子都看成独立的集合然后检查相邻格子如果两个相邻格子都是陆地就把它们合并到同一个集合里。每合并一次集合总数减一。最后剩下的集合数量就是岛屿数量。4.2 二维坐标的一维编码并查集里需要给每个格子一个唯一的 ID。最常用的做法还是id i * n j。这样整个m * n的网格就被映射成了一个长度m * n的一维数组。我在并查集的初始化阶段只对1的格子做初始化每个陆地的parent指向自己count加一。水格子的parent保持默认值不参与统计。4.3 Java版本的并查集实现class Solution { private class UnionFind { int[] parent; int[] rank; int count; public UnionFind(char[][] grid, int m, int n) { 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) { int id i * n j; parent[id] id; count; } } } } public int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 路径压缩 } return parent[x]; } public void union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { return; } // 按秩合并尽量让树更矮 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } count--; } } public int numIslands(char[][] grid) { if (grid null || grid.length 0 || grid[0].length 0) { return 0; } int m grid.length; int n grid[0].length; UnionFind uf new UnionFind(grid, m, n); for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { int id i * n j; // 只需要检查右边和下边避免重复合并 if (i 1 m grid[i 1][j] 1) { uf.union(id, (i 1) * n j); } if (j 1 n grid[i][j 1] 1) { uf.union(id, i * n j 1); } } } } return uf.count; } }这里有两个细节值得说。一是只需要检查右边和下边。因为遍历顺序是从左上到右下当前格子的左边和上边其实已经在之前的格子里检查过了。如果四个方向都检查合并操作会重复执行虽然 union 里有rootX rootY的早退逻辑不会出错但白白浪费时间。二是路径压缩和按秩合并都做了这是在面试中展示你对算法有体系化理解的加分点。复杂度方面并查集操作近似常数级整体时间复杂度约O(m * n * α(m * n))其中α是反阿克曼函数可以近似理解为常数。空间复杂度O(m * n)。4.4 面试里什么时候掏出并查集我的建议是机考笔试时优先写 DFS 或 BFS因为代码短不易出错。面试聊天环节如果面试官主动问“还有更好的办法吗”或者追问“如果这个地图是动态变化的陆地会不断新增你怎么办”这时候再引入并查集。动态场景是并查集的真正用武之地。比如你维护一个实时地图每次新增一块陆地就更新岛屿数量DFS 和 BFS 每次都要重新全图扫描而并查集可以在新增陆地时只做局部合并非常高效。这也是为什么很多进阶题比如“岛屿数量 II”、“连通网络的操作次数”本质都在考并查集。5. 机考输入的差异与现场排查清单5.1 LeetCode风格和ACM风格的差异LeetCode 风格的题目已经帮你封装好了方法签名你只需要写public int numIslands(char[][] grid)。但不少公司的机考平台是 ACM 风格需要自己从标准输入读取数据。这个差异是很多只刷 LeetCode 的人翻车的重灾区。ACM 风格的 Java 模板可以参考import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int m sc.nextInt(); int n sc.nextInt(); sc.nextLine(); // 吃掉第一行末尾的换行符 char[][] grid new char[m][n]; for (int i 0; i m; i) { String line sc.nextLine(); grid[i] line.toCharArray(); } System.out.println(new Solution().numIslands(grid)); } }这里有个细节nextInt()读完 m 和 n 之后输入流里还留着一个换行符如果不加sc.nextLine()吃掉它接下来nextLine()读到的会是空字符串。这个坑我见过太多次了几乎每场 ACM 风格笔试都有人栽在这里。Python 风格类似import sys def main(): data sys.stdin.read().strip().split() if not data: return m, n int(data[0]), int(data[1]) grid [] idx 2 for _ in range(m): grid.append(list(data[idx])) idx 1 print(numIslands(grid))推荐用sys.stdin.read()一次性读入再 split比一行一行input()要快面对大输入时也更稳。5.2 我自己遇到过的五个现场问题第一个是把1写成了1。这个连编译都不报错结果返回 0很难排查。第二个是空数组判断不够。只判断了grid null忘了处理grid.length 0结果遇到空网格直接数组越界。第三个是修改了原始数组但面试官不允许。有的面试官会强调“不要改动输入数据”这时候就不能用沉没法得额外开一个visited数组。我的建议是写代码前先问一句“我可以直接修改传入的 grid 吗”这个提问本身也是加分项说明你有工程意识。第四个是方向数组写错。BFS 里四个方向写成{{-1,0},{1,0},{0,-1},{0,1}}少写一个或者正负号写反都会导致漏掉一部分岛屿。第五个是递归边界顺序写反。先访问数组再判断越界导致越界异常。记住先判边界再取元素。5.3 一个简单的现场验证方法机考写完代码后别急着提交。我会在草稿纸上或者心里快速跑三个用例最小用例[[1]]期望结果是 1。空网格[]期望结果是 0。一个稍微复杂点的用例1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1这个图有三个岛屿左上角的 2x2 方块算一个第三行第三列单独一个右下角两个连在一起一个。如果代码输出 3基本就对了。手算用例比直接提交再等结果要快得多也能帮你提前发现逻辑错误。另外一个必查点测试完是否不小心把grid[i][j] 1写成了赋值。这种低级错误很尴尬却真实发生过多次。6. 变体题与面试追问把一道题变成一类题6.1 三个最常见的变体题面试官不会总满足于考原题。“岛屿数量”最常见的三个变体是最大岛屿面积DFS/BFS 过程中统计连通区域包含多少个1取最大值。岛屿周长遍历每个陆地格子如果它的某个方向是水或者越界周长就加一。闭合岛屿数量边界上的岛屿不算岛屿只统计完全被水包围的岛屿。解决思路是先从四条边界 DFS 把所有和边界相连的陆地淹没再按原题方法统计。这三个变体的代码改动都不大核心还是“遍历 标记”框架。我面试时会主动提一句“这道题考的是连通分量计数常见的变体有求最大面积和求周长基本思路一样。”这句话往往能引导面试官顺着你熟悉的方向提问。6.2 面试追问的几点应对思路如果面试官继续加压可能会问“如果矩阵特别大内存放不下怎么办”答案是分块处理同时只保留相邻块的边界信息类似外部排序的思维。“如果网格里的陆地是动态增加的怎么办”答案就是前面提到的并查集。“如果需求是计算岛屿数量还要标出每个岛屿里的所有坐标点呢”这就是在做连通区域标记在图像处理里叫“连通域标记”可以扩展到图像分割场景。我个人体会是这道题的价值不在于背答案而在于它串起来的几个核心能力二维数组的遍历、递归与非递归的选择、连通性建模、还有从静态问题扩展到动态问题的迁移能力。把这些想明白了这道题就不再是一道孤立的题目而是一整个搜索类问题的地基。最后分享一个我自己的小习惯。刷完这道题之后我会强迫自己不看任何参考分别把 DFS、BFS、并查集三种写法各写一遍写到无脑完成的程度。因为机考现场根本没有时间让你现场推演逻辑能做到不用过脑子就写出框架遇到这道题才是真的稳。希望这篇把细节拆透的文章能让你在这个题上一次过、不返工。