广度优先搜索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