1. 问题背景与核心需求岛屿数量问题Number of Islands是LeetCode上经典的算法面试题之一编号为200。这道题不仅考察基础算法能力更是检验候选人能否将理论知识转化为实际代码的试金石。题目描述很简单给定一个由1(陆地)和0(水)组成的二维网格计算其中岛屿的数量。岛屿被定义为被水包围的、且通过水平或垂直方向相邻的陆地连接形成的区域。在实际面试中这道题之所以高频出现是因为它能同时考察以下几个关键能力对二维矩阵的基本操作能力深度优先搜索(DFS)和广度优先搜索(BFS)的应用并查集(Union Find)等高级数据结构的理解代码实现的简洁性和边界处理能力提示面试时面试官可能会要求你逐步优化解法从最直观的DFS/BFS开始最终给出并查集等更高效的实现。2. 基础解法DFS与BFS实现2.1 深度优先搜索(DFS)实现DFS是最直观的解法其核心思想是当遇到一个1时就以此为起点向四周扩散搜索将所有相连的1都标记为已访问。这样每次遇到未被访问的1就是一个新岛屿。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] # # 标记为已访问 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 count时间复杂度分析O(M×N)其中M和N分别是网格的行数和列数。因为每个网格最多被访问一次。2.2 广度优先搜索(BFS)实现BFS使用队列来实现同样是从遇到的第一个1开始但采用层序遍历的方式标记所有相连的陆地。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 grid[r][c] 0 # 标记为已访问 queue deque([(r, c)]) 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: grid[nr][nc] 0 queue.append((nr, nc)) return countBFS的时间复杂度同样是O(M×N)但空间复杂度在最坏情况下可能比DFS更高当整个网格都是陆地时队列可能存储O(min(M,N))个元素。3. 高级解法并查集实现3.1 并查集基础概念并查集(Union Find)是一种树型的数据结构用于处理一些不相交集合的合并及查询问题。它支持两种操作Find确定元素属于哪个子集Union将两个子集合并成一个集合在岛屿问题中我们可以把每个1看作一个独立的集合然后通过Union操作将相邻的1合并。3.2 并查集实现代码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: grid[r][c] 0 # 避免重复处理 index r * cols c if r 0 and grid[r-1][c] 1: uf.union(index, (r-1)*cols c) if c 0 and grid[r][c-1] 1: uf.union(index, r*cols (c-1)) return uf.count并查集的时间复杂度可以近似看作O(M×N×α(M×N))其中α是反阿克曼函数增长极其缓慢可以认为是常数时间。4. 两种优化实现方案4.1 迭代式DFS实现递归实现的DFS在网格很大时可能会导致栈溢出。我们可以用显式栈来实现迭代式DFSdef 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 stack [(r, c)] grid[r][c] 0 while stack: row, col stack.pop() 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: grid[nr][nc] 0 stack.append((nr, nc)) return count4.2 原地修改的BFS实现我们可以进一步优化BFS实现减少内存使用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 grid[r][c] 0 queue deque() queue.append((r, c)) while queue: row, col queue.popleft() if row 0 and grid[row-1][col] 1: grid[row-1][col] 0 queue.append((row-1, col)) if row rows-1 and grid[row1][col] 1: grid[row1][col] 0 queue.append((row1, col)) if col 0 and grid[row][col-1] 1: grid[row][col-1] 0 queue.append((row, col-1)) if col cols-1 and grid[row][col1] 1: grid[row][col1] 0 queue.append((row, col1)) return count5. 性能对比与适用场景实现方案时间复杂度空间复杂度适用场景DFS递归O(M×N)O(M×N)网格较小递归深度可控DFS迭代O(M×N)O(M×N)避免递归栈溢出风险BFSO(M×N)O(min(M,N))需要最短路径信息时并查集O(M×N×α(M×N))O(M×N)动态连接问题需要频繁合并注意在实际面试中通常从DFS/BFS开始解释然后根据面试官要求逐步优化。并查集虽然效率高但实现较复杂除非明确要求否则不建议作为首选方案。6. 常见问题与调试技巧6.1 边界条件处理空输入检查首先要判断grid是否为空网格尺寸注意行数和列数的获取方式访问越界在DFS/BFS中检查相邻位置是否越界6.2 标记已访问节点常见错误是忘记标记已访问的节点导致重复计算和无限循环。有三种常用标记方法直接修改原矩阵如将1改为0使用单独的visited矩阵使用哈希表记录已访问坐标6.3 方向数组的使用在DFS/BFS中处理四个方向时可以使用方向数组来简化代码directions [(-1,0),(1,0),(0,-1),(0,1)] for dr, dc in directions: nr, nc r dr, c dc # 检查边界和是否访问6.4 并查集实现中的优化路径压缩在find操作中 flatten 树结构按秩合并在union操作中根据rank决定合并方向一维化处理将二维坐标转换为一维索引7. 实际面试中的扩展问题面试官可能会基于这个问题提出一些变种或扩展问题例如统计岛屿的最大面积计算岛屿的周长形状怪异的岛屿如L形、T形动态岛屿问题网格会随时间变化多个网格的岛屿比较对于这些问题核心解决思路仍然是DFS/BFS或并查集但需要根据具体问题调整算法细节。8. 个人实现经验分享在实际编码实现中我发现有几点特别值得注意测试用例设计除了常规情况一定要测试以下边界情况空网格全0网格全1网格单行或单列网格大型网格测试性能代码风格面试时要注意代码的可读性合理命名变量避免全是r/c/i/j适当添加注释解释关键步骤保持一致的缩进和代码风格提前沟通在开始编码前先向面试官说明你的解题思路确认理解正确。遇到问题时也可以适当寻求提示。复杂度分析准备好解释每种实现的时间复杂度和空间复杂度这是面试官常问的后续问题。逐步优化如果时间允许可以从暴力解法开始逐步优化到更高效的实现展示你的思考过程。