近期主要学习队列和栈,使用dfs和bfs解决问题,并查集还没有学过,所以这道题只使用了前面两种方法。岛屿数量可以说是入门级的搜索题目了,因此将解题思路记录于博客,方便以后复习!
题目描述:
给定一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过==水平方向==或==垂直方向==上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
方法一:深度优先搜索(dfs)
1 | class Solution { |
时间复杂度:O(m × n),遍历二维数组
空间复杂度:O(m × n),整个网格都为陆地
方法二:广度优先搜索(bfs)
1 | class Solution { |
时间复杂度:O(m × n),遍历二维数组
空间复杂度:O( min(m, n) ),整个网格为陆地时,队列的大小可以达到min(m, n)
- 本文作者: a_Gen
- 本文链接: http://imaginee.cn/2020/01/25/LeetCode 200.岛屿数量/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!