leetcode的执行用时并不特别准，同一个代码不同提交结果不同。

    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        #深度优先搜索需要函数里定义函数,使用外部函数里的变量，作用域包括内部函数
        max_row=len(image)
        max_col=len(image[0])
        #isvisited=[[False]*len(image[0])]*len(image)
        #向量乘后会造成修改，将该列所有位置更改
        #isvisited=[[False for j in range(len(image[0]))] for i in range(len(image))]
        #print(isvisited)
        curcolor=image[sr][sc]
        def dfs(sr,sc):
            
            #global isvisited

            if curcolor!=image[sr][sc]:
                return
            else:
                image[sr][sc]=newColor
                #print(isvisited,sr,sc)
                #isvisited[sr][sc]=True
                #print(isvisited,sr,sc)
                print("hi")
                if sr+1<len(image):
                    dfs(sr+1,sc)
                if sr-1>=0:
                    dfs(sr-1,sc)
                if sc+1<len(image[0]):
                    dfs(sr,sc+1)
                if sc-1>=0:
                    dfs(sr,sc-1)     
        #print(isvisited)
        if image[sr][sc]!=newColor:
            dfs(sr,sc)
        return image  

非标准写法

 def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        #深度优先搜索需要函数里定义函数,使用外部函数里的变量，作用域包括内部函数
        max_row=len(image)
        max_col=len(image[0])
        #isvisited=[[False]*len(image[0])]*len(image)
        #向量乘后会造成修改，将该列所有位置更改
        isvisited=[[False for j in range(len(image[0]))] for i in range(len(image))]
        #print(isvisited)
        curcolor=image[sr][sc]
        def dfs(sr,sc):
            
            #global isvisited

            if curcolor!=image[sr][sc] or isvisited[sr][sc]:
                return
            else:
                image[sr][sc]=newColor
                #print(isvisited,sr,sc)
                isvisited[sr][sc]=True
                #print(isvisited,sr,sc)
                #print("hi")
                if sr+1<len(image):
                    dfs(sr+1,sc)
                if sr-1>=0:
                    dfs(sr-1,sc)
                if sc+1<len(image[0]):
                    dfs(sr,sc+1)
                if sc-1>=0:
                    dfs(sr,sc-1)     
        #print(isvisited)
        if image[sr][sc]!=newColor:
            dfs(sr,sc)
        return image   

非标准写法

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        isvisited=[[False  for j in range(len(grid[0]))] for i in range(len(grid))]
        def dfs(i,j):
            ans=0
            if isvisited[i][j] or grid[i][j]==0:
                return 0
            else:
                isvisited[i][j]=True
                ans+=1
                for r,c in [(i-1,j),(i+1,j),(i,j+1),(i,j-1)]:
                    if 0<=r<len(grid) and 0<=c<len(grid[0]) and not isvisited[r][c]:
                        ans+=dfs(r,c)
            return ans
        max_area=0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if not isvisited[i][j] and grid[i][j]==1:
                    per_area=dfs(i,j)
                    max_area=max(max_area,per_area)
        return max_area

一遍过，标准写法

掌握好深搜的结构，写出深搜来很简单，栈+树

修改isvisited后和层相关的变量都需要修改（层深度，在该层做的修改）

        order_list=[1,2,3,4]
        order_all=[]
        isvisited=[False]*4
        def dfs(i,cnt,per):
            if cnt==4:
                #print("hi")
                order_all.append([i for i in per])
                return
            else:
                for i in range(4):
                    if not isvisited[i]:
                        isvisited[i]=True
                        cnt+=1
                        per.append(i+1)
                        dfs(i,cnt,per)
                        per.pop()
                        cnt-=1
                        isvisited[i]=False
        for i in range(4):
            isvisited[i]=True
            dfs(i,1,[i+1])
            isvisited[i]=False
        print(order_all)
        print(len(order_all))

1-4的全排列实例

题目描述如下

题

• 注意的是right值的更换是用的满二叉树的性质

• 判断首先判断列表是不是空的，队列的判断也是学问，一般是看left的下一层还存在不，不存在说明list已经包含满了（right指向最后一个）

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

"""



class Solution:
    def connect(self, root: 'Node') -> 'Node':
        #广度搜索+队列
        if root==None:
            return None
        list_node=[None,root]
        left_idx,right_idx=1,2
        while(True):
            if not list_node[left_idx].left:
                break
            for i in range(left_idx,right_idx):
                list_node.append(list_node[i].left)
                list_node.append(list_node[i].right)
            left_idx=right_idx
            right_idx=2*right_idx
        cnt,ch_num=0,1
        #print(len(list_node))
        for i in range(1,len(list_node)):
            cnt+=1
            if cnt==ch_num:
                ch_num*=2
                list_node[i].next=None
                cnt=0
            else:
                list_node[i].next=list_node[i+1]
        list_node.clear()
        return root

使用内存大，但是时间快，也是广度的思想

题目

在给定的网格中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
示例 1：
输入：[[2,1,1],[1,1,0],[0,1,1]]
输出：4

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rotten_list=[(i,j) for j in range(len(grid[0]))for i in range(len(grid)) \
        if grid[i][j]==2]
        q=collections.deque(rotten_list)
        isvisted=[[False]*len(grid[0])for _ in range(len(grid))]
        v_a_flag,ans=False,0
        left,right,move=0,len(q),len(q)
        while q:
            x,y=q.popleft()
            isvisted[x][y]=True
            if left==right:
                right=move
                #print(left,right)
                ans+=1
            left+=1
            ##move+=1
            for nx,ny in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:
                if 0<=nx<len(grid) and 0<=ny<len(grid[0]) and not isvisted[nx][ny]\
                and grid[nx][ny]==1:
                    move+=1
                    isvisted[nx][ny]=True
                    q.append((nx,ny))
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if isvisted[i][j]==False and grid[i][j]==1:
                    #error1马虎，变量名字写错
                    return -1
        #print(isvisted[2][0],grid[2][0])
        return ans

image.png