个人网站备案后做游戏,东莞哪家建网站公司好,网络营销品牌案例分析,品牌网站建设基本流程救命#xff0c;因为实在找不到工作。。。 所以已经开始准备华为OD的笔试题了。。。 但是内心深处不是很想去OD呜呜呜 文章目录 BFS与多源BFS污染水域leetcode 1162:#xff1a;地图分析leetcode 542#xff1a;01矩阵leetcode 1020#xff1a;飞地的数量 BFS与多源BFS
BF…救命因为实在找不到工作。。。 所以已经开始准备华为OD的笔试题了。。。 但是内心深处不是很想去OD呜呜呜 文章目录 BFS与多源BFS污染水域leetcode 1162:地图分析leetcode 54201矩阵leetcode 1020飞地的数量 BFS与多源BFS
BFS广度优先搜索BFS一般用队列实现遵循着先进先出的原则比较典型的例子就是之前说过的二叉树层序遍历。
在二叉树的层序遍历中入口只有一个也就是根节点。在遍历过程中每次都拿出队列的第一个值并把它的衍生值放在队列的最右边。
在二叉树的层序遍历中从上往下一层一层走下去不会出现一个节点重复出现的情况。
多源BFS就像它的名称一样有多个源头也就是入口。一般用在图中以多个入口为起点向周围进行遍历因为从多个入口出发可能走到同一个位置为了防止重复遍历需要对遍历过的位置进行标记。
下面给出了《污染水域》的题解和一些相似的leetcode题目的代码。
污染水域 输入一行字符串字符串可以转换为N*N的数组数组可认为是一个水域判断多少天后水域被全部污染。 数组中只有1和0两个数1表示污染每天只可污染上下左右的水域如果开始全部被污染或永远无法污染则返回-1。 输入101000101输出2说明输入转化为数组是1,0,10,0,01,0,1第一天后水域变为1,1,11,0,11,1,1第二天全部为被污染
这个题就是一个很典型的多源BFS问题首先要找到遍历的入口也就是初始水域中为1的位置。将这些位置都加入队列。 如果水域中不存在1或者水域中全是1那么不需要再进行污染直接返回-1。 我们从每个入口出现向上下左右四个方向进行遍历并标记。如果要遍历的位置已经被标记了或者超过了水域的边界那么就忽略。如果没有被标记则把它加入队列中去。
我们一步一步地完成这个代码。 获取输入构造水域矩阵。 在华为OD的题目中输入需要自己获取所以我们可以先构造一下输入的矩阵。 link list(map(int,input().split()))
n int(math.sqrt(len(link)))
mat [[0]*n for _ in range(n)]现在我们来找多源BFS中的源 并把它存到一个队列中去。 q []
for i in range(n):for j in range(n):mat[i][j] link[i*nj]if link[i*nj]1: # 如果是污染区q.append([i,j])如果区域不存在污染或者全是污染直接返回 - 1。 if not q or len(q) len(link):return -1定义一下遍历的方向和最大天数。 direction [[1,0],[-1,0],[0,1],[0,-1]] # 四个方向
max_num 0 # 求最大天数所以初始化为一个比较小的数开始遍历 while q: # 只要q中有东西就一直遍历cur q.pop(0) # 取出队列的第一个值x, y cur # 当前位置for di in directions: # 遍历四个方向newx xdi[0]newy ydi[1]if newx0 or newy0 or newxn or newyn:continue # 如果越界就跳过if mat[newx][newy]!0:continue # 如果访问过就跳过mat[newx][newy] mat[x][y]1 # 标记当前位置用的数字可以代表与污染区的距离【也就是扩散用的时间】if max_num mat[newx][newy]:max_num mat[newx][newy] # 更新最大天数q.append([newx,newy])
return max_num-1 # 因为mat[x][y]的初始值是1所以这里要-1leetcode 1162:地图分析
https://leetcode.cn/problems/as-far-from-land-as-possible/
这道题也是一个典型的多源BFS。要求的是海洋单元到距离它最近的陆地单元格的距离是最大的可以理解成我们已陆地单元格为源头开始向四周遍历最后访问到的海洋就是距离最远的海洋。
我们用海洋到陆地的距离来标记单元格那么最后找到的海洋的标记就代表了它到离它最近的陆地单元格的距离。
class Solution(object):def maxDistance(self, grid)::type grid: List[List[int]]:rtype: intdirection [[-1,0],[1,0],[0,1],[0,-1]]q []n len(grid)for i in range(n):for j in range(n):if grid[i][j] 1:q.append([i,j])if not q or len(q)n**2:return -1while q:cur q.pop(0)x,y curfor di in direction:tmp_x x di[0]tmp_y y di[1]if tmp_x0 or tmp_y0 or tmp_xn or tmp_yn or grid[tmp_x][tmp_y]!0:continuegrid[tmp_x][tmp_y] grid[x][y]1q.append([tmp_x,tmp_y])return grid[cur[0]][cur[1]]-1leetcode 54201矩阵
https://leetcode.cn/problems/01-matrix/
求每一个非0元素到最近的0的距离。可以理解成以0为起点向周围扩散并用起到到当前位置的距离进行标记。要返回的是距离矩阵其实就是被标记后的矩阵。
class Solution(object):def updateMatrix(self, matrix)::type mat: List[List[int]]:rtype: List[List[int]]q []m len(matrix)n len(matrix[0])for i in range(m):for j in range(n):if matrix[i][j]0:q.append([i,j])else:matrix[i][j] -1direction [[1,0],[-1,0],[0,1],[0,-1]]while q:cur q.pop(0)x,y curfor di in direction:newx xdi[0]newy ydi[1]if newx0 or newy0 or newxm or newyn or matrix[newx][newy]!-1:continuematrix[newx][newy] matrix[x][y]1q.append([newx,newy])return matrixleetcode 1020飞地的数量
https://leetcode.cn/problems/number-of-enclaves/
找到无法离开网格边界的陆地单元格的数量就是找没有和边界相连的陆地单元格的数量。我们可以换个思路找到所有与边界相连的陆地单元格并把它们置0那么剩下的陆地单元格就是不相连的。
我们的源就是边界上的陆地单元格以此为入口向四个方向遍历。
class Solution(object):def numEnclaves(self, grid)::type grid: List[List[int]]:rtype: intm len(grid)n len(grid[0])if m2 or n2:return 0q []for i in range(m):if grid[i][0]1:q.append([i,0])if grid[i][n-1]1:q.append([i,n-1])for j in range(1,n-1):if grid[0][j] 1:q.append([0,j])if grid[m-1][j] 1:q.append([m-1,j])direction [[-1,0],[1,0],[0,1],[0,-1]]while q:cur q.pop(0)x,y curgrid[x][y] 0for di in direction:newx xdi[0]newy ydi[1]if newx0 or newy0 or newxm or newyn or grid[newx][newy]0:continuegrid[newx][newy] 0q.append([newx,newy])return sum([sum(grid[i]) for i in range(m)])
