知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 12 - 岛屿数量 ## 题目(LeetCode 200) 给你一个 '1'(陆地)和 '0'(水)组成的二维网格,计算岛屿数量。 ## 解法:DFS 沉岛 ```java class Solution { public int numIslands(char[][] grid) { int count = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == '1') { dfs(grid, i, j); count++; } } } return count; } private void dfs(char[][] grid, int i, int j) { if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') return; grid[i][j] = '0'; // 沉岛,标记已访问 dfs(grid, i + 1, j); dfs(grid, i - 1, j); dfs(grid, i, j + 1); dfs(grid, i, j - 1); } } ``` > 💬 **Q:给出示例及详细解释** > > 用以下网格演示(`1` 是陆地,`0` 是水): > > ``` > 初始状态: > 1 1 0 0 > 1 0 0 1 > 0 0 1 1 > ``` > > **外层双重循环逐格扫描:** > > --- > > **第 1 步:扫描到 (0,0) = '1',发现岛屿,count=1,调用 dfs(0,0)** > > ``` > dfs(0,0):把 (0,0) 沉掉,变 '0',然后向四个方向扩散 > → dfs(1,0):把 (1,0) 沉掉,继续扩散 > → dfs(2,0):grid[2][0]='0',直接返回 > → dfs(0,0):已经是 '0',直接返回 > → dfs(1,1):grid[1][1]='0',直接返回 > → dfs(1,-1):越界,直接返回 > → dfs(-1,0):越界,直接返回 > → dfs(0,1):把 (0,1) 沉掉,继续扩散 > → dfs(1,1):grid[1][1]='0',直接返回 > → dfs(-1,1):越界,直接返回 > → dfs(0,2):grid[0][2]='0',直接返回 > → dfs(0,0):已经是 '0',直接返回 > → dfs(0,-1):越界,直接返回 > > dfs 结束后,网格变为: > 0 0 0 0 ← (0,0)(0,1)(1,0) 都被沉掉了 > 0 0 0 1 > 0 0 1 1 > ``` > > --- > > **第 2 步:继续扫描,(0,1)(1,0) 已经是 '0',跳过** > > 扫描到 (1,3) = '1',发现岛屿,count=2,调用 dfs(1,3) > > ``` > dfs(1,3):把 (1,3) 沉掉,向四个方向扩散 > → dfs(2,3):把 (2,3) 沉掉,继续扩散 > → dfs(3,3):越界,返回 > → dfs(1,3):已经是 '0',返回 > → dfs(2,4):越界,返回 > → dfs(2,2):把 (2,2) 沉掉,继续扩散 > → 四个方向都是 '0' 或越界,全部返回 > → dfs(0,3):grid[0][3]='0',返回 > → dfs(1,4):越界,返回 > → dfs(1,2):grid[1][2]='0',返回 > > dfs 结束后,网格变为: > 0 0 0 0 > 0 0 0 0 ← (1,3) 被沉掉 > 0 0 0 0 ← (2,2)(2,3) 被沉掉 > ``` > > --- > > **第 3 步:继续扫描,剩余全是 '0',不再触发 dfs** > > 最终 count = 2,答案正确。 > > --- > > **关键理解:** > > ``` > 为什么叫"沉岛"? > 把访问过的陆地 '1' 改成 '0'(沉入水中) > 这样就不需要额外的 visited 数组,直接用原地修改标记已访问 > > 为什么 count++ 在 dfs 之后? > dfs 会把整个连通的岛屿全部沉掉 > dfs 返回后,这整块岛屿只算 1 个,所以 count 只加 1 > > 为什么四个方向都要递归? > 岛屿可以是任意形状,上下左右相连的 '1' 都属于同一个岛 > 必须四个方向都探索,才能把整块岛屿完整地沉掉 > ``` ## 复杂度 - 时间 O(m×n),空间 O(m×n) 最坏递归深度 ## 一句话总结 遇到 '1' 就 DFS 把整个岛沉掉,计数加一。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入