🔗 LeetCode 200 - Number of Islands
📌 题目描述
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的二维网格 grid，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或垂直方向相邻的陆地连接而成。
🔍 示例
1
2
3
4
5
6
7
8
| 输入:
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出: 3
|
💡 解题思路
经典的 深度优先搜索（DFS） 问题：
- 从每个未访问的 ‘1’ 出发进行 DFS，将连通的所有 ‘1’ 标记为 ‘0’；
- 每次遍历完整个岛屿，岛屿数量加 1；
- 或可使用 BFS、并查集进行拓展解法。
时间复杂度：O(m × n)
空间复杂度：O(m × n)
✅ JavaScript 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| var numIslands = function(grid) {
let count = 0;
const rows = grid.length, cols = grid[0].length;
const dfs = (i, j) => {
if (i < 0 || i >= rows || j < 0 || j >= cols || 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 (let i = 0; i < rows; i++) {
for (let j = 0; j < cols; j++) {
if (grid[i][j] === '1') {
dfs(i, j);
count++;
}
}
}
return count;
};
|
✅ Swift 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| func numIslands(_ grid: [[Character]]) -> Int {
var grid = grid
let rows = grid.count
let cols = grid[0].count
var count = 0
func dfs(_ i: Int, _ j: Int) {
if i < 0 || i >= rows || j < 0 || j >= cols || 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 0..<rows {
for j in 0..<cols {
if grid[i][j] == "1" {
dfs(i, j)
count += 1
}
}
}
return count
}
|
🧠 思考拓展
- 如何使用 BFS 实现？
- 如何使用并查集（Union-Find）来解决？
- 如果要求标出每个岛屿的坐标集，该如何修改算法？
