企业官网建设流程全解析

读完本文你将了解：岛屿数量的三种解法优劣 | AI 从递归 DFS 到 BFS 到并查集的优化路径 | 面试中一题多解的正确展示姿势

📋 题目

原题：给定一个由'1'（陆地）和'0'（水）组成的二维网格，计算岛屿的数量。岛屿被水包围，通过水平或垂直方向相邻的陆地连接而成。

💡 先问一个问题

让 AI 写一道"数岛"题，你觉得它会怎么写？

我实测的结果是：它上来就写了个递归 DFS，代码看着很优雅——然后我随手测了个 250×250 全是陆地的极端用例，直接 StackOverflow。

这才有意思：表面考搜索，深层考工程判断。

🤖 第一版：AI 的朴素解法——优雅但会炸

我把题目直接丢给 AI，不加任何提示。以下是它第一版：

defnumIslands(grid):ifnotgrid:return0m,n=len(grid),len(grid[0])count=0defdfs(i,j):ifi<0ori>=morj<0orj>=norgrid[i][j]=='0':returngrid[i][j]='0'# 标记已访问dfs(i+1,j)dfs(i-1,j)dfs(i,j+1)dfs(i,j-1)foriinrange(m):forjinrange(n):ifgrid[i][j]=='1':count+=1dfs(i,j)returncount

这段代码逻辑完全正确，而且相当简洁——不到 15 行就把核心逻辑写完了。AI 选择递归 DFS 的原因很"人类"——它在训练数据里见过太多类似写法，递归天然贴合"填岛"的直觉。跟一个格子相邻的四个格子，递归下去——思路非常顺。

但问题出在哪？Python 默认递归深度只有 1000。一个 33×33 全是陆地的网格（总共 1089 个格子），DFS 可能一次性递归到底，直接打满调用栈。300×300 就更不用说了——9 万个格子连锁递归，栈直接炸穿。

工程上，这是不可接受的。LeetCode 的测试用例碰巧不会全是陆地，但面试官一旦追问，你就得接得住。

复杂度：时间 O(m×n)，空间 O(m×n)（递归栈深度，最坏情况）。

🧠 AI 的自我优化

当我告诉 AI “你的代码在 300×300 全陆地时会 StackOverflow”，它的优化路径是这样的：

第 1 次优化：改 BFS 用队列（避免递归栈）

fromcollectionsimportdequedefnumIslands(grid):ifnotgrid:return0m,n=len(grid),len(grid[0])count=0foriinrange(m):forjinrange(n):ifgrid[i][j]=='1':count+=1q=deque([(i,j)])grid[i][j]='0'whileq:x,y=q.popleft()fordx,dyin[(1,0),(-1,0),(0,1),(0,-1)]:nx,ny=x+dx,y+dyif0<=nx<mand0<=ny<nandgrid[nx][ny]=='1':grid[nx][ny]='0'q.append((nx,ny))returncount

AI 的推理挺实在的：队列存在堆上，不会爆栈。方向数组比四个dfs()调用更紧凑，还少了重复的边界判断代码。

而且 BFS 有一个额外的好处——你可以轻易改成"计算每个岛屿的面积"（加个计数器就行），因为 BFS 天然就是一层一层往外扩的，符合"先近后远"的直觉。这就是为什么在地图应用中（Google Maps 查找最近加油站），BFS 比 DFS 更受欢迎。

第 2 次优化：并查集（适合"动态加陆地"场景）

当我说"如果后续会有新增陆地查询怎么办"，AI 给出了并查集版本：

classUnionFind:def__init__(self,n):self.parent=list(range(n))self.rank=[0]*n self.count=0deffind(self,x):ifself.parent[x]!=x:self.parent[x]=self.find(self.parent[x])# 路径压缩returnself.parent[x]defunion(self,x,y):px,py=self.find(x),self.find(y)ifpx==py:returnifself.rank[px]<self.rank[py]:px,py=py,px self.parent[py]=pxifself.rank[px]==self.rank[py]:self.rank[px]+=1self.count-=1defadd(self):self.count+=1defnumIslands(grid):ifnotgrid:return0m,n=len(grid),len(grid[0])uf=UnionFind(m*n)foriinrange(m):forjinrange(n):ifgrid[i][j]=='1':uf.add()idx=i*n+j# 只合并左和上（避免重复）ifi>0andgrid[i-1][j]=='1':uf.union(idx,(i-1)*n+j)ifj>0andgrid[i][j-1]=='1':uf.union(idx,i*n+(j-1))returnuf.count

这三个版本的演进，本质上是同一个问题的不同工程视角：

☕ Java 实现（CSDN 第一大语言，补上）

publicclassSolution{publicintnumIslands(char[][]grid){if(grid==null||grid.length==0)return0;intm=grid.length,n=grid[0].length;intcount=0;for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(grid[i][j]=='1'){count++;bfs(grid,i,j,m,n);}}}returncount;}privatevoidbfs(char[][]grid,inti,intj,intm,intn){Queue<int[]>q=newLinkedList<>();q.offer(newint[]{i,j});grid[i][j]='0';int[][]dirs={{1,0},{-1,0},{0,1},{0,-1}};while(!q.isEmpty()){int[]cur=q.poll();for(int[]d:dirs){intnx=cur[0]+d[0],ny=cur[1]+d[1];if(nx>=0&&nx<m&&ny>=0&&ny<n&&grid[nx][ny]=='1'){grid[nx][ny]='0';q.offer(newint[]{nx,ny});}}}}}

为什么要加 Java？CSDN 第一大用户群体是 Java 开发者。Python 能看懂不代表面试能用 Java 写出来。两版代码摆在一起，读者自己对比，比讲十句话有用。

🔍 算法模式拆解

这道题涉及三个可切换的算法模式：

模式识别信号：

• 看到"连通区域"、“相邻” →Graph DFS/BFS或Union Find
• 看到"需要动态更新" → 倾向Union Find
• 网格大小超过递归栈深度 → 排除递归 DFS

面试陷阱：很多人上来就说"用 DFS"，面试官追问"300×300 全陆地怎么办？"瞬间暴露深度不足。

那什么时候该用哪种？我的判断框架是：

🏗️ 真实产品场景

这题不只是算法题，它的底层逻辑映射到很多产品功能：

• Google Maps 的"区域合并"：地图上一个区域被道路切分，需要计算连通区域数量——这就是岛屿问题
• Slack 工作区用户分组：有共同频道关系的用户属于同一"岛屿"，计算独立社区数量。想象一下，Slack 有 1000 个用户和 5000 个频道，你需要找出多少个"独立的工作圈子"——完全就是岛屿问题在社交图谱上的投影
• 图像处理的连通域标记：OCR 前的文字区域分割，用的就是 Flood Fill（和 DFS/BFS 完全一样的逻辑）。你手机扫描文档时，背后就是这道题的变体
• LinkedIn 人脉圈计算：如果 A 认识 B 且 B 认识 C，那么 A-B-C 属于同一个人脉圈——这就是并查集的经典场景。LinkedIn 的"你可能认识的人"推荐算法，底层就是并查集帮你找到了"还没连接但属于同一连通分量"的用户对

这也是为什么面试官爱考这道题：一道题能同时考察 DFS、BFS、并查集三种基本功，还能延伸到系统设计和产品思维。你不需要三样都精通，但至少要能说出来"我选的方案有什么优劣"——这才是面试官真正想听的。

再多说一句：实际面试中，如果你上来就给并查集，部分面试官反而会追问"为什么不用更简单的 BFS？"——不是因为你错了，而是想确认你不是在背模板。能解释清楚选型理由的人，比能写出最优解的人更稀缺。

✅ 面试官的点评

写到什么程度算"通过"：

• 给出任意一种正确解法 + 时空复杂度分析 → 及格线
• 能说出递归 DFS 的问题，给出 BFS 替代方案 → 良好
• 三种解法都说清楚，并能分析各自适用场景 → 优秀

加分项：

• 提到sys.setrecursionlimit()只是打补丁，不是正解
• 在 BFS 版本中解释为什么先标记再入队（避免重复入队导致的 O(n²) 爆炸）
• 能画一笔并查集的"路径压缩"示意图

常见踩坑：

• 遍历方向只写了右下两个方向，忘写左上（误以为"只扫一遍就够了"）——这个坑我亲眼见证过好几个人踩，因为在纸上画的时候觉得"从左上往右下扫描，不需要检查左边和上边"，但 DFS 的遍历顺序跟扫描顺序是两码事
• 并查集版本没做路径压缩，find 退化成 O(n)——写并查集最少要记住两样：路径压缩 + 按秩合并，缺一个就是半成品
• 在原数组上直接改会破坏输入（面试官可能追问"如果不让改输入呢"）——可以用 visited 布尔数组，但会多 O(m×n) 的空间开销
• BFS 版本忘了在入队时就标记，导致同一个点被重复入队——这会导致时间复杂度从 O(m×n) 变成 O((m×n)²)，在极端网格下直接超时

📊 同类题推荐

来源说明：

• ✅ 已验证：LeetCode 官方题解 + AI（DeepSeek-v4）多轮实测
• 📄 参考：“Union Find with Path Compression” — Tarjan, 1975