☰
岛屿数量题解:DFS、BFS与并查集三种算法详解
2026/10/2 16:20:41 网站建设 项目流程

做算法题这么多年,力扣 200 题“岛屿数量”大概是互联网技术面试里出场率最高的图论入门题。题目本身不长:给你一个由 '1' 和 '0' 组成的二维网格,'1' 是陆地、'0' 是水,上下左右相邻的 '1' 属于同一座岛,要你数出网格里一共有多少座岛屿。就这么一句话,背后其实串起了 DFS、BFS、并查集三套完整的算法体系。我刷这题前后刷了三遍,第一遍只会写递归,第二遍才理解为什么 BFS 能抗住超大规模用例,第三遍用并查集重写时才真正想明白“连通分量”到底是什么。这篇文章把这三遍的收获和踩过的坑一次讲完,准备面试刷题的朋友可以直接照着练。

1. 这道题考什么:从题意到图论建模

1.1 原题描述与输入输出细节

原题干不长:给你一个由'1'(陆地)和'0'(水)组成的二维网格,计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外,你可以假设该网格的四条边均被水包围。

直接读题有四个细节经常被忽略。第一,输入是字符'1'和'0',不是整数 1 和 0,意味着你在 Python 里写grid[i][j] == 1永远不成立,判断必须是=='1',我第一次用 Java 刷时也踩过char == 1的坑。第二,岛屿由“上下左右”相邻的陆地构成,是四方向连通,不是八方向,更不是对角线也算。很多人刷到后面变种题“岛屿的周长”时,把斜对角也算进去,整个答案就跑偏了。第三,“网格的四条边均被水包围”这句话是在告诉我们不需要单独处理边界外的虚拟水域,越界直接停止探索即可,不用给网格额外加一圈'0'。第四,岛屿数量的本质是统计连通分量个数,同样的思路换个问法,从“统计多少块”变成“统计最大的一块多大”,就是力扣 695 岛屿的最大面积。

这题输出要求很简单,返回一个整数即可。但正因为输入输出看起来平平无奇,面试官才有空间在“怎么遍历、怎么标记、怎么优化空间”这三个点上层层追问,把它变成一道可深可浅的经典题。

1.2 网格即图的映射思路

很多人第一次看到这题会懵:二维数组遍历我懂,但这跟图有什么关系?其实网格天然就是一张图,每个格子是一个节点,上下左右相邻的格子之间有一条无向边。只不过这张图没有用邻接表存储,而是用坐标索引:节点(i, j)的邻居就是(i-1, j)、(i+1, j)、(i, j-1)、(i, j+1),唯一的额外工作就是判断坐标是否越界。

做这个映射之后,问题立刻变得清晰:“岛屿”就是由若干'1'节点组成的连通分量,岛屿数量就是这张“网格图”里所有由'1'构成的连通分量的个数。于是问题变成一个很标准的图论问题:给定一张图,统计满足某种条件的连通分量数量。树的遍历、图的遍历在这里全部适用,DFS 前序遍历、BFS 层序扩展、并查集合并,三套方案都能解,时间复杂度也都是 O(m×n),其中 m 是行数、n 是列数。

我在带新人时有个习惯:只要看到“二维矩阵 + 连通块 + 数量/面积/边界”这三个关键词的组合,直接往图论上靠,大概率没错。这道题就是这种思维模式的最佳训练场。

1.3 为什么它是面试高频题

这题能成为高频题,我认为有三个原因。一是代码量小,主函数加一个辅助函数大约二十行,面试官有足够时间在写完之后继续追问,而不是看候选人憋半天代码;二是它同时考察了二维数组坐标处理、递归或迭代遍历、以及“如何标记已访问”这个基础能力,一个知识点能挖出好几个层面的问题;三是它变种极多,问完这题面试官可以顺理成章接着问“最大面积”“周长”“被围绕的区域”,整套考察闭环非常成熟。

我自己面试别人时也爱用这题,尤其是让候选人讲思路而不是直接写代码。能说出“把每个格子看成图的节点”的人,和图论有关的后续问题基本都能聊下去;只会背模板的人,在问到“为什么这里要把'1'改成'0'”的时候通常就会卡壳。这也是我建议每个准备算法面试的人都把这题吃透的根本原因。

2. 三种主流解法:DFS、BFS、并查集

2.1 DFS:把“访问过”写进网格里

DFS 的思路可以用一句话概括:遍历网格中的每个格子,一旦遇到'1',就说明发现了一座新岛屿,计数器加 1,然后递归地把这座岛上所有相邻的'1'全部标记成'0'。这样后续遍历不会再碰到这座岛的任何部分,自然就不会重复计数。

很多初学者会问:为什么要把'1'改成'0',而不是单独维护一个 visited 二维数组?因为这道题允许修改原输入,原地改数组既省了一张同样大小的布尔表,又把“访问过”和“原来是水”统一处理了,判断条件就可以简化为grid[i][j] == '1'。但如果你面对的是不允许修改输入的场景,或者面试官明确说“不要改变原数组”,那就得换 visited 方案,代价是多一个 O(m×n) 的布尔数组空间。

递归版本实现简单,理解起来也直观,但它有一个隐患:当网格是一个全'1'的超大矩阵时,递归深度可能达到 m×n 的级别。Python 默认递归深度大约 1000,C++ 的调用栈虽然深一些,但也不是无限。力扣的测试数据里确实存在这种极端用例,所以后面我会讲怎么换成 BFS 或手动栈来规避。

2.2 BFS:迭代版,避免递归栈溢出

BFS 是 DFS 的迭代替代方案,核心逻辑是:遇到'1'时先把它改成'0'并入队,然后循环弹出队首坐标,把它的四个相邻格子中仍是'1'的全部改成'0'并入队。这样一层层向外扩展,直到队列为空,说明这座岛已经完全被“淹没”。

这里有一个新手最容易犯的错:只在出队时才标记格子为'0',导致同一个格子被多个邻居重复入队。举个简单例子,一个三格连成 L 形的岛,如果出队时才标记,中间的格子可能被左边和上边同时加入队列,队列里出现大量重复坐标,轻则多做无效循环,重则死循环。正确做法是“入队即标记”,也就是在把邻居加入队列的那一刻就把它改成'0',保证每个节点最多入队一次。

BFS 的优势在于没有递归栈溢出风险,而且在窄长的网格上队列长度很可控。实际刷题时,如果题目数据范围很大,我一般优先写 BFS,稳。

2.3 并查集:把连通问题交给数据结构

并查集是第三条路,也是最能体现数据结构思维的做法。思想是:给每个格子分配一个从 0 到 m×n-1 的唯一编号,编号公式是行号 × 总列数 + 列号;然后扫描网格,对于每一个'1'格子,尝试把它与上方、左方的'1'邻居合并。初始时把并查集的计数器设为陆地的总数,每成功合并一次,计数器减 1,最终计数器的值就是岛屿数量。

这里有一个自然的问题:为什么合并时只需要看上方和左方?因为扫描方向是逐行从左到右、从上到下,每个格子的上、左邻居如果存在'1',那么这两条边已经覆盖了所有横向和纵向的相邻关系。右边和下边的邻居在当前格子被扫描到的时候还没有处理,但等扫描到那个邻居时,它自然会回头检查自己的左方和上方,也就是当前格子,所以不会漏掉任何一条边。

并查集解法的空间复杂度是 O(m×n),因为要维护 parent 数组和 rank 数组;时间上因为路径压缩和按秩合并,每次操作的均摊开销接近常数,整体还是 O(m×n)。理解并查集解法还有一个额外收获:如果题目变成“动态加入陆地,每加一块后问当前有多少岛屿”,也就是力扣 305 岛屿数量 II,并查集就是最优解,DFS 和 BFS 反而难以高效处理。

2.4 四种实现横向对比

对比维度DFS(递归)DFS(手动栈)BFS(队列)并查集
时间复杂度O(m×n)O(m×n)O(m×n)O(m×n×α),近似 O(m×n)
空间复杂度最坏 O(m×n)最坏 O(m×n)队列最坏 O(m×n)O(m×n)
是否修改原数组默认修改默认修改默认修改不修改
栈溢出风险高可控无无
编码难度低中中偏高

我在实际刷题时的一个参考思路是:追求简短就用递归 DFS,担心爆栈就用 BFS,面试官追问“不修改原数组”或“动态加陆地”时再切并查集。三种解法都写一遍,这道题才算真正吃透。

3. 手写实现:完整代码与关键细节分析

3.1 DFS 实现:Python 与 C++ 双版本

先看 Python 递归 DFS 版本,这也是我推荐第一次刷这道题的人先写的版本。

def num_islands(grid): if not grid or not grid[0]: return 0 m, n = len(grid), len(grid[0]) count = 0 def dfs(i, j): if i < 0 or j < 0 or i >= m 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) for i in range(m): for j in range(n): if grid[i][j] == '1': count += 1 dfs(i, j) return count

这段代码有几个细节值得注意。第一,if not grid or not grid[0]同时处理了空数组和只有空行的情况,顺序不能反,否则grid[0]可能越界。第二,递归边界条件写在函数最前面,一进入就判断,简洁且不容易漏。第三,把'1'改成'0'必须在递归之前完成,否则同一个格子会被上下左右四条路径反复访问,造成死循环。

C++ 版本结构完全一致,只是要注意引用传递,否则每次递归都会拷贝整个二维数组:

class Solution { public: int numIslands(vector<vector<char>>& grid) { if (grid.empty() || grid[0].empty()) return 0; int m = grid.size(), n = grid[0].size(); 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; } void dfs(vector<vector<char>>& grid, int i, int j) { if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || 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、1×n、m×1 这三种极端形状,能帮你确认坐标处理和递归终止条件都没有问题。

3.2 BFS 实现:入队即标记

BFS 版本用 Python 写最舒服,因为collections.deque的popleft()是 O(1),而如果用 list 的pop(0)是 O(n),大数据量下会慢很多。

from collections import deque def num_islands(grid): if not grid or not grid[0]: return 0 m, n = len(grid), len(grid[0]) count = 0 directions = [(1, 0), (-1, 0), (0, 1), (0, -1)] for i in range(m): for j in range(n): if grid[i][j] == '1': count += 1 grid[i][j] = '0' queue = deque([(i, j)]) while queue: x, y = queue.popleft() for dx, dy in directions: nx, ny = x + dx, y + dy if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1': grid[nx][ny] = '0' queue.append((nx, ny)) return count

这里我用了方向数组directions而不是写四段重复的if,这是我自己刷到后期才养成的习惯。网格类题目几乎都要处理“四个方向”的遍历,把方向抽象成数组之后,代码量减少、出错率下降,后续遇到“八个方向”“骑士走法”等问题也能复用同一套路。

这段代码里最容易踩的坑就是“入队即标记”。注意看第 15 行和第 16 行,我在把邻居加入队列之前就执行了grid[nx][ny] = '0'。如果这两行顺序反了,先入队再标记,队列中就会出现重复坐标,最坏情况下队列会膨胀到远超网格大小,性能直接崩掉。

3.3 并查集实现:编号、合并、计数

并查集解法写起来稍长,但每一块职责都很清晰。先定义并查集数据结构,再写主逻辑:

class UnionFind: def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n self.count = 0 def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) return self.parent[x] def union(self, x, y): rx, ry = self.find(x), self.find(y) if rx == ry: return if self.rank[rx] < self.rank[ry]: self.parent[rx] = ry elif self.rank[rx] > self.rank[ry]: self.parent[ry] = rx else: self.parent[ry] = rx self.rank[rx] += 1 self.count -= 1 def num_islands(grid): if not grid or not grid[0]: return 0 m, n = len(grid), len(grid[0]) uf = UnionFind(m * n) uf.count = sum(line.count('1') for line in grid) for i in range(m): for j in range(n): if grid[i][j] == '1': idx = i * n + j if i > 0 and grid[i - 1][j] == '1': uf.union(idx, (i - 1) * n + j) if j > 0 and grid[i][j - 1] == '1': uf.union(idx, i * n + j - 1) return uf.count

这段代码有三个关键点。第一,并查集的计数初始值不是 0,而是陆地总数,因为每个陆地初始都独立成岛,合并一次就减少一座岛;这比“初始为 0,每次发现一块全新疆域再加 1”要直观得多。第二,find里用了路径压缩,递归地把父节点指向根节点,这样后续查找近乎 O(1)。第三,主循环里只合并上方和左方,原因在 2.3 里说过,扫描顺序保证了不会漏边。

我最初写并查集时犯过一个错:在union里判断rx == ry后直接return,忘记这时两个节点已经在同一个岛上,不应该再减计数。后来我把它想成“只有真正把两棵树合并成一棵树时才需要减一”,才彻底纠正过来。

3.4 visited 数组与原地修改的取舍

三种解法里,DFS 和 BFS 默认都修改了grid,这是最简单也最推荐的做法。但有些面试场景会明确要求“不能修改输入”,或者你需要在一次遍历结束后保留原始网格做后续计算,这时就必须引入 visited 数组。

用 visited 数组时,代码结构几乎不变,只是把grid[i][j] = '0'替换成visited[i][j] = True,判断条件从grid[nx][ny] == '1'变成grid[nx][ny] == '1' and not visited[nx][ny]。代价是空间复杂度从 O(1)(原地修改)变成 O(m×n)。我自己的经验是:刷题时先问清楚题目允不允许修改原数组,如果不确定,就按“不修改”来写 visited 版本,这样最保险,也不会被面试官挑毛病。

4. 边界条件与易错点:实战踩坑记录

4.1 空数组与不规则输入

题目给的是标准[[char]]输入,但实际刷题时你可能会遇到变种:输入是空列表[],或者列表里有一个空列表[[]]。这两种情况如果不处理,代码会在grid[0]或len(grid[0])处抛异常。

我在 C++ 里见过更隐蔽的版本:vector<vector<char>>本身不为空,但某些行长度不一样,形成“锯齿数组”。虽然力扣测试不会这样,但面试官让你手写代码时可以追问一句“假设所有行等长,对吧”,既展示了你对输入假设的敏感度,也规避了后续的边界问题。

统一做法是函数第一行就写:

if not grid or not grid[0]: return 0

这个判断同时覆盖了空数组和空行,没有多余分支,建议背下来形成肌肉记忆。

4.2 全 '1' 大矩阵与递归深度

如果输入是一个 1000×1000 的全'1'矩阵,DFS 递归从(0,0)进入后,会沿着四个方向一路深入,递归深度最坏能达到 100 万级别。Python 默认递归深度上限大约是 1000,这种用例下直接报RecursionError,C++ 则可能直接栈溢出崩溃。

有三种规避方案:一是把递归 DFS 改成手动栈,用 list 模拟栈;二是直接用 BFS 版本,队列没有递归深度问题;三是用并查集,从头到尾不涉及递归调用本身(虽然find的路径压缩如果用递归写法也有类似隐患,但可以改成迭代写法)。

我个人的建议是:准备面试时把 BFS 作为默认版本记忆,因为网格类题目几乎没有不能换 BFS 的。手动栈虽然也能解决爆栈问题,但代码里需要自己维护(i, j)坐标栈和入栈前标记两个细节,写起来不如 BFS 直觉。

4.3 四方向误写为八方向

题目明确说“水平方向和竖直方向”,也就是只考虑上下左右四个邻居。但很多人在写方向数组时顺手写成了八个方向,把对角线格子也当成同一座岛的成员,导致原本应该分开的两座岛被误判成一座,返回的岛屿数量偏少。

我在一次模拟面试里就见过候选人把directions写成:

directions = [(1,0), (-1,0), (0,1), (0,-1), (1,1), (1,-1), (-1,1), (-1,-1)]

结果一个由对角线相连的棋盘格图案被算成一块,答案直接错了。如果你担心记混,可以记一个口诀:岛屿讲四邻,像素连通才讲八邻。图像处理里的八连通和这里不是一回事,千万别混。

4.4 BFS 重复入队问题

前面提过,BFS 里“出队时才标记”会导致重复入队,这里展开说一个我实际调试过的例子。假设网格是:

1 1 1 1

从(0,0)开始,如果入队时不标记,第一次循环会把(0,1)和(1,0)入队;第二次循环处理(0,1)时,发现(1,1)是'1'又入队,同时它还会再看(0,0),发现已经是'0'所以不动;第三次处理(1,0)时,又发现(1,1)是'1',再次入队。结果(1,1)被加入队列两次,虽然最终结果可能碰巧正确,但队列长度膨胀,而且在更复杂的图形里可能出现死循环。

正确写法是“入队即标记”,确保每个格子最多进入队列一次。这个教训同样适用于图的最短路径问题,BFS 处理节点时永远要在入队时登记访问状态,而不是在出队时。

5. 复杂度分析与变种题扩展

5.1 时间和空间复杂度深挖

三种解法的时间复杂度都是 O(m×n),原因相同:每个格子最多被访问常数次。DFS 和 BFS 中,一个格子一旦被改成'0'就再也不会被当作处理对象,外层主循环还会把每个格子看一遍,所以总共是遍历一遍加每座岛内部访问一遍,合起来还是 O(m×n)。并查集则是在每个'1'格子上做常数次find/union,均摊下来也接近 O(m×n)。

空间复杂度上,三种解法有区别。DFS 递归版的空间主要消耗在调用栈上,全'1'矩阵最坏深度为 m×n,所以空间 O(m×n)。BFS 的空间是队列的最大长度,在窄长矩阵如 1×n 时队列只有常数长度,在满矩阵时最坏也能到 O(m×n),所以通常说“最坏 O(m×n),可近似记为 O(min(m,n))”。并查集固定需要 parent 和 rank 两个长度为 m×n 的数组,空间 O(m×n)。

这里有个常见的面试追问:“你刚才说 BFS 空间是 O(min(m,n)),能不能解释一下?”这个问题其实考察你对队列在网格上扩散规律的理解。BFS 在网格里是按“层”扩散的,某一时刻队列中存放的是当前层和下一层的所有节点,而层的最宽处受限于矩阵的短边,所以可以写成 O(min(m,n))。面试时能把这个道理讲清楚,比公式背得熟更有说服力。

5.2 变种题:最大面积、周长、被围绕的区域

吃透这题之后,直接受益的是下面几个高频变种。

695 岛屿的最大面积:DFS 不再只计数,而是让每个 DFS 返回它遍历过的格子数,主循环里用 max 更新。核心逻辑和这题一模一样,只多一个返回值。

463 岛屿的周长:每个'1'格子本身贡献 4 条边,但每和相邻陆地在某个方向共享一条边,总周长就减 2。也可以 DFS 时遇到边界或水就加 1,遇到已访问格子就跳过。两种写法都能过,后者和本文章的 DFS 结构更接近。

130 被围绕的区域:反向思维,先找边界上的'O',从边界出发把所有能连到的'O'标记成特殊字符,比如'#',然后全图扫描把剩余的'O'改成'X',最后把'#'改回'O'。这个“先逆向标记再统一处理”的思路,和岛屿数量里的“先淹岛再数数”异曲同工。

1254 统计封闭岛屿的数量:先把边界上能到达的所有'0'区域“淹没”,再对内部的'0'块数连通分量,数出来的就是被'1'包围的封闭岛屿。

我的建议是刷完这题,按顺序把 695、463、130 三题各写一遍,你会发现自己对“方向数组 + 状态标记 + 连通分量”这套组合拳已经形成肌肉记忆。

5.3 进阶思路:动态岛屿与沉没法思想

力扣 305 岛屿数量 II 是这题的动态版本:网格初始全是水,每次操作在指定位置把水变成陆地,问每次操作后有多少岛屿。DFS 和 BFS 每次都要重新扫描全图,复杂度直接爆炸,并查集则天然支持这种增量操作。每次新增一块陆地时,就把它和四周的'1'邻居合并,计数器加 1 减去成功合并次数,即可得到新的岛屿数量。

还有一个思想值得单独提出来:这道题里的“把陆地改成水”其实是经典的“沉没法”。你想象一个岛屿浮在水面上,你每找到一座岛就让它沉下去,那么扫完之后所有岛屿都被沉没了,计数也完成了。这个思想在二维网格连通类问题里非常好用,很多题解里提到的“flood fill”算法就是它。理解了这个比喻,你就能明白为什么可以原地修改网格,也就能在面试时把这个“为什么这样不会影响后续遍历”解释得特别生动。

6. 面试表达与现场调试技巧

6.1 从题意到口述思路的引导顺序

面试中拿到这道题,不要上来就写代码。我推荐的表达顺序是:先和面试官确认输入类型和边界,再快速建模,把“网格是图、岛屿是连通分量”这句话说出来,然后给出你最顺手的一种解法。

例如可以这样说:“我先把网格抽象成图,每个格子是一个节点,上下左右是边,那么岛屿就是由字符'1'构成的连通分量。我可以遍历每个格子,遇到一个'1'就把计数加一,然后通过 DFS 把这个连通分量里的所有'1'都改成'0',这样后续就不会重复计数。时间复杂度 O(m×n),空间上递归最深可能 O(m×n)。如果担心大矩阵爆栈,我可以换成 BFS 用队列实现同样逻辑。”

这样一段话既展示了图形建模能力,又主动交代了复杂度和潜在风险,还给出了备选方案。面试官大概率会点点头,让你直接写 BFS 版本。

6.2 口头分析复杂度的正确姿势

口头分析复杂度时有个常见误区:只说“O(m×n)”就停了。再往深说一层,面试官的印象会好很多。

对于 DFS,你可以说:“每个格子最多被修改一次,外层循环每个格子也最多检查一次,所以时间是 O(m×n)。空间上,最坏情况是整张图全是陆地,递归深度达到 m×n,所以空间也是 O(m×n)。”

对于 BFS,你补上一句:“队列里某一时刻最多存的是 BFS 的某一层的节点,在网格类问题里可以记为 O(min(m,n)),最坏不超过 O(m×n)。”

对于并查集,你加一句:“并查集两个数组的长度都是 m×n,空间 O(m×n);由于路径压缩和按秩合并,均摊时间接近常数,整体 O(m×n)。”能把话说得这么细,说明你是真的理解,而不是背答案。

6.3 手写代码时的顺序建议

手写代码时,我建议按下面这个顺序来,能有效减少划线涂改:

  1. 先写空输入判断。这一行几乎不会错,放在最前面能帮你预热。
  2. 定义 m、n、计数器和方向数组。
  3. 写主循环,遇到'1'计数加一,然后调用辅助函数。
  4. 最后写辅助函数,也就是 DFS 或 BFS 的核心。

有一个小技巧:如果你在写 BFS,先把grid[nx][ny] = '0'写在queue.append之前,从一开始就养成正确的标记习惯。如果你写 DFS,把越界和访问判断合并到一行,像if i < 0 or ... or grid[i][j] == '0': return,可以减少一个嵌套层级。

写完后至少跑三个测试用例:一个 1×1 全陆地、一个多行多列含多个岛、一个全是水的矩阵。这三个用例能覆盖绝大多数低级错误,跑完再主动说“我测一下空数组”,面试官通常就不会再挑边界条件的刺了。

6.4 分享一个我在调试时常用的方法

如果代码跑出来结果不对,而你又看不出哪里有问题,有一个很笨但很有效的方法:在每次把'1'改成'0'的地方打印当前坐标和整个网格状态。我自己第一次刷这题时,就是靠这个方法发现了一个微妙的 bug:我把行列坐标写反了,grid[x][y]写成了grid[y][x],导致在非方阵上索引越界而结果错误。

这类坐标错位在方阵上不会暴露,只有跑3×5这种非方阵用例时才看得出来。所以我的建议是:写完代码后,刻意用一个行数和列数不一样的测试用例验证一遍,比如grid = [["1","0","1","0","1"]],这能快速暴露m和n用反的问题。


最后再分享一点个人体会。我刷这题第一遍时,递归 DFS 写得磕磕绊绊,直到某天突然想通“把访问过的陆地改水”这个操作本身就是在做连通分量标记,之后遇到 flood fill 类题目全都会写了。第二遍刷是因为有次线上笔试遇到全'1'大矩阵导致递归爆栈,才老老实实把 BFS 版本背了下来。第三遍是准备系统设计类面试时顺手复习并查集,发现这题是教科书级例题。如果你也在准备面试,我认真建议把这题的三种解法都各写一遍,再顺手把 695、463、130 三题刷掉,之后再看任何“二维网格 + 连通块”的组合题,都会觉得格外轻松。

需要专业的网站建设服务?

联系我们获取免费的网站建设咨询和方案报价,让我们帮助您实现业务目标

立即咨询