AlgoViz Lab交互式算法学习Algorithms first
岛屿数量 · 交互式算法学习
计算由上下左右相连陆地组成的岛屿数量。
#200 · 图
岛屿数量
Number of Islands
grid = [["1","1","0"],["1","0","0"],["0","0","1"]]矩阵7 个关键状态
步骤 1发现第一座岛，把起点 (0,0) 改为 0 并入队。
g[0][0]=0, count=100,0
10,1
00,2
11,0
01,1
01,2
02,0
02,1
12,2
islands1queue[(0,0)]
推荐
BFS 队列
时间
O(mn)空间 O(mn)每发现新岛就用队列逐层访问其所有陆地。
1function numIslands(g) {2 let n = 0;3 for (let r = 0; r < g.length; r++)4 for (let c = 0; c < g[0].length; c++)5 if (g[r][c] === '1') {6 n++;7 const q = [8 [r, c]9 ];10 g[r][c] = '0';11 while (q.length) {12 const [x, y] = q.shift();13 for (const [a, b] of [14 [x + 1, y],15 [x - 1, y],16 [x, y + 1],17 [x, y - 1]18 ])19 if (g[a]?.[b] === '1') {20 g[a][b] = '0';21 q.push([a, b])22 }23 }24 } return n;25}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1class Solution {2 private char[][] grid;3 private int m;4 private int n;5 6 public int numIslands(char[][] grid) {7 m = grid.length;8 n = grid[0].length;9 this.grid = grid;10 int ans = 0;11 for (int i = 0; i < m; ++i) {12 for (int j = 0; j < n; ++j) {13 if (grid[i][j] == '1') {14 dfs(i, j);15 ++ans;16 }17 }18 }19 return ans;20 }21 22 private void dfs(int i, int j) {23 grid[i][j] = '0';24 int[] dirs = {-1, 0, 1, 0, -1};25 for (int k = 0; k < 4; ++k) {26 int x = i + dirs[k];27 int y = j + dirs[k + 1];28 if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {29 dfs(x, y);30 }31 }32 }33}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
岛屿数量 · 解法对比
计算由上下左右相连陆地组成的岛屿数量。
- 测试用例
grid = [["1","1","0"],["1","0","0"],["0","0","1"]]- 题目分类
- 图
- 解法对比
- 2
DFS 洪泛填充
遇到未访问陆地就计数，并递归淹没整座岛。
- 时间
O(mn)- 空间
O(mn)
BFS 队列
每发现新岛就用队列逐层访问其所有陆地。
- 时间
O(mn)- 空间
O(mn)