200. 岛屿数量 python题目DFSBFS

104 阅读 0 评论 69 点赞

我是靠谱客的博主笑点低信封，这篇文章主要介绍200. 岛屿数量 python题目DFSBFS，现在分享给大家，希望可以做个参考。

题目

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

复制代码

遍历–>两种思路: DFS 或者 BFS

DFS

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        nr = len(grid)
        if not nr:
            return 0
        nc = len(grid[0])
        counter = 0
        def dfs(r,c):
            grid[r][c] = '0'
            for x, y in [(r,c-1), (r,c+1), (r+1,c), (r-1,c)]:
                if 0 <= x < nr and 0 <= y < nc and grid[x][y] == '1':
                    dfs(x,y)
        for r in range(nr):
            for c in range(nc):
                if grid[r][c] == '1':
                    counter += 1
                    dfs(r,c)
        return counter

时间复杂度：O(MN)
空间复杂度：O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MMN。
。

BFS

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        nr = len(grid)
        if not nr:
            return 0
        nc = len(grid[0])
        counter = 0
        for r in range(nr):
            for c in range(nc):
                if grid[r][c] == '1':
                    counter += 1
                    grid[r][c] = '0'
                    neighbor = collections.deque([(r, c)])
                    while neighbor:
                        row, col = neighbor.popleft()
                        for x, y in [(row, col-1), (row, col+1), (row+1, col), (row-1, col)]:
                            if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
                                neighbor.append((x, y))
                                grid[x][y] = '0'
        return counter

时间复杂度：O(MN)
空间复杂度：O(min(M,N))
在最坏情况下，整个网格均为陆地，队列的大小可以达到 min(M,N)。
因为BFS是分层遍历的，离出发点最近的一层遍历完再遍历下一层，队列中存放的元素数量最多就是层数的最大值，在这个矩阵中层数是min(M,N),所以空间复杂度是O(min(M,N))