网站建设可以先备案嘛,mvc5网站开发之美,温州网站设计工作室,邢台网站123733.图像渲染
题目链接#xff1a;https://leetcode.com/problems/flood-fill
解法#xff1a;
可以用深度优先搜索和广度优先搜索。
深度优先搜索。每次搜索到一个方格时#xff0c;如果其与初始位置的方格颜色相同#xff0c;就将该方格的染色#xff0c;然后继续对…733.图像渲染
题目链接https://leetcode.com/problems/flood-fill
解法
可以用深度优先搜索和广度优先搜索。
深度优先搜索。每次搜索到一个方格时如果其与初始位置的方格颜色相同就将该方格的染色然后继续对其上下左右4个方位进行染色如果不相同则进行返回。
因为初始位置的颜色会被修改所以我们需要保存初始位置的颜色以便于之后的更新操作。
广度优先搜索。使用队列每次搜索到一个方格时如果其与初始位置的方格颜色相同就将该方格的染色并把上下左右4个方位加入队列。遵循先进先出而不是把某个位置深挖到底。
需要注意的是如果算法开始之前当前的颜色已经和需要染的颜色相同了就直接返回因为如果相邻点和当前颜色相同那么就和需要染的颜色相同不需要再染如果相邻点和当前颜色不相同那么没法染。所以就是不用操作了。
参考题解BFSDFS
边界条件当前的颜色和需要染的颜色相同。
时间复杂度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 imagedef 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:returnimage[sr][sc] self.new_colordirections [(-1, 0),(1,0),(0, -1),(0, 1)]for d in directions:self.dfs(image, srd[0], scd[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 imageque deque([(sr,sc)])old_color image[sr][sc]image[sr][sc] colordirections [(-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 rd[0], cd[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] colorreturn 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 id[0], jd[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] 1q.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), keylambda 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 0hi - 1 # 调整为左闭右闭区间while lo hi:mid lo (hi - lo) // 2if arr[mid][1] x:lo mid 1else:hi mid - 1return lo # 返回第一个大于x的元素的索引
