Leetcode打卡:新增道路查询后的最短距离II
执行结果:通过
题目:3244 新增道路查询后的最短距离II
给你一个整数 n
和一个二维整数数组 queries
。
有 n
个城市,编号从 0
到 n - 1
。初始时,每个城市 i
都有一条单向道路通往城市 i + 1
( 0 <= i < n - 1
)。
queries[i] = [ui, vi]
表示新建一条从城市 ui
到城市 vi
的单向道路。每次查询后,你需要找到从城市 0
到城市 n - 1
的最短路径的长度。
所有查询中不会存在两个查询都满足 queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]
。
返回一个数组 answer
,对于范围 [0, queries.length - 1]
中的每个 i
,answer[i]
是处理完前 i + 1
个查询后,从城市 0
到城市 n - 1
的最短路径的长度。
示例 1:
输入: n = 5, queries = [[2, 4], [0, 2], [0, 4]]
输出: [3, 2, 1]
解释:
新增一条从 2 到 4 的道路后,从 0 到 4 的最短路径长度为 3。
新增一条从 0 到 2 的道路后,从 0 到 4 的最短路径长度为 2。
新增一条从 0 到 4 的道路后,从 0 到 4 的最短路径长度为 1。
示例 2:
输入: n = 4, queries = [[0, 3], [0, 2]]
输出: [1, 1]
解释:
新增一条从 0 到 3 的道路后,从 0 到 3 的最短路径长度为 1。
新增一条从 0 到 2 的道路后,从 0 到 3 的最短路径长度仍为 1。
提示:
3 <= n <= 105
1 <= queries.length <= 105
queries[i].length == 2
0 <= queries[i][0] < queries[i][1] < n
1 < queries[i][1] - queries[i][0]
- 查询中不存在重复的道路。
- 不存在两个查询都满足
i != j
且queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]
。
代码以及解题思路
代码:
class Solution:def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:st = LazySegmentTree(n)ans = []for l, r in queries:st.update(1,1,n,l+2,r, 0)ans.append(st.cnt[1]-1)return ansclass LazySegmentTree:def __init__(self, n: int):self.cnt = [0] * (4 * n)self.todo = [-1] * (4 * n)self.build(1,1,n)# 初始化线段树 o,l,r=1,1,ndef build(self, o: int, l: int, r: int) -> None:if l == r:self.cnt[o] = 1returnm = (l + r) >> 1self.build(o * 2, l, m)self.build(o * 2 + 1, m + 1, r)self.maintain(o)def maintain(self, o: int) -> None:self.cnt[o] = self.cnt[o * 2] + self.cnt[o * 2 + 1]def do(self, o: int, val: int) -> None:self.cnt[o] = valself.todo[o] = valdef spread(self, o: int) -> None:v = self.todo[o]if v == 0:self.do(o * 2, v)self.do(o * 2 + 1, v)self.todo[o] = -1def update(self, o: int, l: int, r: int, L: int, R: int, val: int) -> None:if L <= l and r <= R:self.do(o, val)returnself.spread(o)m = (l + r) >> 1if m >= L:self.update(o * 2, l, m, L, R, val)if m < R:self.update(o * 2 + 1, m + 1, r, L, R, val)self.maintain(o)def query(self, o: int, l: int, r: int, L: int, R: int) -> int:if L <= l and r <= R:return self.cnt[o]self.spread(o)m = (l + r) >> 1res = 0if L <= m:res = self.query(o * 2, l, m, L, R)if m < R:res = max(res, self.query(o * 2 + 1, m + 1, r, L, R))return res
解题思路:
- 初始化线段树:
- 创建一个
LazySegmentTree
实例,其大小为4n
(因为线段树通常需要一个额外的空间来存储内部节点)。 - 初始化
cnt
数组来存储每个节点的区间内未访问元素的数量。 - 初始化
todo
数组来存储延迟的更新操作。 - 调用
build
方法来构建线段树,初始时所有元素都是未访问的,所以每个叶子节点的cnt
值都设为 1(表示该位置是未访问的)。
- 创建一个
- 处理查询:
- 对于每个查询
(l, r)
,调用update
方法将索引从l+2
到r
(注意这里的l+2
是因为题目可能有特定的索引约定,比如索引 0 和 1 被视为特殊情况,或者为了避免边界问题)之间的所有元素标记为已访问(即将其cnt
值更新为 0)。 - 在每次更新后,通过查看根节点的
cnt
值(即整个数组的未访问元素数量)减 1 来计算最近的未访问元素与数组起始位置的距离。这是因为每次更新都会使得一个元素从未访问变为已访问,而根节点的cnt
值反映了整个数组中未访问元素的数量。减 1 是因为索引是从 0 开始的,而我们需要的是距离,所以需要将计数器的值转换为实际的索引距离(这里假设数组中的元素是连续排列的,没有空缺)。
- 对于每个查询
- 线段树的操作:
build
方法用于构建线段树,初始化每个叶子节点的cnt
值。maintain
方法用于维护节点的cnt
值,确保它反映了其子节点的cnt
值之和。do
方法用于立即更新节点的cnt
值和todo
值。spread
方法用于将延迟的更新操作传播到子节点。update
方法用于执行区间更新操作,使用延迟技术来优化性能。query
方法虽然在这段代码中未使用,但通常用于查询区间内的某些信息(如最大值、最小值等)。
相关文章:

Leetcode打卡:新增道路查询后的最短距离II
执行结果:通过 题目:3244 新增道路查询后的最短距离II 给你一个整数 n 和一个二维整数数组 queries。 有 n 个城市,编号从 0 到 n - 1。初始时,每个城市 i 都有一条单向道路通往城市 i 1( 0 < i < n - 1&…...

Spring Web入门练习
加法计算器 约定前后端交互接⼝ 约定 "前后端交互接⼝" 是进⾏ Web 开发中的关键环节. 接⼝⼜叫 API(Application Programming Interface), 我们⼀般讲到接⼝或者 API,指的都是同⼀个东西. 是指应⽤程序对外提供的服务的描述, ⽤于交换信息…...

计算机毕业设计 | SpringBoot+vue汽车资讯网站 汽车购买咨询管理系统(附源码+论文)
1,绪论 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及,互联网成为人们查找信息的重要场所,二十一世纪是信息的时代,所以信息的管理显得特别重要。因此,使用计算机来管理汽车资讯网站的相关信息成为必然…...

stm32下的ADC转换(江科协 HAL版)
十二. ADC采样 文章目录 十二. ADC采样12.1 ADC的采样原理12.2 STM32的采样基本过程1.引脚与GPIO端口的对应关系2.ADC规则组的四种转换模式(**)2.2 关于转换模式与配置之间的关系 12.3 ADC的时钟12.4 代码实现(ADC单通道 & ADC多通道)1. 单通道采样2. 多通道采样 19.ADC模数…...

解决IntelliJ IDEA的Plugins无法访问Marketplace去下载插件
勾选Auto-detect proxy setting并填入 https://plugins.jetbrains.com 代理URL,可以先做检查连接:...

react 如何修改弹出的modal的标题
原来标题的样子: 修改为: 实现方式: <Modal title<span>股价趋势/{this.state.pccode}</span> visible{this.state.isPriceModalOpen} style{{ top: 20 }} width{1320} height{400} footer{null} onCancel{()>this.hideMo…...

C#中的二维数组的应用:探索物理含义与数据结构的奇妙融合
在C#编程中,二维数组(或矩阵)是一种重要的数据结构,它不仅能够高效地存储和组织数据,还能通过其行、列和交叉点(备注:此处相交处通常称为“元素”或“单元格”,代表二维数组中的一个…...

HTML5拖拽API学习 托拽排序和可托拽课程表
文章目录 前言拖拽API核心概念拖拽式使用流程例子注意事项综合例子🌰 可拖拽课程表拖拽排序 前言 前端拖拽功能让网页元素可以通过鼠标或触摸操作移动。HTML5 提供了标准的拖拽API,简化了拖放操作的实现。以下是拖拽API的基本使用指南: 拖拽…...
内容补充页(相关公式解释)
from 学习日记_20241117_聚类方法(高斯混合模型) 学习日记_20241117_聚类方法(高斯混合模型) 公式 P ( Z k ) π k P(Zk) \pi_k P(Zk)πk 在高斯混合模型 (GMM) 中,公式 P ( Z k ) π k P(Zk) \pi_k P(Zk…...

vue中动态渲染静态图片资源
不报错且f12查看元素的时候,显示的src说明已经渲染到html的src上,但是就是不显示在页面上 原因 在vue上,动态渲染静态图片资源(比如从assets文件夹加载的图片)需要注意打包工具对静态资源的解析方式 由于vue2的脚手…...

管伊佳ERP,原名华夏ERP,一个简约易上手的国产ERP系统
JSH_ERP(管伊佳ERP)是一款开源、模块化的企业资源计划系统,旨在为中小企业提供高效的管理工具。它基于SpringBoot框架和SaaS模式,支持进销存、财务、生产等业务模块,包括零售、采购、销售、仓库和报表管理。 核心特点…...

学习虚幻C++开发日志——委托(持续更新中)
委托 官方文档:Delegates and Lamba Functions in Unreal Engine | 虚幻引擎 5.5 文档 | Epic Developer Community | Epic Developer Community 简单地说,委托就像是一个“函数指针”,但它更加安全和灵活。它允许程序在运行时动态地调用不…...

开窗函数 - first_value/last_value
1、开窗函数是什么? 开窗函数用于为行定义一个窗口(这里的窗口是指运算将要操作的行的集合),它对一组值进行操作,不需要使用 GROUP BY 子句对数据进行分组,能够在同一行中同时返回基础行的列和聚合列。 2、…...

「一」HarmonyOS端云一体化概要
关于作者 白晓明 宁夏图尔科技有限公司董事长兼CEO、坚果派联合创始人 华为HDE、润和软件HiHope社区专家、鸿蒙KOL、仓颉KOL 华为开发者学堂/51CTO学堂/CSDN学堂认证讲师 开放原子开源基金会2023开源贡献之星 「目录」 「一」HarmonyOS端云一体化概要 「二」体验HarmonyOS端云一…...

nodejs21: 快速构建自定义设计样式Tailwind CSS
Tailwind CSS 是一个功能强大的低级 CSS 框架,只需书写 HTML 代码,无需书写 CSS,即可快速构建美观的网站。 1. 安装 Tailwind CSS React 项目中安装 Tailwind CSS: 1.1 安装 Tailwind CSS 和相关依赖 安装 Tailwind CSS: npm…...
从JSON数据提取嵌套字段并转换为独立列的简洁方法
从JSON数据提取嵌套字段并转换为独立列的简洁方法 在数据处理和数据分析的日常工作中,我们经常遇到复杂的嵌套数据结构,特别是嵌入在JSON字段中的数据。这些数据往往需要解析并展开成独立的列,以便后续分析和建模。本文将详细介绍如何在Pyth…...

湘潭大学软件工程算法设计与分析考试复习笔记(四)
回顾 湘潭大学软件工程算法设计与分析考试复习笔记(一)湘潭大学软件工程算法设计与分析考试复习笔记(二)湘潭大学软件工程算法设计与分析考试复习笔记(三) 前言 现在是晚上十一点,我平时是十…...

特征交叉-DeepCross Network学习
一 tensorflow官方实现 tensorflow的官方实现已经是V2版本 class Cross(tf.keras.layers.Layer):"""Cross Layer in Deep & Cross Network to learn explicit feature interactions.Args:projection_dim: int,低秩矩阵的维度,应该小…...

stm32cubemx+VSCODE+GCC+makefile 开发环境搭建
title: stm32cubemxVSCODEGCCmakefile 开发环境搭建 tags: FreertosHalstm32cubeMx 文章目录 内容往期内容导航第一步准备环境vscode 插件插件配置点灯 内容 往期内容导航 第一步准备环境 STM32CubeMXVSCODEMinGWOpenOcdarm-none-eabi-gcc 然后把上面下载的软件 3 4 5 bin 文…...
Go语言中的Defer机制详解与示例
在Go语言中,defer是一个关键字,用于确保资源的清理和释放,特别是在函数中创建的资源。defer语句会将其后的函数调用推迟到包含它的函数即将返回时执行。这使得defer成为处理文件关闭、数据库连接释放、解锁等资源清理操作的理想选择。 Defer…...

XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...

HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...

招商蛇口 | 执笔CID,启幕低密生活新境
作为中国城市生长的力量,招商蛇口以“美好生活承载者”为使命,深耕全球111座城市,以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子,招商蛇口始终与城市发展同频共振,以建筑诠释对土地与生活的…...

【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

医疗AI模型可解释性编程研究:基于SHAP、LIME与Anchor
1 医疗树模型与可解释人工智能基础 医疗领域的人工智能应用正迅速从理论研究转向临床实践,在这一过程中,模型可解释性已成为确保AI系统被医疗专业人员接受和信任的关键因素。基于树模型的集成算法(如RandomForest、XGBoost、LightGBM)因其卓越的预测性能和相对良好的解释性…...
LangChain【6】之输出解析器:结构化LLM响应的关键工具
文章目录 一 LangChain输出解析器概述1.1 什么是输出解析器?1.2 主要功能与工作原理1.3 常用解析器类型 二 主要输出解析器类型2.1 Pydantic/Json输出解析器2.2 结构化输出解析器2.3 列表解析器2.4 日期解析器2.5 Json输出解析器2.6 xml输出解析器 三 高级使用技巧3…...

MeshGPT 笔记
[2311.15475] MeshGPT: Generating Triangle Meshes with Decoder-Only Transformers https://library.scholarcy.com/try 真正意义上的AI生成三维模型MESHGPT来袭!_哔哩哔哩_bilibili GitHub - lucidrains/meshgpt-pytorch: Implementation of MeshGPT, SOTA Me…...