LeetCode 200题：岛屿数量问题的三种解法与优化

1. 岛屿数量问题概述LeetCode 200题岛屿数量是算法面试中的经典问题考察的是图的遍历和搜索能力。题目给定一个由1(陆地)和0(水)组成的二维网格要求计算网格中岛屿的数量。岛屿被定义为由水平或垂直方向上相邻的陆地连接形成的区域。这个问题在实际中有很多应用场景比如图像处理中的连通区域分析、游戏开发中的地图生成、社交网络中的好友圈统计等。理解并掌握这个问题的解法对于准备技术面试的程序员来说至关重要。2. 问题分析与解法思路2.1 问题理解与建模首先我们需要明确几个关键点网格中的每个格子要么是1(陆地)要么是0(水)岛屿是由相邻的1组成的区域相邻指的是上下左右四个方向网格边界外的区域都视为水这个问题可以建模为图论中的连通分量问题其中每个1代表图中的一个节点相邻的1之间存在边。我们的目标就是计算这个图中连通分量的数量。2.2 常见解法比较解决这个问题主要有三种思路深度优先搜索(DFS)从遇到的第一个1开始递归地访问所有相邻的1并将它们标记为已访问广度优先搜索(BFS)同样从第一个1开始但使用队列来按层次访问相邻的1并查集(Union-Find)将相邻的1逐步合并到同一个集合中最后统计集合的数量DFS和BFS的时间复杂度都是O(M×N)其中M和N分别是网格的行数和列数因为每个格子最多被访问一次。空间复杂度在最坏情况下也是O(M×N)因为递归调用栈或队列可能存储所有格子。并查集的时间复杂度可以认为是O(M×N×α(M×N))其中α是阿克曼函数的反函数通常认为是一个很小的常数。空间复杂度是O(M×N)。3. 深度优先搜索(DFS)解法详解3.1 算法步骤DFS是最直观的解法具体步骤如下遍历网格中的每一个格子当遇到1时岛屿数量加1从这个1开始进行DFS将所有相连的1都标记为0(表示已访问)继续遍历剩下的格子3.2 代码实现def numIslands(grid): if not grid: return 0 count 0 rows, cols len(grid), len(grid[0]) def dfs(r, c): if r 0 or c 0 or r rows or c cols or grid[r][c] ! 1: return grid[r][c] 0 # 标记为已访问 dfs(r1, c) # 下 dfs(r-1, c) # 上 dfs(r, c1) # 右 dfs(r, c-1) # 左 for r in range(rows): for c in range(cols): if grid[r][c] 1: count 1 dfs(r, c) return count3.3 复杂度分析时间复杂度O(M×N)每个格子最多被访问一次空间复杂度O(M×N)最坏情况下递归栈的深度可能是整个网格4. 广度优先搜索(BFS)解法详解4.1 算法步骤BFS使用队列来实现具体步骤遍历网格中的每一个格子当遇到1时岛屿数量加1将这个1加入队列并开始BFS从队列中取出一个1将其标记为0并将其相邻的1加入队列重复步骤4直到队列为空4.2 代码实现from collections import deque def numIslands(grid): if not grid: return 0 count 0 rows, cols len(grid), len(grid[0]) for r in range(rows): for c in range(cols): if grid[r][c] 1: count 1 queue deque([(r, c)]) grid[r][c] 0 # 标记为已访问 while queue: row, col queue.popleft() for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: nr, nc row dr, col dc if 0 nr rows and 0 nc cols and grid[nr][nc] 1: queue.append((nr, nc)) grid[nr][nc] 0 return count4.3 复杂度分析时间复杂度O(M×N)每个格子最多被访问一次空间复杂度O(min(M,N))队列的大小最多是网格的较短边5. 并查集(Union-Find)解法详解5.1 并查集基础并查集是一种数据结构主要用于处理不相交集合的合并与查询问题。它支持两种操作Find查找元素属于哪个集合Union合并两个集合5.2 算法步骤初始化并查集每个1的格子是一个独立的集合遍历网格对于每个1检查其右边和下边的格子如果相邻格子也是1则合并这两个集合最后统计集合的数量5.3 代码实现class UnionFind: def __init__(self, grid): rows, cols len(grid), len(grid[0]) self.parent [i for i in range(rows * cols)] self.rank [0] * (rows * cols) self.count sum(grid[r][c] 1 for r in range(rows) for c in range(cols)) def find(self, i): if self.parent[i] ! i: self.parent[i] self.find(self.parent[i]) return self.parent[i] def union(self, x, y): rootx self.find(x) rooty self.find(y) if rootx ! rooty: if self.rank[rootx] self.rank[rooty]: self.parent[rooty] rootx elif self.rank[rootx] self.rank[rooty]: self.parent[rootx] rooty else: self.parent[rooty] rootx self.rank[rootx] 1 self.count - 1 def numIslands(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) uf UnionFind(grid) for r in range(rows): for c in range(cols): if grid[r][c] 1: index r * cols c if r 1 rows and grid[r1][c] 1: uf.union(index, (r1)*cols c) if c 1 cols and grid[r][c1] 1: uf.union(index, r*cols c1) return uf.count5.4 复杂度分析时间复杂度O(M×N×α(M×N))其中α是阿克曼函数的反函数空间复杂度O(M×N)用于存储父节点和秩6. 算法优化与变种6.1 方向数组优化在DFS和BFS中我们可以使用方向数组来简化相邻格子的访问directions [(-1,0),(1,0),(0,-1),(0,1)] # 上下左右这样在遍历相邻格子时代码会更加简洁。6.2 访问标记优化除了修改原网格我们还可以使用额外的visited数组来记录访问状态这在某些不能修改原网格的场景下很有用。6.3 并行计算优化对于非常大的网格可以考虑将网格分割并并行处理不同区域最后合并结果。7. 常见错误与调试技巧7.1 边界检查忘记检查网格边界是常见错误确保在访问grid[r][c]前检查r和c的范围。7.2 无限递归在DFS实现中如果没有正确标记已访问的格子会导致无限递归和栈溢出。7.3 方向遗漏确保检查所有四个方向上下左右不要遗漏任何一个。7.4 字符类型注意题目中的1和0是字符而不是数字比较时要用1而不是1。8. 实际应用与扩展8.1 图像处理在图像处理中类似的算法可以用于识别和统计图像中的连通区域。8.2 游戏开发在游戏地图生成中可以用于确保地图的连通性或者计算可到达的区域。8.3 社交网络可以用于计算社交网络中的好友圈数量或社区发现。8.4 变种问题统计岛屿的最大面积计算岛屿的周长封闭岛屿数量岛屿不接触网格边界不同形状的岛屿数量9. 面试技巧与准备建议9.1 面试常见问题解释你的解法思路和时间复杂度为什么选择DFS/BFS/并查集如何处理非常大的网格如何修改算法来统计岛屿的最大面积9.2 准备建议熟练掌握DFS和BFS的实现理解并查集的数据结构练习相关的变种问题注意代码的整洁性和边界条件9.3 代码风格建议使用有意义的变量名添加必要的注释处理边界条件考虑可读性和可维护性10. 个人实战经验分享在实际刷题过程中我发现以下几点特别重要理解问题本质不要急于编码先彻底理解题目要求和边界条件画图辅助对于网格问题画一个小例子有助于理解算法流程逐步优化先实现基础解法再考虑优化空间和时间复杂度测试用例设计各种边界情况的测试用例如空网格、全1网格、全0网格等对于LeetCode 200这样的经典题目建议至少用两种不同的方法实现并比较它们的优缺点。这不仅有助于深入理解算法也能在面试中展示你的全面思考能力。