thinkphp建站网址,东莞东城租房,成都有哪些设计公司,为什么要建设企业网站心路历程#xff1a;
在没有看图论这一章之前看这道题没什么直接的思路#xff0c;在看完图论之后#xff0c;学着使用DFS和BFS去套用解决。第一次自己做的时候还是遇到了很多小问题。整体思路很流畅#xff0c;但是需要处理的细节第一次没怎么处理好#xff0c;花了很多…
心路历程
在没有看图论这一章之前看这道题没什么直接的思路在看完图论之后学着使用DFS和BFS去套用解决。第一次自己做的时候还是遇到了很多小问题。整体思路很流畅但是需要处理的细节第一次没怎么处理好花了很多时间去思考图中的回溯和常规组合/子集回溯问题的区别。 这道题的一个整体思路还是对grid进行遍历然后标记所有连成一片陆地的点下次直接跳过。
注意的点
1、这道题很难用visited[]然后append的方式去记录访问过的点只能用visited[i][j]True这种方式否则会超时。 2、用DFS时虽然用的还是回溯的模板但是由于目的是记录访问过的所有点而不是路径区域问题而非路径问题所以不需要恢复现场。 3、用BFS时如果在出队时记录visited会超时需要在入队的时候记录visited才行。因为在BFS中队列的长度可能会很长而且很容易把重复的结点入队。用DFS时把visited的赋值放在candidate的选择那也会加快程序的运行这样就不用在下次收集candicate的时候收集重复的结点了。可以总结为在visited岛屿问题中在用到not allvisited[newx][newy]后立刻赋值True。 4、图中的四向问题用dxy [(0,1), (0,-1), (1,0), (-1,0)]的形式会更清晰简洁。 5、无论是DFS还是BFS本质在每次处理的都是以i, j为索引的’结点‘。 6、图中的DFS和回溯的唯一区别就是对于visited的维护模式不同回溯需要pop图的深搜只要遍历过就下次无论如何也不用考虑了毕竟搜索的是区域而不是路径。遍历过的多叉树的路径就保存下来
解法一DFS遍历grid
class Solution:def numIslands(self, grid: List[List[str]]) - int:# DFS 循环遍历回溯求区域而不是路径因此不需要在回溯函数调用后恢复现场m, n len(grid), len(grid[0])dxy [(0,1), (0,-1), (1,0), (-1,0)]def dfs(i,j): # 对i,j区域进行搜索将联通i,j的陆地全部记录起来。# 获取可选集合candicate []for dx, dy in dxy:newx, newy idx, jdyif 0 newx m-1 and 0 newy n-1 and grid[newx][newy] 1 and not allvisited[newx][newy]:candicate.append([newx, newy])allvisited[newx][newy] True # 在用到not allvisited[newx][newy]后立刻赋值if not candicate:returnfor each in candicate:dfs(each[0], each[1])# visited.pop() # 不用恢复了因为不是要求路径的总和而是记录遍历过的路径路径就是一个gridallvisited [[False]*n for _ in range(m)] # 用allvisited visited的那种做法会超时num 0for xi in range(m):for yi in range(n):if not allvisited[xi][yi] and grid[xi][yi] 1:dfs(xi,yi)num 1return num解法二BFS遍历grid
class Solution:def numIslands(self, grid: List[List[str]]) - int:# BFS 没有必要找到每个岛屿的陆地区域只需要将遍历过的标记上即可基本图和回溯的任何问题都得记录visited至少要考虑上一步重复from collections import dequem, n len(grid), len(grid[0])dxy [(0,1), (0,-1), (1,0), (-1,0)]visited [[False]*n for _ in range(m)]num 0quelen []for i in range(m):for j in range(n):# 对每个i,j做bfs并标记上搜索过的区域if grid[i][j] 1 and not visited[i][j]: # 1 和 1num 1que deque([[i,j]])visited[i][j] Truewhile que: # 不需要记录层数quelen.append(len(que))x, y que.popleft()# visited[x][y] True # 出队放会超时for dx, dy in dxy:newx, newy xdx, ydyif 0 newx m-1 and 0 newy n-1 and not visited[newx][newy] and grid[newx][newy] 1:que.append([newx, newy])visited[newx][newy] True # 只可以在进队的时候设置visited出队的时候会超时return num
