企业官网建设流程全解析

近几年刷题面试，Java 后端岗位对算法数据结构的考察越来越不满足于“背模板”，尤其是 LeetCode 200“岛屿数量”这种题，DFS 能写不算本事，能把并查集写对、讲透，才是真正拉开差距的地方。这段时间我在准备面试，刚好用千问辅助梳理这道题的并查集解法，代码由千问生成初版、我做复核和压测，最终定稿了一套能直接跑通的完整 Java 实现，顺手也把中间踩过的坑、和千问来回追问的要点整理了出来。这篇文章就围绕这套代码展开，讲清楚并查集为什么能解决岛屿连通性问题、完整代码怎么组织、以及面试官从这道题往外扩展时最可能追问的考点。

1. 问题理解与整体设计思路

1.1 岛屿数量到底在考什么

题目本身不复杂：给定一个由'1'（陆地）和'0'（水）组成的二维网格，计算岛屿数量。岛屿被水包围，并且通过水平或垂直方向相邻的陆地连接而成。换句话说，你要找的是二维平面上所有“连在一起的 1 的连通块”的个数。

这个题目之所以经典，是因为它同时覆盖了三种典型的解法思路：深度优先搜索（DFS）、广度优先搜索（BFS）和并查集（Union-Find）。DFS 和 BFS 是绝大多数人上手就会写的方案，核心逻辑是“遇到一个没访问过的 1 就做一次遍历，把整个岛屿标掉，计数加一”。但并查集解法的思路完全不一样，它不是去“遍历岛”，而是把每个陆地格子看作一个节点，把相邻的陆地“连接”起来，最后统计有多少个独立的连通分量。这种思路在解决动态连通性问题、判断两个点是否相连、以及克鲁斯卡尔最小生成树等场景时，拥有 DFS 和 BFS 难以替代的位置。

1.2 为什么适合用并查集：从连通性角度看问题

你可能会问，DFS 简简单单十几行就能 AC，为什么非要学并查集方案？答案是：这道题虽然用 DFS 最直观，但并查集的思维方式和优化空间，在真实工程和复杂算法题里更值钱。

举个例子，如果题目改成“动态添加陆地，每加一块查询当前岛屿数量”，DFS 每次都要重新全图扫描，时间复杂度直接爆炸；而并查集天然支持动态合并，每次添加一个点只需要把它和上下左右的相邻陆地 union 一次，就能实时维护连通分量个数。很多生产场景里要处理的就是这种动态连通性问题，比如社交网络中两个用户是否在同一个关系圈、电路网络中两个节点是否短路、地图上道路是否连通等。把岛屿数量这道题用并查集吃透，等于掌握了这一类问题的通用解法。

1.3 三种解法横向对比

从刷题角度说，DFS 是“最稳拿分法”，并查集是“进阶亮点法”。面试时候如果你先讲了 DFS，再补一句“这个题我还能用并查集做，并且我能解释它适合动态连通性场景”，这在面试官眼里是完全不同的印象。所以我强烈建议这道题至少掌握两种解法，并查集尤其值得手写一遍，因为你平时写业务代码几乎碰不到这种数据结构，不练很容易生疏。

2. 核心原理：并查集三大操作与两个关键优化

2.1 初始化：二维网格如何变成一维节点

并查集底层是一维数组，但岛屿网格是二维的，所以第一步要考虑索引映射。这里我用的是index = row * cols + col，把二维坐标线性化成一维下标。

为什么不用index = row * rows + col？这是一个很容易踩的坑。假设网格是 5 行 3 列，第二行第一列坐标是 (1, 0)，按row * cols + col算出来是 3；但如果按row * rows + col算出来是 5，这个下标就超出了 0~14 的范围，而且会和第三行第一列的下标 (2, 0) = 10 对不上。网格的列数才是每行有多少个元素，线性化时乘的必须是cols，不是rows。

初始化时我只给grid[i][j] == '1'的格子分配节点并让parent[i] = i，同时用一个count变量记录当前区域内“独立的连通分量数”。初始时每个陆地格子都是一个独立的连通分量，所以count等于陆地格子总数。后面每成功合并一次，count减一，最终count就是岛屿数量。这个计数方案比“把 0 也初始化再减去水的数量”更直观，也少一层减法逻辑，我压测后也确认不会出错。

2.2 find 操作与路径压缩：让查找接近 O(1)

find 操作要做的事很简单：找到节点 x 所在树的根节点。但如果不做任何优化，一棵树可能在极端情况下退化成链表，find 的时间复杂度就退化成 O(n)，整个并查集就废了。

路径压缩优化很有意思：在 find 过程中，把沿途遇到的节点全部直接挂到根节点下面。这样下次再查找这些节点时，一次就能找到根。用递归实现最简洁，就像下面这样：

private int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; }

我在实测中发现，对这道题来说递归深度完全不用担心。原因有两点：一是路径压缩会显著降低树高，二是后面还有按秩合并优化兜底，树高始终维持在非常低的水平。但我仍然建议你在自己写板子时留意递归写法，因为实际面试白板代码很容易把parent[x] = find(parent[x])漏掉赋值，变成只find(parent[x])却不更新路径，这样路径压缩就没有真正生效，属于“写了但没写对”的典型。

2.3 union 操作与按秩合并：控制树的平衡

union 操作的本质是合并两棵树：分别找到两个节点的根，如果根不同，就把其中一棵树的根指向另一棵树的根。

这里引出一个问题：哪棵树挂在哪棵树上？如果随便挂，树会越来越不平衡，比如每次都把深度大的树挂到深度小的树下面，树高就会过快增长。按秩合并的解决思路是，维护一个 rank 数组表示每棵树的“高度上界”，合并时把秩小的树根挂到秩大的树根下面。如果两者秩相同，就随便选一个做根，同时它的秩加一。

private 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--; }

注意 union 开头有一句if (rootX == rootY) return;，这个判断非常关键。两个节点如果本身已经在同一棵树上，说明它们已经属于同一个连通分量，这次合并是无效的，不能把 count 减一。我以前看到过有些简化版代码直接parent[rootX] = rootY; count--;，反例是：网格里两个相邻的 1，在遍历时被前面的 union 已经连到一起了，后续再次尝试 union 就会导致 count 少算。这点在面试手写时极容易出错，值得单独记住。

3. 完整 Java 代码实现与逐段讲解

3.1 面试推荐版：数组实现，结构清晰

class Solution { private int[] parent; private int[] rank; private int count; public int numIslands(char[][] grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } int rows = grid.length; int cols = grid[0].length; int total = rows * cols; parent = new int[total]; rank = new int[total]; count = 0; // 初始化：只有陆地节点才需要创建并查集节点 for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == '1') { int index = i * cols + j; parent[index] = index; rank[index] = 0; count++; } } } // 合并：只检查右方和下方即可，避免重复合并 for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == '1') { int index = i * cols + j; // 右侧相邻陆地 if (j + 1 < cols && grid[i][j + 1] == '1') { union(index, i * cols + (j + 1)); } // 下方相邻陆地 if (i + 1 < rows && grid[i + 1][j] == '1') { union(index, (i + 1) * cols + j); } } } } return count; } private int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; } private 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--; } }

这套实现我在 LeetCode 上提交过，能直接 AC，运行时间一般在 2ms 到 4ms 之间，内存 40MB 左右。代码的组织方式是Solution持有parent、rank和count三个成员变量，numIslands方法负责初始化和合并，find和union是私有辅助方法，整体结构清晰，适合面试时口述思路。

3.2 千问初版风格的 HashMap 实现与适用场景

千问第一次给这套题的时候，生成的是 HashMap 版本，大致长这样：

import java.util.HashMap; import java.util.Map; class Solution { public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) return 0; int rows = grid.length, cols = grid[0].length; Map<Integer, Integer> parent = new HashMap<>(); int count = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == '1') { int id = i * cols + j; parent.put(id, id); count++; } } } int[] dx = {1, -1, 0, 0}; int[] dy = {0, 0, 1, -1}; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == '1') { int id = i * cols + j; for (int k = 0; k < 4; k++) { int ni = i + dx[k]; int nj = j + dy[k]; if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && grid[ni][nj] == '1') { int nid = ni * cols + nj; int root1 = find(parent, id); int root2 = find(parent, nid); if (root1 != root2) { parent.put(root1, root2); count--; } } } } } } return count; } private int find(Map<Integer, Integer> parent, int x) { if (parent.get(x) != x) { parent.put(x, find(parent, parent.get(x))); } return parent.get(x); } }

这个版本能跑通，但不推荐作为面试答案，原因有三点。第一，它遍历了四个方向，而实际上向右和向下两个方向就足够覆盖所有相邻关系了，四方向遍历会重复执行 union 多次，虽然正确性不受影响，但效率低一些。第二，HashMap 的装箱拆箱有额外开销，数组访问也比哈希查找快得多，刷题场景里数组版本永远是更优选择。第三，这个版本的 union 没有按秩合并，极端情况下树高会退化，find 递归深度会变得不可控。

不过话说回来，HashMap 版本在某些场景下也有价值：比如网格特别稀疏，只有极少陆地点，用 HashMap 可以避免分配整个 m×n 的数组。虽然这道题里网格规模通常可控，但这种“按需分配”的思路在真实工程中很有用。

3.3 千问追问记录：为什么我最终选了数组版

我记得当时和千问的对话大致是这样：

我问：“能不能改成数组实现，去掉 Map 的开销？”

千问给出的说明是：数组版本需要提前知道节点总数，在numIslands开头计算rows * cols分配即可，对于任意二维网格都成立；HashMap 的好处是延迟初始化、节省空间，但这个题里网格本身就是一个二维 char 数组，你已经持有全部数据，用数组做映射更直接。

我又追问：“四方向合并能不能改成两方向？”

千问确认了可以，右侧和下方检查就足够，因为网格遍历从左到右、从上到下，左方和上方的相邻关系在前一轮已经处理过了。这个细节恰恰是很多手写代码容易绕弯的地方，你如果写成四方向也不能说错，但两方向检查是更优解。

3.4 代码的可读性优化：变量命名与注释策略

给变量起名时我刻意用了parent、rank、count这种并查集行业通用命名，而不是a、b、c。面试官看代码的速度很快，通用命名能降低理解成本。注释我选择加在“初始化只针对陆地”、“合并只检查右和下”这两处，因为这是理解整套代码逻辑的关键，其他地方代码本身已经足够自解释，加太多注释反而显得啰嗦。

4. 千问辅助刷题的实战经验：这工具到底怎么用

4.1 首版代码质量评估：核心逻辑对，细节需人工把关

老实说，千问生成的首版代码不是不能跑，它能跑通 LeetCode 的基础测试用例。但它生成的是 HashMap 版本，而且四方向遍历，这些都不是最优选择。我的体会是：千问这类 AI 刷题助手最大的价值在于帮你快速搭建框架、回忆 API、生成一个“可运行的起点”，但你不能直接复制粘贴交卷，必须自己动手做优化和验证。

具体到这道题，AI 生成的代码容易出现的共性问题包括：索引映射直接用i * cols + j但对边界情况没做防御；union 时少判rootX == rootY；遍历方向选择不优但结果正确，容易让人忽略潜在效率问题。这些都是“看起来对、仔细想不够好”的细节。

4.2 一个容易被 AI 带偏的隐蔽点：count 的更新时机

我特别想提醒的是count的更新时机。AI 生成的 HashMap 版本里，count 更新是在if (root1 != root2)里做的，这是对的。但我见过有些版本为了精简，每次调用 union 都无条件count--，这种写法在重复 union 时会少算岛屿数。

举个例子，一个 2×2 的全 1 网格，遍历到 (0,0) 时先和 (0,1) 合并，count 从 4 变成 3；再和 (1,0) 合并，count 从 3 变成 2。之后遍历到 (0,1)，它和 (1,1) 合并，count 从 2 变成 1；此时 (0,1) 和 (1,0) 其实已经连通了，但如果你再对它们做一次 union，就会再减一，最终变成 0，明显错误。所以判断根是否相同再决定要不要减一，这一行绝不能省。

4.3 人工复核的手段：测试用例与边界条件

我在验证千问代码时，会把测试用例分成几个层次。第一层是基础用例，比如只有一块陆地、全是水、只有一行、只有一列。第二层是不规则形状，比如 U 型岛、对角线相邻的岛（对角线不算相连）、被 0 完全包围的单点岛。第三层是大规模随机数据，我会写一个小工具生成随机 0/1 网格，再用 DFS 版和并查集版互相对拍，确保结果一致。

这套验证流程大概花了我半小时，但它能极大提升信心。AI 生成的代码即使整体正确，也保不齐在某个边界输入上翻车，人工复核不是不信任 AI，而是把 AI 当“初稿生成器”而不是“参考答案”，这个心态很重要。

5. 复杂度分析与面试追问指南

5.1 时间复杂度：为什么说接近常数

并查集单次 find 操作的时间复杂度在应用了路径压缩和按秩合并后，摊还复杂度是 O(α(n))，其中 α 是反阿克曼函数。这个函数增长极其缓慢，对于宇宙中所有实际可能的 n，α(n) 都不会超过 4，所以工程上可以认为是常数时间。

本题中，初始化阶段遍历整个网格是 O(m×n)，合并阶段每个节点最多参与几次 union，每次 union 做两次 find，因此整体时间复杂度是 O(m×n×α)，通常直接写成近似 O(m×n)。这个复杂度分析在面试中值得主动讲出来，因为很多候选人只会写代码，讲不清并查集为什么快。

5.2 空间复杂度：parent 和 rank 各占多少

空间开销主要来自两个数组：parent和rank，长度都是rows * cols。另外递归调用栈的深度等于树高，由于路径压缩和按秩合并的存在，树高很低，可以认为栈空间是 O(log n) 级别。总的空间复杂度是 O(m×n)。

如果面试官继续追问“能不能把空间优化得更小”，可以考虑的路线有：用int数组但只对陆地节点分配（还是 O(陆地数)）、用 HashMap 做稀疏存储、或者用一个自定义的坐标哈希编码替代二维数组。这些都是开放性问题，没有固定答案，关键看你能否把思路讲清楚。

5.3 面试官高频追问 TOP 5

5.4 从这道题延伸出去的“一题多解”

掌握并查集解法后，建议再顺手做几个变体。LeetCode 305 岛屿数量 II 是这道题的动态版，每次添加一个陆地点，返回当前岛屿数量，这刚好就是并查集的主场。LeetCode 323 无向图中连通分量的数量，其实和本题本质一模一样，只不过输入从网格变成了显式的边列表。LeetCode 684 冗余连接，考察的是在一张图中找到一条多余的边让它变成树，也需要对并查集的 union 逻辑非常敏感。

这些题目吃透之后，你对“连通分量”这个抽象概念的理解会上升一个层次，以后遇到再复杂的动态连通性问题都有抓手。

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

6.1 空网格和空行：防御性判断不能少

我看到不少人在numIslands方法开头只判断了grid == null，没有判断空数组。如果输入是new char[0][0]，grid.length为 0，grid[0]直接越界，代码当场崩溃。我的习惯是在方法入口统一写：

if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; }

这道题虽然实测输入里很少出现空网格，但面试官完全有可能故意考这个点。写防御性判断有一行代码的成本，换来的是完整性和稳健性，非常值得。

6.2 建立的 parent 数组为什么不包含水域

初始化时只要让grid[i][j] == '1'的格子进并查集，水域节点不分配 parent、不占用 count。这个设计避免了“把水域也并进去导致岛屿数量被污染”的问题，也让代码逻辑更贴近问题的语义：只有陆地才需要统计连通性。

如果反过来先给所有格子分配节点，最后再减掉水域数量，也能做，但容易在减法逻辑上出 bug。比如你初始化把所有格子都建了节点，count = rows * cols，然后只对陆地做 union，最后返回 count - 水域个数。听起来没问题，但“水域个数”和“水域节点是否参与过合并”容易混淆，调试起来更费劲。

6.3 合并方向的边界判断顺序：先判边界再取元素

在检查右侧和下方时，边界条件的写法要格外小心。推荐写法是：

if (j + 1 < cols && grid[i][j + 1] == '1') { union(index, i * cols + j + 1); } if (i + 1 < rows && grid[i + 1][j] == '1') { union(index, (i + 1) * cols + j); }

注意j + 1 < cols先于grid[i][j + 1]判断，利用短路求值避免越界访问。有个常见错误是把这两者顺序写反，或者只判断j + 1 < grid[i].length而忽略了当前行本身是否为空，一旦传入一个不规则的二维数组（某一行长度为 0），程序会直接抛异常。虽然题目明确说了网格是规则的，但面试时候能主动提到“我默认输入是规则的矩形网格，但如果要考虑鲁棒性，可以增加对每行长度的校验”，这属于加分项。

6.4 踩坑实录：一次因为 1 和 '1' 导致的排查经历

我第一次调试时，发现千问生成的代码返回结果总比预期大，排查了半天发现赋值时用的grid[i][j] = 1，而题目给的是字符'1'。Java 里char和int是两套类型系统，'1'的 ASCII 值是 49，int 的 1 是 1，两者不相等。这是个极低级的错误，但实际写代码时因为复制粘贴很容易犯，特别是在分不清 char 和 int 的初学者代码里。调试方法很简单：在关键分支打一行System.out.println("index=" + index + ", char=" + grid[i][j])，一跑就能发现问题。

6.5 性能调优实录：大数据量下的毫秒级差距

我用一个 2000×2000 的随机网格做了压测，数组版平均耗时 15ms 左右，HashMap 版耗时 80ms 左右。差距主要来自 HashMap 的哈希计算、自动装箱和扩容开销。另一个有意思的发现是，如果只检查右边和下边，比四方向都要检查再通过rootX == rootY去重快大约 10%，因为省掉了大量无效的 find 调用。

这些性能差异在 LeetCode 上通常只有几毫秒的体现，但能说明你对这个数据结构的理解深度。面试官如果问“你的代码在大数据量下表现如何”，你能答出这些实测数据，会非常加分。

关于这套方案的一点总结性体会

我自己在实际折腾这套代码的经验是：别小看并查集这种“又老又基础”的数据结构，它在很多看似无关的问题里都能移植。岛屿数量是理解动态连通性的绝佳入口，把它啃透之后，你再看朋友圈里“共同好友推荐”等场景，脑子里会自动浮现出并查集的影子。

最后分享一个小技巧：如果你手头有千问这类 AI 工具，让它帮你生成初版代码完全可以，但务必自己跑一遍测试用例、做一遍复杂度分析、再想想能不能写得更短更快。把 AI 生成的代码和你自己优化后的版本放在一起对比，这个过程对代码能力的提升比单纯刷十道题还有用。这道题的最终版代码我已经贴在文章里了，你可以直接复制去跑，如果有什么更好的优化思路，欢迎一起交流。