LeetCode 题解工作台
岛屿数量
给你一个由 '1' （陆地）和 '0' （水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。 示例 1： 输入： grid = [ ['1','1','1','1','0'],…
5
题型
7
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
我们可以使用深度优先搜索（DFS）来遍历每个岛屿。遍历网格中的每个单元格 $(i, j)$，如果该单元格的值为 '1'，则说明我们找到了一个新的岛屿。我们可以从该单元格开始进行 DFS，将与之相连的所有陆地单元格的值都标记为 '0'，以避免重复计数。每次找到一个新的岛屿时，我们将岛屿数量加 1。 时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。其中 和 …
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [ ['1','1','1','1','0'], ['1','1','0','1','0'], ['1','1','0','0','0'], ['0','0','0','0','0'] ] 输出：1
示例 2：
输入：grid = [ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ] 输出：3
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]的值为'0'或'1'
解题思路
方法一：DFS
我们可以使用深度优先搜索（DFS）来遍历每个岛屿。遍历网格中的每个单元格 ，如果该单元格的值为 '1'，则说明我们找到了一个新的岛屿。我们可以从该单元格开始进行 DFS，将与之相连的所有陆地单元格的值都标记为 '0'，以避免重复计数。每次找到一个新的岛屿时，我们将岛屿数量加 1。
时间复杂度 ，空间复杂度 。其中 和 分别为网格的行数和列数。
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(i, j):
grid[i][j] = '0'
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
dfs(x, y)
ans = 0
dirs = (-1, 0, 1, 0, -1)
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
dfs(i, j)
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity varies: DFS/BFS is O(m _n) as each cell is visited once. Union-Find is O(m_ n * α(m _n)) where α is the inverse Ackermann function. Space complexity is O(m_ n) for visited markers or recursion/queue storage depending on the approach. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect array traversal plus DFS/BFS as a primary approach.
- question_mark
Check if candidate handles edge cases like all water or single-cell islands.
- question_mark
Look for marking strategies to prevent revisiting cells and miscounting islands.
常见陷阱
外企场景- error
Failing to mark visited cells, causing infinite loops or double-counting.
- error
Confusing diagonal adjacency with vertical/horizontal adjacency.
- error
Using recursion without stack limits, which may cause stack overflow on large grids.
进阶变体
外企场景- arrow_right_alt
Count islands considering diagonal adjacency as connected.
- arrow_right_alt
Return the size of the largest island instead of the count.
- arrow_right_alt
Allow dynamic addition of land cells and update the island count incrementally.