当前位置： 首页 > news >正文

青海网站制作哪家好,员工培训内容,asp网站源码安装教程,企业网站软件下载基础知识补充 1.图分为有向图和无向图#xff0c;有权图和无权图#xff1b; 2.图的表示方法#xff1a;邻接矩阵适合表示稠密图#xff0c;邻接表适合表示稀疏图#xff1b; 邻接矩阵#xff1a; 邻接表#xff1a; 基础操作补充 1.邻接矩阵#xff1a; class GraphAd…基础知识补充 1.图分为有向图和无向图有权图和无权图 2.图的表示方法邻接矩阵适合表示稠密图邻接表适合表示稀疏图    邻接矩阵    邻接表 基础操作补充 1.邻接矩阵 class GraphAdjacencyMatrix:def init(self, num_vertices):self.num_vertices num_verticesself.matrix [[0] * num_vertices for _ in range(num_vertices)]def add_edge(self, start, end): # 无向图self.matrix[start][end] 1self.matrix[end][start] 1 2.邻接表 from collections import defaultdictclass GraphAdjacencyList:def init(self):self.graph defaultdict(list)def add_edge(self, start, end): # 无向图self.graph[start].append(end)self.graph[end].append(start) 3.图的遍历 # 深度优先搜索(DFS):

从上到下递归或栈实现

def dfs(graph, start, visitedNone):if visited is None:visited set()visited.add(start)print(start, end )for neighbor in graph[start]:if neighbor not in visited:dfs(graph, neighbor, visited)# 广度优先搜索(BFS):

从左到右队列实现

from collections import dequedef bfs(graph, start):visited set()queue deque([start])visited.add(start)while queue:current queue.popleft()print(current, end )for neighbor in graph[current]:if neighbor not in visited:queue.append(neighbor)visited.add(neighbor) 题目 200 岛屿数量 给你一个由 1陆地和 0水组成的的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外你可以假设该网格的四条边均被水包围。 方法一深度优先搜索 DFS 若当前点是岛屿时向上下左右四个点做深度搜索终止条件越界当前是水 class Solution(object):def numIslands(self, grid)::type grid: List[List[str]]:rtype: intdef dfs(nums, x, y):if x0 or xlen(nums)-1: return if y0 or ylen(nums[0])-1: return if nums[x][y] 0:return else:nums[x][y] 0 # 必须先置0否则会在两个1间连续递归至超过栈长dfs(nums, x-1, y)dfs(nums, x1, y)dfs(nums, x, y-1)dfs(nums, x, y1)cnt 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] 1:dfs(grid, i, j)cnt 1return cnt 方法二广度优先搜索 BFS 若当前点是岛屿时将其上下左右四个点都加入队列终止条件越界当前是水 class Solution(object):def numIslands(self, grid)::type grid: List[List[str]]:rtype: intdef bfs(nums, x, y):queue [(x, y)]while queue:(x, y) queue.pop(0)if x0 or xlen(nums)-1: continue elif y0 or ylen(nums[0])-1: continue elif nums[x][y] 0:continue else:nums[x][y] 0 # 必须先置0否则会在两个1间连续递归至超过栈长queue.append((x-1, y))queue.append((x1, y))queue.append((x, y-1))queue.append((x, y1))cnt 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] 1:bfs(grid, i, j)cnt 1return cnt 994 腐烂的橘子 在给定的 m x n 网格 grid 中每个单元格可以有以下三个值之一 值 0 代表空单元格值 1 代表新鲜橘子值 2 代表腐烂的橘子。 每分钟腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能返回 -1 。 第一次遍历将所有新鲜橘子腐烂统计腐烂次数第二次遍历统计是否还有剩余的新鲜橘子(若初始就不含有新鲜橘子呢) 一次遍历统计新鲜橘子数量的同时记录腐烂橘子的位置队列 遍历队列若当前位置是腐烂橘子则将其上下左右四个点入队若当前位置是新鲜橘子则将新鲜橘子数量-1再将其上下左右四个点入队需要将处理过的位置的值置为0代表不再处理 class Solution(object):def orangesRotting(self, grid)::type grid: List[List[int]]:rtype: intcnt, queue 0, []m, n len(grid), len(grid[0])for i in range(m):for j in range(n):if grid[i][j] 1:cnt 1elif grid[i][j] 2:queue.append([i,j])if cnt 0: return 0time, stack -1, []while queue:[x, y] queue.pop(0)if -1xm and -1yn and grid[x][y]:if grid[x][y] 1: cnt - 1grid[x][y] 0 # 不再处理这个点stack.append([x-1, y])stack.append([x1, y])stack.append([x, y-1])stack.append([x, y1])if not queue and stack:queue stacktime 1 stack []return -1 if cnt else time 计算遍历深度用BFS 207 课程表 你这个学期必须选修 numCourses 门课程记为 0 到 numCourses - 1 。在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出其中 prerequisites[i] [ai, bi] 表示如果要学习课程 ai 则 必须 先学习课程  bi 。 例如先修课程对 [0, 1] 表示想要学习课程 0 你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习如果可以返回 true 否则返回 false 。 方法一广度优先搜索 from collections import deque from collections import defaultdictclass Solution(object):def canFinish(self, numCourses, prerequisites)::type numCourses: int:type prerequisites: List[List[int]]:rtype: booldegree [0]numCourses maps defaultdict(list) queue deque()for cur, pre in prerequisites:degree[cur] 1 # 统计每门课的先修课程数maps[pre].append(cur) # 记录基础课和对应的进阶课for i in range(numCourses):if degree[i] 0: queue.append(i) # 无先修课程基础课时入队count 0while queue:course queue.popleft()count 1for i in maps[course]: # 将以course为基础课的进阶课的先修课数-1degree[i] - 1if degree[i] 0: # 已修完全部基础课queue.append(i) return count numCourses 方法二深度优先搜索 class Solution(object):def canFinish(self, numCourses, prerequisites)::type numCourses: int:type prerequisites: List[List[int]]:rtype: booldegree [0] numCoursesmaps defaultdict(list)def dfs(i):if degree[i]-1: return False # degree[i]-1 表示会陷入循环if degree[i]1: return True # degree[i]1 表示能完成课 degree[i]-1 # 防止 1-0-1 转回来的情况for pre in maps[i]: # 遍历每门基础课if not dfs(pre): return Falsedegree[i]1 # 该门课可以完成return Truefor cur, pre in prerequisites: # 记录先修课和其基础课程maps[cur].append(pre)for i in range(numCourses): # 遍历每门课dfs(i)return sum(degree) numCourses # 若每门课都完成应该全为1 208 实现Trie(前缀树) Trie发音类似 try或者说 前缀树 是一种树形数据结构用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景例如自动补完和拼写检查。 请你实现 Trie 类 Trie() 初始化前缀树对象。void insert(String word) 向前缀树中插入字符串 word 。boolean search(String word) 如果字符串 word 在前缀树中返回 true即在检索之前已经插入否则返回 false 。boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix 返回 true 否则返回 false 。 核心使用「边」来代表有无字符使用「点」来记录是否为「单词结尾」以及「其后续字符串的字符是什么」 class TrieNode:def init(self):self.children {}self.is_end Falseclass Trie(object):def init(self):self.root TrieNode()def insert(self, word)::type word: str:rtype: Nonenode self.rootfor c in word:if c not in node.children:node.children[c] TrieNode()node node.children[c]node.is_end Truedef searchPrefix(self, word):node self.rootfor c in word:if c not in node.children: return Nonenode node.children[c]return nodedef search(self, word)::type word: str:rtype: boolnode self.searchPrefix(word)return node is not None and node.is_enddef startsWith(self, prefix)::type prefix: str:rtype: boolnode self.searchPrefix(prefix)return node is not None 额外补充 flood fill 带你学习Flood Fill算法与最短路模型 - 时间最考验人 - 博客园 (cnblogs.com)