代码随想录算法训练营第五十八天|拓扑排序精讲 、dijkstra(朴素版)精讲
拓扑排序
117. 软件构建
from collections import deque, defaultdictdef topological_sort(n, edges):inDegree = [0] * n # inDegree 记录每个文件的入度umap = defaultdict(list) # 记录文件依赖关系# 构建图和入度表for s, t in edges:inDegree[t] += 1umap[s].append(t)# 初始化队列,加入所有入度为0的节点queue = deque([i for i in range(n) if inDegree[i] == 0])result = []while queue:cur = queue.popleft() # 当前选中的文件result.append(cur)for file in umap[cur]: # 获取该文件指向的文件inDegree[file] -= 1 # cur的指向的文件入度-1if inDegree[file] == 0:queue.append(file)if len(result) == n:print(" ".join(map(str, result)))else:print(-1)if __name__ == "__main__":n, m = map(int, input().split())edges = [tuple(map(int, input().split())) for _ in range(m)]topological_sort(n, edges)
dijkstra(朴素版)
def dijkstra(grid, start, end, n):min_dist = [float('inf')] * (n + 1)visited = [False] * (n + 1)parent = [-1] * (n + 1)min_dist[start] = 0for _ in range(1, n):min_val = float('inf')cur = 1for v in range(1, n + 1):if not visited[v] and min_dist[v] < min_val:min_val = min_dist[v]cur = vvisited[cur] = Truefor v in range(1, n + 1):if (not visited[v] andgrid[cur][v] != float('inf') andmin_dist[cur] + grid[cur][v] < min_dist[v]):min_dist[v] = min_dist[cur] + grid[cur][v]parent[v] = cur# 打印最短路径path = [end]while parent[path[-1]] != -1:path.append(parent[path[-1]])path.reverse()for i in range(len(path) - 1):print(f"{path[i]} -> {path[i + 1]}")def main():n, m = map(int, input().split())grid = [[float('inf')] * (n + 1) for _ in range(n + 1)]for _ in range(m):p1, p2, val = map(int, input().split())grid[p1][p2] = valstart = 1end = ndijkstra(grid, start, end, n)if __name__ == "__main__":main()
相关文章:
代码随想录算法训练营第五十八天|拓扑排序精讲 、dijkstra(朴素版)精讲
拓扑排序 117. 软件构建 from collections import deque, defaultdictdef topological_sort(n, edges):inDegree [0] * n # inDegree 记录每个文件的入度umap defaultdict(list) # 记录文件依赖关系# 构建图和入度表for s, t in edges:inDegree[t] 1umap[s].append(t)# 初…...
【ARM】ULINK Pro如何和SWD接口进行连接调试
【更多软件使用问题请点击亿道电子官方网站】 1、 文档目标 解决ULINK Pro和JTAR接口进行连接问题。 2、 问题场景 因为ULINK Pro本身自带的接口是Cortex-M ETM Interface 20-pin Connector。所以无法和JTAR接口直接进行连接。 图2-1 3、软硬件环境 1)、软件版…...
react框架安全设计
react框架安全设计 1、易受攻击的React版本 React库在过去有一些严重性很高的漏洞,因此最好保持稳定版中的最新版本。 2、数据绑定 使用默认的{}进行数据绑定,React会自动对值进行转义以防止XSS攻击。但注意这种保护只在渲染textContent时候有用,渲染 HTML attributes的…...
Kafka生产调优实践。Kafka消息安全性、消息丢失、消息积压、保证消息顺序性
文章目录 搭建Kafka监控平台合理规划Kafka部署环境合理优化Kafka集群配置优化Kafka客户端使用方式合理保证消息安全消费者防止消息重复消费 生产环境常见问题分析消息零丢失方案消息积压如何处理如何保证消息顺序 搭建Kafka监控平台 官网地址 下载efak-web-3.0.2-bin.tar.gz安…...
DDColor部署安装,在服务器Ubuntu22.04系统——点动科技
DDColor图片上色项目的部署安装,在服务器Ubuntu22.04系统——点动科技 一、ubuntu22.04基本环境配置1.1 更换清华Ubuntu镜像源1.2 更新包列表:2. 安装英伟达显卡驱动2.1 使用wget在命令行下载驱动包2.2 更新软件列表和安装必要软件、依赖2.2 卸载原有驱动…...
使用 SSL/TLS 加密保障 RocketMQ 的安全传输
引言 在现代分布式系统中,数据传输的安全性至关重要。Apache RocketMQ作为一款高性能、高吞吐量的消息中间件,在许多关键应用场景中被广泛使用。为了确保消息传输的安全性,SSL/TLS 加密提供了一种可靠的解决方案。本文将详细介绍如何在 Rock…...
uni-app开发
参考帖 uniapp官方文档 组件库 项目中肯定需要使用第三方组件库,因为现有的这些不够方便我们去使用 uview: 演示 | uView 2.0 - 全面兼容 nvue 的 uni-app 生态框架 - uni-app UI 框架 ThorUI: 介绍 | ThorUI文档 创建uni-app项目 有HBuilder…...
2024社招面经_存储DB广告架构方向
总结 第一次社招,主要是三四月份面的,offer的有高德、拼多多、腾讯、美团、快手、携程,后面面的比较累了,因为美团定级和涨幅都还行就去了美团,没再继续面别的。 因为时间比较久了,只在这里贴一下当时有记…...
android10 系统定制:增加应用锁功能
实现效果如下,上锁应用在桌面或最近任务打开弹出解锁界面,需要解锁成功才能打开应用。解锁界面可点击返回或Home键关闭,非上锁应用可直接打开。 基本思路:拦截系统应用启动,判断应用是否在锁住状态,弹出解锁Window。解锁完成后再正常启动应用。分为从桌面启动和最近任务…...
数据结构----队列
一、队列 1)队列定义 队列(Queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。 允许插入的端是队尾,允许删除的端是队头。队列是一个先进先出(FIFO)的线性表,相应 的也有顺序存储和链式存储两种方式。 2&#…...
【python】实现对文件夹中的图像连续重命名方法
import os import shutildef rename_images(input_folder):# 获取输入文件夹下的所有图片文件(假设都是.jpg格式)image_files [f for f in os.listdir(input_folder) if os.path.isfile(os.path.join(input_folder, f)) and f.endswith(".jpg"…...
【nginx 第一篇章】认识一下 NGINX 服务器
一、简介 Nginx (engine x) 是一个高性能的 HTTP 和反向代理服务器,也是一个 IMAP/POP3/SMTP 代理服务器。由俄罗斯程序员 Igor Sysoev 开发,并在2004年首次公开发布。Nginx 以其高并发处理能力、低内存消耗、稳定性、丰富的功能集、简单的配置以及低学…...
【物联网】(防水篇)哪些电子产品需要通过 IPX7 防水级别测试?
哪些电子产品需要通过 IPX7 防水级别测试? 举例一些可能需要通过 IPX7 防水级别测试的产品 - 电子产品:如智能手机、平板电脑、智能手表、运动手环等,以满足用户在不同场景下的使用需求,例如在潮湿环境或意外沾水时仍能正常工作。…...
高级java每日一道面试题-2024年8月09日-网络篇-什么是XSS攻击如何避免?
如果有遗漏,评论区告诉我进行补充 面试官: 什么是XSS攻击如何避免? 我回答: XSS(Cross-Site Scripting,跨站脚本攻击)是一种常见的Web应用程序安全漏洞,攻击者通过在网页中注入恶意脚本,当其他用户浏览这些网页时&…...
Linux时间管理:命令与脚本的完美结合
目录 前言 Linux时间管理命令 date命令 cron定时任务 at命令 sleep命令 脚本与时间命令的结合使用 备份脚本示例 设置cron任务 监控脚本执行时间 结论 致谢 前言 在Linux系统中,时间管理是一项基础而关键的任务。无论是安排周期性的备份、监控任务的执…...
基于ssm+vue+uniapp的微信外卖小程序
开发语言:Java框架:ssmuniappJDK版本:JDK1.8服务器:tomcat7数据库:mysql 5.7(一定要5.7版本)数据库工具:Navicat11开发软件:eclipse/myeclipse/ideaMaven包:M…...
lvs(linux virtual server)实例
一.lvs概述 1.1什么是lvs LVS(Linux Virtual Server)是一个基于Linux操作系统的虚拟服务器技术,用于实现负载均衡和高可用性。LVS通过将客户端的请求分发到多台后端服务器上,从而提高整体服务的处理能力和可靠性。LVS主要有两个组…...
Unity游戏开发
Unity游戏开发 系列文章的目录: 第一章:Hello,Unity! “好读书,不求甚解;每有会意,便欣然忘食。” 本文目录: Unity游戏开发 Unity游戏开发前言今天我们来体验一下unity开发创建第一…...
5. MQTT消息类型详解(三)
9 SUBACK消息 9.1 消息结构 SUBACK消息是订阅确认消息,格式如下: ------------------------------- | 消息类型(1字节) | ------------------------------- | 保留标志(1字节) …...
TypeScript JSX
介绍 在线的免费的代码转换器工具:可以把HTML 代码移植到 JSX 语法。还支持很多其他的转换。 JSX 是 ECMAScript 的一种类似 XML 的语法扩展,没有任何定义的语义。它不打算由引擎或浏览器实现。它并不是将 JSX 纳入 ECMAScript 规范本身的提议。它旨在供…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
C++:多态机制详解
目录 一. 多态的概念 1.静态多态(编译时多态) 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1).协变 2).析构函数的重写 5.override 和 final关键字 1&#…...
接口自动化测试:HttpRunner基础
相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具,支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议,涵盖接口测试、性能测试、数字体验监测等测试类型…...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
提升移动端网页调试效率:WebDebugX 与常见工具组合实践
在日常移动端开发中,网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时,开发者迫切需要一套高效、可靠且跨平台的调试方案。过去,我们或多或少使用过 Chrome DevTools、Remote Debug…...
