代码随想录算法训练营第六十一天 | floyd算法
Floyd 算法精讲
题目链接:97. 小明逛公园
文章讲解:代码随想录
思想:本题是多源最短路,即求多个起点到多个终点的多条最短路径。用Floyd 算法。
Floyd 算法对边的权值正负没有要求,都可以处理,Floyd算法核心思想是动态规划。
动规五部曲:
1、确定dp数组(dp table)以及下标的含义
grid[i][j][k] = m,表示 节点i 到 节点j 以[1...k] 集合中的一个节点为中间节点的最短距离为m。
2、确定递推公式
(1)节点i 到 节点j 的最短路径经过节点k
对于第一种情况,grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]
节点i 到 节点k 的最短距离是不经过节点k,中间节点集合为[1...k-1],所以表示为grid[i][k][k - 1]
节点k 到节点j 的最短距离也是不经过节点k,中间节点集合为[1...k-1],所以表示为 grid[k][j][k - 1]
(2)节点i 到 节点j 的最短路径不经过节点k
第二种情况,grid[i][j][k] = grid[i][j][k - 1]
如果节点i 到 节点j的最短距离不经过节点k,那么中间节点集合[1...k-1],表示为 grid[i][j][k - 1]
因为我们是求最短路,对于这两种情况自然是取最小值。
即: grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1], grid[i][j][k - 1])
3、dp数组如何初始化
把k 赋值为 0,本题节点0是无意义的,节点是从1 到 n,在下一轮计算的时候,就可以根据 grid[i][j][0] 来计算 grid[i][j][1],此时的 grid[i][j][1] 就是 节点i 经过节点1 到达 节点j 的最小距离了。
本题求的是最小值,所以输入数据没有涉及到的节点的情况都应该初始为一个最大数
4、确定遍历顺序
好比是一个三维坐标,i和j是平层,而k 是垂直向上的。遍历的顺序是从底向上一层一层去遍历。
所以遍历k 的for循环一定是在最外面,这样才能一层一层去遍历。
5、举例推导dp数组
相关文章:
代码随想录算法训练营第六十一天 | floyd算法
Floyd 算法精讲 题目链接:97. 小明逛公园 文章讲解:代码随想录 思想:本题是多源最短路,即求多个起点到多个终点的多条最短路径。用Floyd 算法。 Floyd 算法对边的权值正负没有要求,都可以处理,Floyd算法…...
[三分钟]web自动化测试(三):selenium自动化测试常用函数(下)
文章目录 4.等待4.1 强制等待4.2 隐式等待4.3 显式等待 5.浏览器导航5.1 浏览器的前进、后退、刷新5.2 打开网站 6. 弹窗6.1 确认和取消6.2 输入信息 7. 文件上传 4.等待 如果页面渲染的速度赶不上代码执行的速度,可能会因为渲染过慢出现自动化误报的问题。 此时可…...
文档声明:HTML文档的基石
在前端开发的世界里,文档声明虽是一个看似不起眼的细节,却在网页的解析和渲染过程中扮演着至关重要的角色。今天,就让我们深入探讨文档声明的奥秘,揭开它背后的原理和重要性。 一、文档声明的定义与作用 文档声明,顾…...
光学涡旋干涉仪
一、什么是涡旋干涉仪? 涡旋光束一般指电场含有螺旋相位因子exp(iℓθ)的光束,其中ℓ为拓扑荷数,θ为方位角,其波前为螺旋形,光束中心存在相位奇点,因此涡旋光束的光强轮廓是中心强度为零的圆环。早在1992…...
Wireshark快速入门--对启动的后端程序进行抓包
怎么对自己启动的后端程序进行抓包? 1. 安装并启动 Wireshark 你要先从 Wireshark 官网 下载对应系统的安装包,然后进行安装。安装完成后,启动该软件。 可以快速入门可以参考博文:从零开始学 Wireshark:网络分析入门…...
ViTa-Zero:零样本视觉触觉目标 6D 姿态估计
25年4月来自Amazon 公司、Brown 大学和 Northestern 大学的论文“ViTa-Zero: Zero-shot Visuotactile Object 6D Pose Estimation”。 目标 6D 姿态估计是机器人技术中的一项关键挑战,尤其对于操作任务而言。虽然先前结合视觉和触觉(视觉触觉࿰…...
继承(c++版 非常详细版)
一. 继承的概念及定义 1.1 继承的概念 继承(inheritance)机制是⾯向对象程序设计使代码可以复⽤的最重要的⼿段,它允许我们在保持原有 类特性的基础上进⾏扩展,增加⽅法(成员函数)和属性(成员变量),这样产⽣新的类,称派⽣类。继…...
解锁服务器迁移的未来:《2025 服务器迁移效率白皮书》(附下载)
一、背景🏙️ 随着全球数字化转型的不断加速,企业在推动 IT 基础设施现代化过程中,面临着前所未有的服务器迁移挑战。传统的迁移工具和多云、混合云环境带来的复杂性,导致迁移效率低、成本高、人力投入大,从而严重阻碍…...
STM32的Flash映射双重机制
在STM32微控制器中,存在一个重要的内存映射特性:Flash存储器可以同时出现在两个不同的地址区域,而且可以通过重映射功能改变CPU启动时从哪个地址获取初始指令。 STM32的Flash映射双重机制 当描述"通常起始于地址0x00000000,…...
简单了解跨域问题
什么是跨域? 跨域是浏览器基于同源策略的安全机制。 如何两个请求之间,域名,端口,协议三者中有任意一个不同,就会产生跨域问题。 跨域的解决方案 1. CORS(跨源资源共享) 后端通过设置响应头声…...
sql学习笔记(四)
今天看到一个sql题,“近30天,******”,这里需要用到一个函数,date_add,其作用是在指定日期基础上添加一个时间间隔。 语法(以mysql为例): DATE_ADD(date, INTERVAL value unit) d…...
基于 Java 的实现前端组装查询语句,后端直接执行查询方案,涵盖前端和后端的设计思路
1. 前端设计 前端负责根据用户输入或交互条件,动态生成查询参数,并通过 HTTP 请求发送到后端。 前端逻辑: 提供用户界面(如表单、筛选器等),让用户选择查询条件。将用户选择的条件组装成 JSON 格式的查询参数。发送 HTTP 请求(如 POST 或 GET)到后端。示例: 假设用…...
反射与注解实现动态功能扩展案例-插件系统
学海无涯,志当存远。燃心砺志,奋进不辍。 愿诸君得此鸡汤,如沐春风,事业有成。 若觉此言甚善,烦请赐赞一枚,共励学途,同铸辉煌! 开发一个需要高度扩展性的应用,比如Web框…...
auto(x) decay copy
该提案为auto又增加了两个新语法:auto(x) 和auto{x}。两个作用一样,只是写法不同,都 是为x 创建一份拷贝。 为什么需要这么个东西?看一个例子: void bar(const auto&);void foo(const auto& param) {auto co…...
基于STM32、HAL库的DS2411R安全验证及加密芯片驱动程序设计
一、简介: DS2411R是Maxim Integrated(现为Analog Devices)生产的一款1-Wire硅序列号芯片,具有以下特点: 64位唯一ROM序列号(包括8位家族码、48位序列号和8位CRC校验码) 工作电压范围:2.8V至5.25V 工作温度范围:-40C至+85C 采用TO-92或SOT-223封装 通过1-Wire协议通信…...
疫苗接种体系进入“全生命周期”时代:公共卫生治理再提速
疫苗接种体系进入“全生命周期”时代:公共卫生治理再提速 在防控重大传染病的国家公共卫生战略中,疫苗接种始终处于基础性、先导性地位。2025年4月25日是第39个全国儿童预防接种日,活动主题为“打疫苗、防疾病、保健康”。近年来,…...
zynq 7010 PS 串口打印
前言 之前写过一篇文章《zynq 7010 PL 点灯例程》,介绍的是 zynq PL 部分的使用,今天这篇文章则是介绍 zynq PS 部分的使用。 在此之前,先总结点题外话 PL 编程,核心思想是生成 bitstream 文件,加载到 FPGA 运行PS …...
【补题】ACPC Kickoff 2025 F. Kinan The Bank Robber
题意:给出长度为n的序列,接下来给出了两个包裹,你可以选择把数字放进这两个包裹当中,要求你放的的方式,最终会让包裹内的数字双双互质,请你给出你的放法,如果没有输出-1 思路: 1.包…...
局域网传文件——基于flask实现
项目地址 git clone gitgitee.com:xhdx/co_-shared_-doc_in_-local_-net.git 所需python包 flask2.2.3 markdown3.4.1 bleach5.0.1 通过局域网的方式实现文件夹共享,共享的文件会放在uploads这个文件夹下: 运行界面: 包括预览、删除、下载等…...
苍穹外卖10
WebSocket WebSocket是基于TCP的一种新的网络协议。它实现了浏览器与服务器全双工通信----浏览器和服务器只需要完成一次握手,两者之间就可以创建持久性的连接,并进行双向数据传输。 HTTP协议和WebSocket协议对比: HTTP是短链接 WebSocke…...
第一天 车联网定义、发展历程与生态体系
前言 车联网(Internet of Vehicles, IoV)作为物联网(IoT)在汽车领域的延伸,正在彻底改变人们的出行方式。无论是自动驾驶、远程诊断,还是实时交通优化,车联网技术都扮演着核心角色。本文将从零…...
大模型(LLMs)强化学习—— PPO
一、大语言模型RLHF中的PPO主要分哪些步骤? 二、举例描述一下 大语言模型的RLHF? 三、大语言模型RLHF 采样篇 什么是 PPO 中 采样过程?介绍一下 PPO 中 采样策略?PPO 中 采样策略中,如何评估“收益”? …...
麻衣相法【麻衣相士】开篇
好久没有发布新的文章了,主要最近一方面没看书,时间基本都用来打游戏了;另一方面看的几本书实在是看不懂,就更不能写上来了。不过今天看到了《麻衣相法》这本书,就又点燃了本人的兴趣,以后失业了,可以摆个小摊子谋生! 话不多说,先把这本书开始的针对人的面部部位进行各…...
vLLM技术解析:大语言模型推理服务的性能革新引擎
vLLM大模型 vLLM(Vectorized Large Language Model Serving System)是由加州大学伯克利分校计算机系统研究团队开发的下一代大语言模型推理服务系统。作为专为现代化AI部署设计的开源框架,该系统通过突破性的内存架构创新和计算流程优化&…...
《无刷空心杯电机减速机选型及行业发展趋势》
无刷空心杯电机作为高精度驱动系统的核心部件,通常需搭配减速机以实现低转速、高扭矩输出。以下是当前主流的减速机类型、市场占比、参数对比及优劣势分析,结合行业数据与典型应用场景展开说明: 一、主流减速机类型及市场占比 1. 行星减速机 市场占比:约 45%-55%(工业自…...
Java锁的升级流程详解:无锁、偏向锁、轻量级锁、重量级锁
在Java中,为了在多线程并发场景下既保证线程安全,又尽可能提高性能,JVM针对synchronized实现了锁的优化升级机制。 锁可以从无锁逐步升级到偏向锁、轻量级锁,最后是重量级锁。 话不多说,发车! 一、无锁&am…...
terraform local-exec与remote-exec详解
在 Terraform 中,local-exec 和 remote-exec 是两种常用的 provisioner(资源调配器),用于在资源创建前后执行脚本或命令。它们的核心区别在于执行位置:local-exec 在运行 Terraform 的本地机器上执行命令,而…...
武装Burp Suite工具:APIKit插件_接口安全扫描.
武装Burp Suite工具:APIKit插件_接口安全扫描. API安全是指通过技术手段和管理措施保护应用程序接口(API)免受未授权访问、数据泄露或恶意攻击的防护体系,核心措施包括身份认证(如OAuth2.0/JWT)、权限控制…...
数据库系统概论|第三章:关系数据库标准语言SQL—课程笔记6
前言 经过前面几篇文章的介绍,已经完成了对于数据查询操作的介绍,接下来,本篇文章将介绍数据更新这一板块,包括插入数据、修改数据以及删除数据三种操作方法。 注:本文中所涉及的数据库前文中已经介绍(指…...
如何在idea中写spark程序
1. 安装配置 Java 和 Scala Java:确保已安装合适版本的 Java Development Kit(JDK),并配置好 JAVA_HOME 环境变量。Scala:由于 Spark 常用 Scala 语言编写,需安装 Scala 开发环境。可在 IDEA 中通过 Se…...
Linux428 chmod 0xxx 1xxx 2xxx 4xxx;umask;chown 属主属组 软件包rpm
sudo: 账户过期,或 PAM 配置缺少 sudo 使用的“account”节,联系您的系统管理员 这样子有没有用嘞 不行 为什么使用caozx26用户sudo修改了shop文件夹强制位,shop文件夹权限中不显示 成功了?真奇怪 查看文件夹权限用 -ld ch…...
基于强化学习的用于非刚性图像配准的引导式超声采集|文献速递-深度学习医疗AI最新文献
Title 题目 Guided ultrasound acquisition for nonrigid image registration usingreinforcement learning 基于强化学习的用于非刚性图像配准的引导式超声采集 01 文献速递介绍 超声成像通常用于引导手术和其他医疗程序,在这些过程中,临床医生会持…...
Shell脚本-嵌套循环应用案例
在Shell脚本编程中,嵌套循环是一种强大的工具,可以用于处理复杂的任务和数据结构。通过在一个循环内部再嵌套另一个循环,我们可以实现对多维数组、矩阵操作、文件处理等多种高级功能。本文将通过几个实际的应用案例来展示如何使用嵌套循环解决…...
QTableView复选框居中
目录 方法一:QSS方法2:自定义复选框委托类一、构造函数 CheckBoxDelegate()二、paint() 方法三、editorEvent() 方法四、关键设计要点五、扩展应用场景六、代码示例(补充) 方法一:QSS QTableView::indicator {position: relative…...
C语言教程(十八):C 语言共用体详解
一、共用体的定义 共用体的定义和结构体类似,使用 union 关键字,其基本语法如下: union 共用体名 { 数据类型 成员1; 数据类型 成员2; // 可以有更多成员 }; 以下是一个简单的共用体定义示例: union Data {int i;float f;char …...
企业办公系统开发如何重塑现代工作方式?
随着工作方式的革新,企业办公软件开发已成为提升组织效率的核心驱动力。从基础的文档处理到复杂的协同办公平台开发,现代办公系统正在彻底改变传统工作模式。本文将深入解析办公类软件的关键技术与发展趋势。 一、企业级办公系统开发的核心模块 专业的O…...
springboot 实现敏感信息脱敏
记录于2025年4月28号晚上--梧州少帅 1. 定义枚举类: public enum DesensitizeType {NAME, EMAIL } 2. 创建自定义注解: 用于标记需要脱敏的字段及其类型。 Retention(RetentionPolicy.RUNTIME) JacksonAnnotationsInside JsonSerialize(using Desen…...
JavaWeb学习打卡-Day5-Spring事务管理、SpringAOP
Spring事务管理 Transactional注解 位置:业务层(Service)的方法上、类上、接口上。作用:将当前方法交给spring进行事务管理,方法执行前,开启事务;成功执行完毕,提交事务࿱…...
项目立项管理
项目立项管理是对拟规划和实施的项目技术上的先进性、适用性,经济上的合理性、效益性,实施上的可能性、风险性以及社会价值的有效性、可持续性等进行全面科学的综合分析,为项目决策提供客观依据的一种技术经济研究活动。 一般包括项目建议与…...
一文梳理业财融合在财务管理中的运用!
目录 一、业财融合在财务管理中的运用概括 二、促进财务决策科学化 1. 传统财务决策的局限性 2. 业财融合助力财务决策科学化 三、加强成本控制 1. 传统成本控制的不足 2. 业财融合实现精准成本管控 四、优化资金管理 1. 传统资金管理的问题 2. 业财融合优化资金配置…...
C#核心知识
委托 如何声明一个委托:通过 【delegate 返回值类型 委托名称】 的格式来定义 如何使用一个委托:使用new关键字,并传入和声明委托的构造相同的方法名,比如:new 委托名称(与委托的参数和返回值相同的一个方法名) 如何…...
[多彩数据结构] 笛卡尔树
[多彩数据结构] 笛卡尔树 定义 笛卡尔树,就是一棵树(废话)中存两个信息,为 ( w , i ) (w,i) (w,i)。其中 k w e i g h t , i i d kweight,iid kweight,iid。 即 w w w 存的是节点的值, i i i 存的是编号。 每…...
【Spark入门】Spark RDD基础:转换与动作操作深度解析
目录 1 RDD编程模型概述 1.1 RDD操作分类 2 常用转换操作详解 2.1 基本转换操作 2.2 键值对转换操作 2.3 复杂转换操作 3 动作操作触发机制 3.1 常见动作操作 3.2 动作操作性能对比 4 RDD执行机制深度解析 4.1 惰性求值原理 4.2 任务生成过程 5 性能优化实践 5.1 …...
一文了解 模型上下文协议(MCP)
MCP(Model Context Protocol,模型上下文协议)是由Anthropic公司于2024年11月推出的一项开放标准协议,旨在解决大型语言模型(LLM)与外部数据源和工具之间的通信问题。其核心目标是通过提供一个标准化的接口&…...
每日算法-250428
每日算法 - 2024年4月28日 记录今天完成的几道 LeetCode 算法题。 1877. 数组中最大数对和的最小值 题目描述: 思路 贪心策略。 解题过程 为了最小化所有数对和中的最大值,直观的想法是避免让两个较大的数相加。因此,最优策略是将数组中最小的元素…...
【“星瑞” O6 评测】 — CPU llama.cpp不同优化速度对比
前言 随着大模型应用场景的不断拓展,arm cpu 凭借其独特优势在大模型推理领域的重要性日益凸显。它在性能、功耗、架构适配等多方面发挥关键作用,推动大模型在不同场景落地 1. Kleidi AI 简介 Arm Kleidi 成为解决这些挑战的理想方案,它能…...
Redis 常见问题深度剖析与全方位解决方案指南
Redis 是一款广泛使用的开源内存数据库,在实际应用中常会遇到以下一些常见问题: 1.内存占用问题 问题描述:随着数据量的不断增加,Redis 占用的内存可能会超出预期,导致服务器内存不足,影响系统的稳定性和…...
在g2o图优化框架中,顶点(Vertex)和边(Edge)的定义与功能的区别
在g2o图优化框架中,顶点(Vertex)和边(Edge)是构建优化问题的核心组件,两者的定义与功能存在以下关键区别: 1. 作用与本质差异 顶点(Vertex) 代表待优化的变量,例如: 位姿(如VertexSE3Expmap表示3D位姿,包含平移和旋转)空间点坐标(如VertexPointXYZ表示3D点)参数…...
stm32wb55rg (2) 阅读资料手册
阅读资料是嵌入式开发的必备技能,能够从资料中找到自己想要的技术信息,才是最为核心的技术能力。 nucleowb55rg板子的MCU为stm32wb55rg,这块板子的资料有很多,但有些内容可以边用边读,有些内容有必要预先掌握下。 下面…...
基于Python的携程国际机票价格抓取与分析
一、项目背景与目标 携程作为中国领先的在线旅行服务平台,提供了丰富的机票预订服务。其国际机票价格受多种因素影响,包括季节、节假日、航班时刻等。通过抓取携程国际机票价格数据,我们可以进行价格趋势分析、性价比评估以及旅行规划建议等…...