本机号码一键登录,网站seo计划,太古楼角原网站建设,广州建网站的公司 白云区Leetcode 200. 岛屿数量
深度优先搜索法#xff1a;
对于这道题来说#xff0c;是一个非常经典的图的问题#xff0c;我们可以先从宏观上面来看问题#xff0c;也就是说在不想具体算法的前提下#xff0c;简单的说出如何找到所有的岛屿呢#xff1f; 如图中所示#x…Leetcode 200. 岛屿数量
深度优先搜索法
对于这道题来说是一个非常经典的图的问题我们可以先从宏观上面来看问题也就是说在不想具体算法的前提下简单的说出如何找到所有的岛屿呢 如图中所示首先非常显而易见的要素就是我们一定要遍历图中的每一个坐标这是肯定的然后呢对于岛屿的数量一开始想的肯定就是每当我们访问了一个1的坐标时我们就找到了一个岛屿可是因为我们要遍历整个图所以肯定不能每次遇到一个1就对岛屿的数量进行增加因为题目说了横纵连接着的坐标都是1的话都属于同一个岛屿就像上图一样证明我们只有三个岛屿
那么我们是不是可以像一个办法当我们找到了一个岛屿的坐标后把属于这个坐标的岛屿的其他所有值为1的坐标都记录下来这样以来意思就是说在我们继续遍历的时候我们检查每一个坐标时如果发现这个坐标已经被标记过了证明他并不是一个新的岛屿而是一个之前就发现过的岛屿的一部分那么就可以了
如何去实现这个标记的方法呢就可以用到我们的深度优先搜索从新发现的坐标开始一直找直到找到了岛屿的边缘或者整个图的边缘之后返回这样就能找到所有属于相同岛屿的坐标那么我们可以把主代码写出来了已经
class Solution:def numIslands(self, grid: List[List[str]]) - int:res 0# iterate to check every box in the grid to see# if it is a start for a new lslandfor r in range(len(grid)):for c in range(len(grid[0])):# if so, run a dfs to mark all its fellow# box and add the 1 to the resultif grid[r][c] 1:dfs(grid, r, c)res res 1return res
主体部分的代码非常简单然后呢我们需要做的就是对于dfs的编写正如在这个主体代码中写的你会发现我这里还是用的如果box中存的元素是1那就最终要增加岛屿数量这难道不是错的吗其实这里就隐喻了我们是如何完成对一个岛屿上所有的box进行标记的与其新建一个空间例如集合然后把dfs中搜索到的box全都加入进去然后每一次循环遍历的时候去看当前的box是否在那个集合中更好的方法其实就是直接原地更改我们的grid将搜索到的box中的值从1修改到2这样这个主体函数中的if 语句就不会被execute了
class Solution:def numIslands(self, grid: List[List[str]]) - int:def dfs(grid, r, c):# base case, do nothing when we# reached the edge of entire grid or found waterif not (0 r len(grid) and 0 c len(grid[0])) or grid[r][c] ! 1:return# mark the visited box as 2grid[r][c] 2# call the recursive case on each direction from current boxdfs(grid, r - 1, c)dfs(grid, r 1, c)dfs(grid, r, c - 1)dfs(grid, r, c 1)res 0# iterate to check every box in the grid to see# if it is a start for a new lslandfor r in range(len(grid)):for c in range(len(grid[0])):# if so, run a dfs to mark all its fellow# box and add the 1 to the resultif grid[r][c] 1:dfs(grid, r, c)res res 1return res
这样你就有了整个的代码其实这种类型的深度优先搜索可以参考我们在二叉树的时候是怎么做的无非也是一直遍历然后直到我们reach 到了leaf node然后发现新的node是空的时候就直接return这里不过是多加了两个方向在二叉树里的recursive case是对左右子节点继续call这里是对上下左右四个横纵坐标的方向继续call然后呢条件多加了一个这里对应的不能超出边界就是二叉树中的if not root, 只是这里还要保证grid[r][c] 1不是1的话就不是我们要找的同一个岛屿上的点 时间复杂度 O(m*n)m和n就是grid的长和宽因为我们要遍历每一个坐标 空间复杂度 O(m*n)在最坏的情况下如果左上角的box就是陆地1并且整张图都是1 那么我们就要把每一个box都有一个recursive function这样在就会用 到一个大小为m*n的栈 Leetcode 994. 腐烂的橘子
广度优先搜索法
这道题的关键在于我们在一开始所给的grid里面存在多个橘子的可能我们需要在把能弄腐烂的橘子全部弄完之后就返回结果所以每一分钟里我们需要对所有当前的橘子进行扩散这里运用深度优先的递归就很麻烦因为我们每一次逻辑要处理多个搜索
这里我们就使用广度优先利用队列来对腐烂橘子进行保存并且通过出队来进行遍历然后扩散后把新的腐烂的橘子继续加入队列
这样以来每一次我们通过向四个方向的检查中发现新的好橘子之后就可以立马对其进行操作具体分三步第一步将其加入我们的队列代表下一轮遍历的时候他会pop出来作为新的坐标然后向四周扩散第二步将我们的好橘子的count做一个递减第三步将grid中其坐标位置的值从1变成2避免后序的遍历中反复visit这个坏橘子
class Solution:def orangesRotting(self, grid: List[List[int]]) - int:# we are using a queue to do the bfsq deque()fresh_count 0res 0# loop through the gird first to find # the amount of fresh and add the rotten to# the queuefor i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] 1:fresh_count fresh_count 1elif grid[i][j] 2:q.append((i, j))# loop until we have no more rotten orangewhile q and fresh_count 0:# every time we start pop out q again, we did another searchres res 1# for each rotten orango, pop them outfor _ in range(len(q)):box q.popleft()r, c box[0], box[1]# check topif r - 1 0 and grid[r - 1][c] 1:fresh_count fresh_count - 1q.append((r - 1, c))grid[r - 1][c] 2# check rightif c 1 len(grid[0]) and grid[r][c 1] 1:fresh_count fresh_count - 1q.append((r, c 1))grid[r][c 1] 2# check botif r 1 len(grid) and grid[r 1][c] 1:fresh_count fresh_count - 1q.append((r 1, c)) grid[r 1][c] 2# check leftif c - 1 0 and grid[r][c - 1] 1:fresh_count fresh_count - 1q.append((r, c - 1))grid[r][c - 1] 2# we did not get them all rottonif fresh_count 0:return -1else:return res 时间复杂度 O(m*n)m和n就是grid的长和宽因为我们要遍历每一个坐标 空间复杂度 O(m*n)在最坏的情况下一开始所有的橘子都是坏橘子我们使用的额外空间队列的长度最大就是m*n
