昨天的遗留问题：
深度遍历和广度优先遍历
在深度遍历中，定义一个全局变量记录结点是否被访问的值，利用递归回溯实现深度访问节点。
广度优先：定义数组标记节点访问状态，利用队列存储某个节点的邻接节点，当队列中节点全部出队表示该节点的邻接节点访问完毕，换另一个节点访问

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/flood-fill
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目733 图像渲染

有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。

你也被给予三个整数 sr , sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。

为了完成 上色工作 ，从初始像素开始，记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为 newColor 。

最后返回 经过上色渲染后的图像 。

class Solution:def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:n, m = len(image), len(image[0])currColor = image[sr][sc]def dfs(x: int, y: int):if image[x][y] == currColor:image[x][y] = colorfor 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:dfs(mx, my)if currColor != color:dfs(sr, sc)return image#用广度有限遍历que = collections.deque([(sr, sc)])image[sr][sc] = colorwhile que:x, y = que.popleft()for x_n,y_m in[(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:if 0 <= x_n < n and 0 <= y_m < m and image[x_n][y_m] == currColor:que.append((x_n,y_m))image[x_n][y_m] =colorreturn image

53 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。

思路 动态规划五部曲：
1 dp[i] 以i为结尾的最大连续子序列的和
2 递推公式 max(num[i] 延续前面的和 dp[i-1]+nums[i] ,前面的全部舍去nums[i] )
3 初始化： dp[0]=nums[0]
4 遍历顺序 for i in range(index,len(nums)): 顺推
5 打印数组

代码

class Solution:def maxSubArray(self, nums: List[int]) -> int:if len(nums)==0:return 0max_=0res=nums[0]for i in range(0,len(nums)):max_=max(max_+nums[i],nums[i])res=max(max_,res)return res

232 用栈实现队列

class MyQueue:def __init__(self):self.stack=[]def push(self, x: int) -> None:return self.stack.append(x)def pop(self) -> int:return self.stack.pop(0)def peek(self) -> int:return self.stack[0]def empty(self) -> bool:if len(self.stack)==0:return Trueelse:return False

278 第一个错误版本
思路：为减少调用次数，采用二分查找法实现

class Solution:def firstBadVersion(self, n: int) -> int:left=1right=nwhile left<=right:mid=(left+right)//2if isBadVersion(mid) and not isBadVersion(mid-1):return midelif isBadVersion(mid) and isBadVersion(mid-1):right=mid-1elif not isBadVersion(mid):left=mid+1

383 赎金信
思路：
利用 dict存储magazine中各字符存在的次数
代码

class Solution:def canConstruct(self, ransomNote: str, magazine: str) -> bool:ran={}mag={'sum':0}for i in magazine:if i not in mag:mag[i]=0else:mag[i]= mag[i]+1mag['sum']=mag['sum']+1for j in ransomNote:if j not in mag:return Falseelse:if mag[j] <0:return Falsemag[j]=mag[j]-1return True     

70 爬楼梯
通过在 n-1 阶的那块一次性爬 1 步来达到 n 楼层，以及通过在 n - 2 阶 一次性爬 2 步来达到 n 楼层。所以就是这两种情况的总和。

某阶楼梯的爬法等于前两种之和
#DP[i] 第i阶楼梯的爬法
# 递推公式： dp[i]=dp[i-1]+dp[i-2]
#初始值
#遍历顺序
#打印

class Solution:def climbStairs(self, n: int) -> int:d0=1d1=1if n==1:return 1d2=d0+d1for i in range(3,n+1):d0=d1d1=d2d2=d0+d1return d2