Grind75第9天 | 733.图像渲染、542.01矩阵、1235.规划兼职工作

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 image

542.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 dist

1235.规划兼职工作

题目链接：https://leetcode.com/problems/maximum-profit-in-job-scheduling

解法：

动态规划+二分查找，又是一个看了很久题解也没看明白的题目。再慢慢研究。

参考题解：动态规划+二分查找

边界条件：无

时间复杂度：O(nlogn)，排序的复杂度是 O(nlogn)，遍历+二分查找的复杂度合计是O(nlogn)

空间复杂度：O(n)

class Solution:
    def jobScheduling(self, startTime, endTime, profit):
        n = len(startTime)
        jobs = sorted(zip(startTime, endTime, profit), key=lambda p: p[1])
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            k = self.binary_search(jobs, jobs[i - 1][0], i)
            dp[i] = max(dp[i - 1], dp[k] + jobs[i - 1][2])
        return dp[n]
    
    def binary_search(self, arr, x, hi):
        lo = 0
        hi -= 1  # 调整为左闭右闭区间
        while lo <= hi:
            mid = lo + (hi - lo) // 2

            if arr[mid][1] <= x:
                lo = mid + 1
            else:
                hi = mid - 1
        return lo  # 返回第一个大于x的元素的索引