美文网首页
2.算法-BFS/DFS

2.算法-BFS/DFS

作者: 做一只有趣的芦苇 | 来源:发表于2020-11-07 21:27 被阅读0次

广度优先搜索BFS

200. 岛屿数量

def numIslands(self, grid: List[List[str]]) -> int:
        lr = len(grid)
        if lr == 0 : return 0
        lc = len(grid[0])
        from collections import deque 
        cnt = 0
        for row in range(lr):
            for col in range(lc):
                if grid[row][col] == '1':
                    cnt += 1
                    grid[row][col] = '0'   #通过赋值为0标记访问过
                    d = deque([(row,col)])
                    while d:
                        (r,c) = d.popleft()
                        for (x,y) in [(r-1,c),(r,c-1),(r+1,c),(r,c+1)]:
                            if 0<=x<lr and  0<=y<lc and grid[x][y]=='1':
                                d.append((x,y))
                                grid[x][y] = '0'
        return cnt

1. 733. 图像渲染

这每日一题不是个简单题目啊。。。 广度优先搜索

def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        currColor = image[sr][sc]
        if currColor == newColor:
            return image
        
        n, m = len(image), len(image[0])
        que = collections.deque([(sr, sc)])
        image[sr][sc] = newColor
        while que:
            x, y = que.popleft()
            for mx, my in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                if 0 <= mx < n and 0 <= my < m and image[mx][my] == currColor:
                    que.append((mx, my))
                    image[mx][my] = newColor
        
        return image

答案里面用到了deque 学习一下,就在原来list的基础上增加了从头部pop extend的各种操作
python deque

相关文章

  • BFS

    [TOC] BFS 和 DFS BFS广度有限搜索和DFS深度优先搜索算法是特别常用的两种算法 DFS 算法就是回...

  • 2.算法-BFS/DFS

    广度优先搜索BFS 200. 岛屿数量[https://leetcode-cn.com/problems/numb...

  • 大一上acm总结

    先说说都学了些什么吧。1 . 三个算法专题,高精度,dfs,bfs,高精度基础应用没什么问题,dfs,bfs,题做...

  • Binary Tree(2)

    BFS vs DFS for Binary Tree What are BFS and DFS for Binar...

  • 图的桥和割点

    内容概要: 图中的桥 图的DFS遍历树和BFS遍历树及其与寻桥算法的关系 图的割点 DFS和BFS的对比小结 桥(...

  • (原创)BFS广度优先算法,看完这篇就够了

    BFS算法 上一篇文章讲解了DFS深度优先遍历的算法,我们说 DFS 顾名思义DEEPTH FIRET,以深度为第...

  • 图的结构 BFS DFS

    题目:BFS 一个队列,一个set集合 题目:DFS 题目:Kruskal算法 题目:Prim Dijkstra算法

  • LeetCode指北-BFS

    BFS就是广度优先算法,BFS相对DFS来说不太直观。BFS中,我们会搜索r的“孙子节点”之前先访问结点r的所有相...

  • 岛屿问题

    岛屿系列题目的核心考点就是用 DFS/BFS 算法遍历二维数组。本文分析DFS算法。 一、框架 因为二维矩阵本质上...

  • [Haskell] DFS与BFS

    1. DFS 2. BFS 参考 Algorithms: A Functional Programming App...

网友评论

      本文标题:2.算法-BFS/DFS

      本文链接:https://www.haomeiwen.com/subject/hizlmktx.html