如何管理公司网站后台,北京公司注册查询,2022最新时事新闻及点评,建筑装饰网站模板文章目录 题目743.网络延迟时间3341.到达最后一个房间的最少时间I 求解最短路径的问题#xff0c;分为使用BFS和使用迪斯科特拉算法#xff0c;这两种算法求解的范围是有区别的 BFS适合求解#xff0c;边的权值都是1的图中的最短路径的问题 图论 之 BFS迪斯科特拉算法适合求… 文章目录 题目743.网络延迟时间3341.到达最后一个房间的最少时间I 求解最短路径的问题分为使用BFS和使用迪斯科特拉算法这两种算法求解的范围是有区别的 BFS适合求解边的权值都是1的图中的最短路径的问题 图论 之 BFS迪斯科特拉算法适合求解边的权值不一样的图其中该算法有两种实现方式分别适用于两种情况的图 稠密图使用朴素的Dijkstra算法其中稠密图的定义是边的数量级与 o ( n 2 ) o(n^2) o(n2)相当的图朴素的Dijkstra算法的时间复杂度是 o ( n 2 ) o(n^2) o(n2),其中n是图的节点的数量稀疏图使用堆优化的Dijkstra算法算法的时间复杂度是 o ( m l o g m ) o(mlogm) o(mlogm)其中m是边的数量如果输入的稠密图那么使用堆优化的Dijkstra算法的时间复杂度是 o ( n 2 l o g n ) o(n^2logn) o(n2logn) 朴素的Dijkstras算法的模版 # 存储边的情况
edge [[float(inf)]*n for n in range(n)]
# dis[i]表示 单源点k到其余节点i的最短的路径
dis [float(inf)]*n
dis[k] 0
# 这个done[k] True不用设置后面会依据这个把起点弹出
done [False]*n # done[i]标记是否找到 到达节点i的最短的路径while True:x -1for i,ok in enumerate(done):# 找到在还没确定最小距离的节点该节点到源点的距离最小if not ok and (x 0 or dis[i] dis[x]):x i# 判断是否都找到了if x 0:# 这里就已经求解完成了后续你可以返回最大值return dis# 有节点无法到达if dis[x] float(inf):return -1# 设置标志位表示节点x的最小距离已经确定done[x] True# 遍历当前节点的所有的邻居更新答案for j,d in enumerate(edge[x]):dis[j] min(dis[j],dis[j]d) 使用堆优化的Dijkstra算法 import heapqclass Solution:def networkDelayTime(self, times: List[List[int]], n: int, k: int) - int:# 使用堆优化的Dijkstra算法# 使用堆优化的话适用于稀疏图所以边的记录我们使用邻接表edge [[] for _ in range(n)]for x,y,z in times:edge[x-1].append((y-1,z))dis [float(inf)]*n dis[k-1] 0# 入堆的元素是 (dis[x],x)第一个元素是距离这也是设置的优先级h [(0,k-1)]while h:# 出堆dx,x heapq.heappop(h)# 如果当前的距离大于最小距离直接过if dx dis[x]:# 说明之前出过堆continue# 访问邻居不一定是这个邻接表或者邻接矩阵二维表也可以for y,d in edge[x]:# 计算更新值计算方式按照题目的意思new_dis dx d # 只有更优的值才能被加入进去if new_dis dis[y]:dis[y] new_disheapq.heappush(h,(new_dis,y))mx max(dis)return mx if mx float(inf) else -1
题目
743.网络延迟时间
743.网络延迟时间 思路分析由于边的数量远远大于节点的数量所以我们还是考虑使用稠密图下的朴素的Dijkstra算法最后返回不是无穷的最大的路径即可 class Solution:def networkDelayTime(self, times: List[List[int]], n: int, k: int) - int:# 区别于BFS求解的最短距离这个距离的边的权值不一样# 使用朴素的迪斯科特拉算法# 邻接矩阵记录边的情况edge [[float(inf)]*(n) for _ in range(n)]# 有向边for e in times:edge[e[0]-1][e[1]-1] e[2]dis [float(inf)]*n # 记录k到各个节点的最短距离ans dis[k-1] 0done [False] * n # 记录节点的最短距离是否被确定while True:x -1# 找到最短距离还没确定并且节点k到它的距离是最短的节点for i,ok in enumerate(done):if not ok and (x0 or dis[i] dis[x]):x i # 如果x0,表示全部的节点已经全部都访问过了if x 0 :return ans# 如果最短的节点的距离是无穷说明不可达if dis[x] float(inf):return -1# 更新ans dis[x]done[x] Truefor y,d in enumerate(edge[x]):dis[y] min(dis[y],dis[x]d) 使用堆优化的解法 import heapqclass Solution:def networkDelayTime(self, times: List[List[int]], n: int, k: int) - int:# 使用堆优化的Dijkstra算法# 使用堆优化的话适用于稀疏图所以边的记录我们使用邻接表edge [[] for _ in range(n)]for x,y,z in times:edge[x-1].append((y-1,z))dis [float(inf)]*n dis[k-1] 0# 入堆的元素是 (dis[x],x)h [(0,k-1)]while h:dx,x heapq.heappop(h)if dx dis[x]:# 说明之前出过堆continuefor y,d in edge[x]:new_dis dx d if new_dis dis[y]:dis[y] new_disheapq.heappush(h,(new_dis,y))mx max(dis)return mx if mx float(inf) else -1
3341.到达最后一个房间的最少时间I
3341.到达最后一个房间的最少时间I 思路分析开始的时候我错误的以为题目中只能向右或者向下运动 所以写了一个动态规划进行求解实际上这个思路是错误的,不过要是只能向下或者向右运动的话动态规划也是一种很好的做法 # 动态规划的做法竟然可以过700个测试用例
import heapq
class Solution:def minTimeToReach(self, moveTime: List[List[int]]) - int:# 开始的时候从(0,0)出发移动到相邻的房间其实也只是向下或向右运动# 感觉可以用动态规划dp[i][j]表示到达i,j所需的最少的时间# 递推公式# dp[i][j] min(max(dp[i-1][j],moveTime[i][j])1,max(dp[i][j-1],moveTime[i][j])1)n len(moveTime)m len(moveTime[0])dp [[float(inf)]*(m1) for _ in range(n1)]dp[1][1] 0for i in range(n):for j in range(m):if i 0 and j 0:continuedp[i1][j1] min(max(dp[i][j1],moveTime[i][j])1,max(dp[i1][j],moveTime[i][j])1)for i in dp:print(i )return dp[n][m] 正确的思路应该是使用Dijkstra算法不过开始的时候我有点纠结这个edge也就是边的矩阵如何转化为邻接矩阵或者邻接表后面一想还是我的固定思维阻碍了我邻接矩阵和邻接表只是一个工具帮助我们找到当前的节点的邻居但是在现在的图中你通过坐标的加减不就可以得到对应的邻居嘛 展示使用朴素Dijkstra算法做法
import heapq
class Solution:def minTimeToReach(self, moveTime: List[List[int]]) - int:# 首先先使用 堆优化的Dijkstra进行解题# 图已经构建就是moveTime# dis[i][j]表示(0,0)到(i,j)的最短的时间n,m len(moveTime),len(moveTime[0])dis [[float(inf)]*m for _ in range(n)]dis[0][0] 0done [[False]*m for _ in range(n)]while True:x,y -1,-1# 开始遍历还没确定的点for i in range(n):for j in range(m):if not done[i][j] and ((x0 and y 0) or dis[i][j] dis[x][y]):x,y i,jif x0 and y 0:# 说明都找到了return dis[n-1][m-1]# 设置已经找到done[x][y] True# 访问邻居for i,j in (x1,y),(x-1,y),(x,y1),(x,y-1):if 0 i n and 0 j m:dis[i][j] min(max(dis[x][y],moveTime[i][j]) 1,dis[i][j])
展示使用堆优化的Dijkstra算法
import heapq
class Solution:def minTimeToReach(self, moveTime: List[List[int]]) - int:# 首先先使用 堆优化的Dijkstra进行解题# 图已经构建就是moveTime# dis[i][j]表示(0,0)到(i,j)的最短的时间n,m len(moveTime),len(moveTime[0])dis [[float(inf)]*m for _ in range(n)]dis[0][0] 0h [(0,0,0)]while True:d,x,y heapq.heappop(h)if x n-1 and y m-1:return d # 已经更新过了if d dis[x][y]:continue# 访问邻居for i,j in (x1,y),(x-1,y),(x,y1),(x,y-1):if 0 i n and 0 j m:# 合法的坐标# 计算当前的距离小于才入堆new_dis max(d,moveTime[i][j])1if dis[i][j]new_dis:dis[i][j] new_disheapq.heappush(h,(dis[i][j],i,j)) 文章转载自： http://www.morning.ns3nt8.cn.gov.cn.ns3nt8.cn http://www.morning.ktyww.cn.gov.cn.ktyww.cn http://www.morning.lfqnk.cn.gov.cn.lfqnk.cn http://www.morning.mjkqj.cn.gov.cn.mjkqj.cn http://www.morning.ftlgy.cn.gov.cn.ftlgy.cn http://www.morning.nzqmw.cn.gov.cn.nzqmw.cn http://www.morning.itvsee.com.gov.cn.itvsee.com http://www.morning.whnps.cn.gov.cn.whnps.cn http://www.morning.mzskr.cn.gov.cn.mzskr.cn http://www.morning.wrlqr.cn.gov.cn.wrlqr.cn http://www.morning.pqppj.cn.gov.cn.pqppj.cn http://www.morning.ddxjr.cn.gov.cn.ddxjr.cn http://www.morning.jqswf.cn.gov.cn.jqswf.cn http://www.morning.wnwjf.cn.gov.cn.wnwjf.cn http://www.morning.tgnr.cn.gov.cn.tgnr.cn http://www.morning.cwcdr.cn.gov.cn.cwcdr.cn http://www.morning.snktp.cn.gov.cn.snktp.cn http://www.morning.lbzgt.cn.gov.cn.lbzgt.cn http://www.morning.rtspr.cn.gov.cn.rtspr.cn http://www.morning.fpkpz.cn.gov.cn.fpkpz.cn http://www.morning.wrkcw.cn.gov.cn.wrkcw.cn http://www.morning.pmftz.cn.gov.cn.pmftz.cn http://www.morning.dwtdn.cn.gov.cn.dwtdn.cn http://www.morning.xyyplp.cn.gov.cn.xyyplp.cn http://www.morning.sdkaiyu.com.gov.cn.sdkaiyu.com http://www.morning.ntnml.cn.gov.cn.ntnml.cn http://www.morning.zlchy.cn.gov.cn.zlchy.cn http://www.morning.fmrwl.cn.gov.cn.fmrwl.cn http://www.morning.zhengdaotang.cn.gov.cn.zhengdaotang.cn http://www.morning.mwns.cn.gov.cn.mwns.cn http://www.morning.ffptd.cn.gov.cn.ffptd.cn http://www.morning.tfpbm.cn.gov.cn.tfpbm.cn http://www.morning.juju8.cn.gov.cn.juju8.cn http://www.morning.nfbkz.cn.gov.cn.nfbkz.cn http://www.morning.rwjh.cn.gov.cn.rwjh.cn http://www.morning.cszbj.cn.gov.cn.cszbj.cn http://www.morning.tbplf.cn.gov.cn.tbplf.cn http://www.morning.bfhfb.cn.gov.cn.bfhfb.cn http://www.morning.ggxbyhk.cn.gov.cn.ggxbyhk.cn http://www.morning.fcqlt.cn.gov.cn.fcqlt.cn http://www.morning.rpms.cn.gov.cn.rpms.cn http://www.morning.rddlz.cn.gov.cn.rddlz.cn http://www.morning.ssglh.cn.gov.cn.ssglh.cn http://www.morning.mwqbp.cn.gov.cn.mwqbp.cn http://www.morning.lflsq.cn.gov.cn.lflsq.cn http://www.morning.wdhzk.cn.gov.cn.wdhzk.cn http://www.morning.4q9h.cn.gov.cn.4q9h.cn http://www.morning.qwlml.cn.gov.cn.qwlml.cn http://www.morning.fgxws.cn.gov.cn.fgxws.cn http://www.morning.pxbrg.cn.gov.cn.pxbrg.cn http://www.morning.ryfpx.cn.gov.cn.ryfpx.cn http://www.morning.807yy.cn.gov.cn.807yy.cn http://www.morning.stfdh.cn.gov.cn.stfdh.cn http://www.morning.tmlhh.cn.gov.cn.tmlhh.cn http://www.morning.ywpwg.cn.gov.cn.ywpwg.cn http://www.morning.pdmsj.cn.gov.cn.pdmsj.cn http://www.morning.ldcrh.cn.gov.cn.ldcrh.cn http://www.morning.zbhfs.cn.gov.cn.zbhfs.cn http://www.morning.kfwrq.cn.gov.cn.kfwrq.cn http://www.morning.ppghc.cn.gov.cn.ppghc.cn http://www.morning.nqdkx.cn.gov.cn.nqdkx.cn http://www.morning.mnjwj.cn.gov.cn.mnjwj.cn http://www.morning.clkjn.cn.gov.cn.clkjn.cn http://www.morning.qzqjz.cn.gov.cn.qzqjz.cn http://www.morning.nxkyr.cn.gov.cn.nxkyr.cn http://www.morning.cytr.cn.gov.cn.cytr.cn http://www.morning.lmctj.cn.gov.cn.lmctj.cn http://www.morning.fykqh.cn.gov.cn.fykqh.cn http://www.morning.llyjx.cn.gov.cn.llyjx.cn http://www.morning.kbdjn.cn.gov.cn.kbdjn.cn http://www.morning.abgy8.com.gov.cn.abgy8.com http://www.morning.sxhdzyw.com.gov.cn.sxhdzyw.com http://www.morning.qxbsq.cn.gov.cn.qxbsq.cn http://www.morning.lzwfg.cn.gov.cn.lzwfg.cn http://www.morning.fmrd.cn.gov.cn.fmrd.cn http://www.morning.kongpie.com.gov.cn.kongpie.com http://www.morning.wqcbr.cn.gov.cn.wqcbr.cn http://www.morning.ghfrb.cn.gov.cn.ghfrb.cn http://www.morning.nlkm.cn.gov.cn.nlkm.cn http://www.morning.hchrb.cn.gov.cn.hchrb.cn
