盘锦微信网站建设,深圳十大室内设计工作室,广州建设企业网站公司,购物网站模板免费方法
1.深度搜索
2.广度搜索
3.回溯
4.数据收集叶子节点路径#xff1a;每个节点计数#xff1a;深度/次数
题型
岛屿问题主函数遍历所有数组元素#xff0c;找岛屿个数深度/广度搜索函数负责把岛屿跑满(visited[i]True)岛屿边界控制
图搜索深度/广度搜索
797. 所有可能… 方法
1.深度搜索
2.广度搜索
3.回溯
4.数据收集叶子节点路径每个节点计数深度/次数
题型
岛屿问题主函数遍历所有数组元素找岛屿个数深度/广度搜索函数负责把岛屿跑满(visited[i]True)岛屿边界控制
图搜索深度/广度搜索
797. 所有可能的路径
class Solution:def __init__(self):self.res []# self.path [0]def allPathsSourceTarget(self, graph: List[List[int]]) - List[List[int]]:path [0]# l set()self.tracebacking( graph, 0, path)return self.resdef tracebacking(self, graph, node, path):if(node len(graph)-1):self.res.append(path[:])# print(self.res)returnfor index, node in enumerate(graph[node]):path.append(node)self.tracebacking( graph, node, path)path.pop()
200. 岛屿数量
class Solution:def __init__(self):self.dir [[0,1],# right[1,0],#down[-1,0],#up[0,-1]]#leftdef numIslands(self, grid: List[List[str]]) - int:m len(grid) #hangn len(grid[0])#lieprint(m, n)visited [[False]*n for _ in range(m)]result 0for i in range(m):for j in range(n):# print( grid[i][j] 1))if visited[i][j] False and grid[i][j] 1:self.dfs(grid, visited, i, j)#self.bfs(grid, visited, i, j)result 1# print(visited)return resultdef dfs(self, grid, visited, x, y):if grid[x][y] 0 or visited[x][y] True:returnvisited[x][y] Truefor i in range(4):nextx x self.dir[i][0]nexty y self.dir[i][1]if nextx0 or nextxlen(grid) or nexty0 or nextylen(grid[0]):continueself.dfs(grid, visited, nextx, nexty)def bfs(self, grid, visited, x, y):q deque()q.append((x, y))visited[x][y] Truewhile q:x, y q.popleft()# print(x,y)for i in range(4):nextx x self.dir[i][0]nexty y self.dir[i][1]if nextx0 or nextxlen(grid) or nexty0 or nextylen(grid[0]) or visited[nextx][nexty] True or grid[nextx][nexty] 0:continuevisited[nextx][nexty] Trueq.append((nextx, nexty))
695. 岛屿的最大面积 对岛屿数量进行修改就可以了
区别在于最大面积计算递归次数(dfs)或者入栈次数bfs)
class Solution:def __init__(self):self.dir [[0,1],# right[1,0],#down[-1,0],#up[0,-1]]#leftself.maxsize 0self.count 0def maxAreaOfIsland(self, grid: List[List[int]]) - int:m len(grid) #hangn len(grid[0])#lie# print(m, n)visited [[False]*n for _ in range(m)]for i in range(m):for j in range(n):if visited[i][j] False and grid[i][j] 1:#bfs# self.maxsize max(self.maxsize, self.bfs(grid, visited, i, j))#dfsself.count 0self.dfs(grid, visited, i, j)self.maxsize max(self.maxsize, self.count)return self.maxsize# def bfs(self, grid, visited, x, y):# q deque()# q.append((x, y))# visited[x][y] True# maxtem 1# while q:# x, y q.popleft()# for i in range(4):# nextx x self.dir[i][0]# nexty y self.dir[i][1]# if nextx0 or nextxlen(grid) or nexty0 or nextylen(grid[0]) or visited[nextx][nexty] True or grid[nextx][nexty] 0:# continue# visited[nextx][nexty] True# maxtem 1# q.append((nextx, nexty))# return maxtemdef dfs(self, grid, visited, x, y):if grid[x][y] 0 or visited[x][y] True:return 0visited[x][y] Trueself.count 1for i in range(4):nextx x self.dir[i][0]nexty y self.dir[i][1]if nextx0 or nextxlen(grid) or nexty0 or nextylen(grid[0]):continueself.dfs(grid, visited, nextx, nexty)
