Leetcode 200. 岛屿数量-Toy模板网

这篇具有很好参考价值的文章主要介绍了Leetcode 200. 岛屿数量。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Leetcode 200. 岛屿数量,基础算法与数据结构,Python编程,leetcode,算法

心路历程：

在没有看图论这一章之前看这道题没什么直接的思路，在看完图论之后，学着使用DFS和BFS去套用解决。第一次自己做的时候还是遇到了很多小问题。整体思路很流畅，但是需要处理的细节第一次没怎么处理好，花了很多时间去思考图中的回溯和常规组合/子集回溯问题的区别。
这道题的一个整体思路还是对grid进行遍历，然后标记所有连成一片陆地的点，下次直接跳过。

注意的点：

1、这道题很难用visited=[]然后append的方式去记录访问过的点，只能用visited[i][j]=True这种方式，否则会超时。
2、用DFS时，虽然用的还是回溯的模板，但是由于目的是记录访问过的所有点而不是路径（区域问题而非路径问题），所以不需要恢复现场。
3、用BFS时，如果在出队时记录visited会超时，需要在入队的时候记录visited才行。因为在BFS中队列的长度可能会很长，而且很容易把重复的结点入队。用DFS时，把visited的赋值放在candidate的选择那，也会加快程序的运行，这样就不用在下次收集candicate的时候收集重复的结点了。可以总结为，在visited岛屿问题中，在用到not allvisited[newx][newy]后立刻赋值True。
4、图中的四向问题用dxy = [(0,1), (0,-1), (1,0), (-1,0)]的形式会更清晰简洁。
5、无论是DFS还是BFS，本质在每次处理的都是以i, j为索引的’结点‘。
6、图中的DFS和回溯的唯一区别就是对于visited的维护模式不同，回溯需要pop，图的深搜只要遍历过就下次无论如何也不用考虑了，毕竟搜索的是区域而不是路径。（遍历过的多叉树的路径就保存下来）文章来源地址https://www.toymoban.com/news/detail-842503.html

解法一：DFS+遍历grid

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # DFS + 循环遍历；回溯求区域而不是路径，因此不需要在回溯函数调用后恢复现场
        m, n = len(grid), len(grid[0])
        dxy = [(0,1), (0,-1), (1,0), (-1,0)]
        def dfs(i,j):  # 对i,j区域进行搜索，将联通i,j的陆地全部记录起来。
            # 获取可选集合
            candicate = []
            for dx, dy in dxy:
                newx, newy = i+dx, j+dy
                if 0 <= newx <= m-1 and 0 <= newy <= n-1 and grid[newx][newy] == '1' and not allvisited[newx][newy]:
                    candicate.append([newx, newy])
                    allvisited[newx][newy] = True  # 在用到not allvisited[newx][newy]后立刻赋值
            if not candicate:
                return
            for each in candicate:
                dfs(each[0], each[1])
                # visited.pop()  # 不用恢复了，因为不是要求路径的总和，而是记录遍历过的路径（路径就是一个grid）

        allvisited = [[False]*n for _ in range(m)]  # 用allvisited += visited的那种做法会超时
        num = 0
        for xi in range(m):
            for yi in range(n):
                if not allvisited[xi][yi] and grid[xi][yi] == '1':
                    dfs(xi,yi)
                    num += 1
        return num

解法二：BFS+遍历grid

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # BFS； 没有必要找到每个岛屿的陆地区域，只需要将遍历过的标记上即可；基本图和回溯的任何问题都得记录visited，至少要考虑上一步重复
        from collections import deque
        m, n = len(grid), len(grid[0])
        dxy = [(0,1), (0,-1), (1,0), (-1,0)]
        visited = [[False]*n for _ in range(m)]
        num = 0
        quelen = []
        for i in range(m):
            for j in range(n):
                # 对每个i,j做bfs并标记上搜索过的区域
                if grid[i][j] == '1' and not visited[i][j]:  # 1 和 '1'
                    num += 1
                    que = deque([[i,j]])
                    visited[i][j] = True
                    while que:  # 不需要记录层数
                        quelen.append(len(que))
                        x, y = que.popleft()
                        # visited[x][y] = True  # 出队放会超时
                        for dx, dy in dxy:
                            newx, newy = x+dx, y+dy
                            if 0 <= newx <= m-1 and 0 <= newy <= n-1 and not visited[newx][newy] and grid[newx][newy] == '1':
                                que.append([newx, newy])
                                visited[newx][newy] = True  # 只可以在进队的时候设置visited，出队的时候会超时！
        return num