岛屿数量(DFS / BFS)
哪些公司问过
答案要点
- 遍历网格,遇到 '1' 计数加一,并 DFS/BFS 把整个岛屿标记掉
- DFS 向四个方向扩展,遇到边界或水返回;标记已访问可改为 '0' 或用 visited
- 时间 O(m×n),每个格子最多访问一次;空间取决于递归深度
- 网格很大时用 BFS 或并查集,避免递归栈溢出
- 进阶:最大面积在 DFS 中累计;搭桥用多源 BFS 逐层向外扩展
易错点
- 忘了标记已访问的格子,导致重复计数或死循环
- 递归时没有判断边界
- 网格非常大时递归栈溢出
- 把字符 '1' 和整数 1 混淆
面试官常见追问
- 岛屿的最大面积怎么求?
- 如果要搭桥连接两个岛屿,最少需要多长?
- 除了 DFS,还有什么解法?
- 原地修改网格有什么问题?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。