733.图像渲染
题目链接：https://leetcode.com/problems/flood-fill
解法：
可以用深度优先搜索和广度优先搜索。
深度优先搜索。每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格的染色，然后继续对其上下左右4个方位进行染色；如果不相同，则进行返回。
因为初始位置的颜色会被修改，所以我们需要保存初始位置的颜色，以便于之后的更新操作。
广度优先搜索。使用队列，每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格的染色，并把上下左右4个方位加入队列。遵循先进先出，而不是把某个位置深挖到底。
需要注意的是，如果算法开始之前，当前的颜色已经和需要染的颜色相同了，就直接返回，因为如果相邻点和当前颜色相同，那么就和需要染的颜色相同，不需要再染，如果相邻点和当前颜色不相同，那么没法染。所以就是不用操作了。
参考题解：BFS+DFS
边界条件：当前的颜色和需要染的颜色相同。
时间复杂度：O(n×m)
空间复杂度：O(n×m)
# DFS
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
# 需要染成的颜色
self.new_color = color
# 初始颜色
self.old_color = image[sr][sc]
self.dfs(image, sr, sc)
return image
def dfs(self, image, sr, sc):
if sr < 0 or sc < 0 or sr >= len(image) or sc >= len(image[0]):
return
# 如果相邻的像素不相同，则返回
if image[sr][sc] != self.old_color:
return
# 如果已经被染色，则返回
if image[sr][sc] == self.new_color:
return
image[sr][sc] = self.new_color
directions = [(-1, 0),(1,0),(0, -1),(0, 1)]
for d in directions:
self.dfs(image, sr+d[0], sc+d[1])# BFS
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
# 这个条件如果不加，那么下面可能无限循环
# 如果当前的颜色就是要染的颜色，那么不同的颜色没法染，相同的颜色不用染，所以不用操作
if image[sr][sc] == color:
return image
que = deque([(sr,sc)])
old_color = image[sr][sc]
image[sr][sc] = color
directions = [(-1,0), (1,0), (0,-1), (0,1)]
m, n = len(image), len(image[0])
while que:
for i in range(len(que)):
r, c = que.popleft()
for d in directions:
new_r, new_c = r+d[0], c+d[1]
if 0 <= new_r < m and 0 <= new_c < n and image[new_r][new_c] == old_color:
que.append((new_r, new_c))
image[new_r][new_c] = color
return image542.01矩阵
题目链接：https://leetcode.com/problems/01-matrix
解法：
这个题动态规划的写法看着很复杂，广度优先搜索的思路非常优雅简洁。
假设矩阵中一共有两个0，其他都是1，如下图的左图所示。首先初始化所有点的距离为0，然后把值为0的这两个点加入队列。接着把0周围的1都计算距离，距离都是1，同时把这些值为1的点加入队列。到弹出值为1的点时，它相邻的且未访问过的点（值也是1），距离都为2，即 dist[i][j] + 1。
这就是大致的思路，从下图也可以看出。
参考题解：BFS
边界条件：无
时间复杂度：O(mn)
空间复杂度：O(mn)
class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
m,n = len(mat), len(mat[0])
dist = [[0]*n for _ in range(m)]
zero_pos = [(i,j) for i in range(m) for j in range(n) if mat[i][j] == 0]
q = deque(zero_pos)
visited = set(zero_pos)
directions = [(-1,0), (1,0), (0,-1), (0,1)]
while q:
i, j = q.popleft()
for d in directions:
new_i, new_j = i+d[0], j+d[1]
# 第一轮先把0附近的1都计算距离
# 第二轮把1附近的1都计算距离
if 0 <= new_i < m and 0 <= new_j < n and (new_i, new_j) not in visited:
dist[new_i][new_j] = dist[i][j] + 1
q.append((new_i, new_j))
visited.add((new_i, new_j))
return dist1235.规划兼职工作
题目链接：https://leetcode.com/problems/maximum-profit-in-job-scheduling
解法：
动态规划+二分查找。这个题的实现细节有些比较坑的地方，我下面总结一下。
1. dp[i]的定义：使用 dp[i] 表示前 i 份兼职工作可以获得的最大报酬，即区间 [0,i−1]的所有兼职工作可以获得的最大报酬。这意味着 dp 是 1 indexed的，而工作的三个列表 starttime, endtime, profit 都是 0 indexed。dp[1] 对应到 starttime[0], endtime[0], profit[0]。
初始时 dp[0]=0=0，表示没有兼职工作时报酬为 0。
2.转移方程：对于 i>0，根据第 i （对应dp中的i，profit中的i-1）份兼职工作是否被选择，我们有以下转移方程：
dp[i] = max(dp[i-1], dp[k] + profit[i-1])
因此我们需要找到小于等于第 i 份兼职的startTime的endTime。这里非常危险，因为存在这种情况：endtime的列表为[1,2,3,3,4]，而第1份兼职的startTime=3，那么我们注意到endtime列表中有两个满足条件的3，而我们需要的是第2个而不是第1个。那么怎么处理呢？
我们转为找到第一个大于startTime的endTime，它的下标为k，那么我们真正需要的就是k-1，对应到dp就是dp[k]。
这就是为什么很多题解用了 python 的bisect_right 函数得到第一个大于startTime的索引k，然后直接使用dp[k]的原因。这里其实省略了过程：由k得到k-1，再因为profit[i-1]对应dp[i]，所以k-1对应dp[k]。说得也没有很严谨，但就是这个思路。
3. 二分查找的实现：这里二分查找的实现和leetcode的二分查找不一样，leetcode的二分查找，列表中的数是唯一的，不存在重复。但是这个题存在重复的case，比如上面举的例子 [1,2,3,3,4]，从中寻找小于等于3的数的索引。如果按照 nums[mid] == 3，return mid，那么得到的就是第1个3的索引，而我们实际想要的是第2个3的索引。
因此二分查找的实现就是同 bisect_right 的功能，返回第一个大于target的数的索引。
参考题解：动态规划+二分查找
边界条件：无
时间复杂度：O(nlogn)，排序的复杂度是 O(nlogn)，遍历+二分查找的复杂度合计是O(nlogn)文章来源：https://www.toymoban.com/news/detail-809431.html
空间复杂度：O(n)文章来源地址https://www.toymoban.com/news/detail-809431.html
class Solution:
def jobScheduling(self, startTime, endTime, profit):
n = len(startTime)
# 按照endTime升序排列
jobs = sorted(zip(startTime, endTime, profit), key=lambda p: p[1])
# dp[i] 是 1 indexed，dp[0]表示无兼职，dp[1]表示1份兼职的最大报酬
# 但 jobs是 0 indexed，dp[1]对应到jobs[0], dp[2]对应到[0,1]左闭右闭区间的jobs，所以 dp[i] 表示前i份兼职（对应job中的i-1）的最大报酬
dp = [0] * (n + 1)
for i in range(1, n + 1):
k = self.binary_search(jobs, jobs[i - 1][0], i-1)
dp[i] = max(dp[i - 1], dp[k] + jobs[i - 1][2])
return dp[n]
def binary_search(self, arr, x, hi):
lo = 0
while lo <= hi:
mid = lo + (hi - lo) // 2
if arr[mid][1] <= x:
lo = mid + 1
else:
hi = mid - 1
return lo # 返回第一个大于x的值的索引到了这里，关于Grind75第9天 | 733.图像渲染、542.01矩阵、1235.规划兼职工作的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
