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

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] 中的每个 ianswer[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

解题思路:

  1. 初始化线段树
    • 创建一个 LazySegmentTree 实例,其大小为 4n(因为线段树通常需要一个额外的空间来存储内部节点)。
    • 初始化 cnt 数组来存储每个节点的区间内未访问元素的数量。
    • 初始化 todo 数组来存储延迟的更新操作。
    • 调用 build 方法来构建线段树,初始时所有元素都是未访问的,所以每个叶子节点的 cnt 值都设为 1(表示该位置是未访问的)。
  2. 处理查询
    • 对于每个查询 (l, r),调用 update 方法将索引从 l+2 到 r(注意这里的 l+2 是因为题目可能有特定的索引约定,比如索引 0 和 1 被视为特殊情况,或者为了避免边界问题)之间的所有元素标记为已访问(即将其 cnt 值更新为 0)。
    • 在每次更新后,通过查看根节点的 cnt 值(即整个数组的未访问元素数量)减 1 来计算最近的未访问元素与数组起始位置的距离。这是因为每次更新都会使得一个元素从未访问变为已访问,而根节点的 cnt 值反映了整个数组中未访问元素的数量。减 1 是因为索引是从 0 开始的,而我们需要的是距离,所以需要将计数器的值转换为实际的索引距离(这里假设数组中的元素是连续排列的,没有空缺)。
  3. 线段树的操作
    • build 方法用于构建线段树,初始化每个叶子节点的 cnt 值。
    • maintain 方法用于维护节点的 cnt 值,确保它反映了其子节点的 cnt 值之和。
    • do 方法用于立即更新节点的 cnt 值和 todo 值。
    • spread 方法用于将延迟的更新操作传播到子节点。
    • update 方法用于执行区间更新操作,使用延迟技术来优化性能。
    • query 方法虽然在这段代码中未使用,但通常用于查询区间内的某些信息(如最大值、最小值等)。

相关文章:

Leetcode打卡:新增道路查询后的最短距离II

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

Spring Web入门练习

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

计算机毕业设计 | SpringBoot+vue汽车资讯网站 汽车购买咨询管理系统(附源码+论文)

1&#xff0c;绪论 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及&#xff0c;互联网成为人们查找信息的重要场所&#xff0c;二十一世纪是信息的时代&#xff0c;所以信息的管理显得特别重要。因此&#xff0c;使用计算机来管理汽车资讯网站的相关信息成为必然…...

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&#xff0c;可以先做检查连接&#xff1a;...

react 如何修改弹出的modal的标题

原来标题的样子&#xff1a; 修改为&#xff1a; 实现方式&#xff1a; <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#编程中&#xff0c;二维数组&#xff08;或矩阵&#xff09;是一种重要的数据结构&#xff0c;它不仅能够高效地存储和组织数据&#xff0c;还能通过其行、列和交叉点&#xff08;备注&#xff1a;此处相交处通常称为“元素”或“单元格”&#xff0c;代表二维数组中的一个…...

HTML5拖拽API学习 托拽排序和可托拽课程表

文章目录 前言拖拽API核心概念拖拽式使用流程例子注意事项综合例子&#x1f330; 可拖拽课程表拖拽排序 前言 前端拖拽功能让网页元素可以通过鼠标或触摸操作移动。HTML5 提供了标准的拖拽API&#xff0c;简化了拖放操作的实现。以下是拖拽API的基本使用指南&#xff1a; 拖拽…...

内容补充页(相关公式解释)

from 学习日记_20241117_聚类方法&#xff08;高斯混合模型&#xff09; 学习日记_20241117_聚类方法&#xff08;高斯混合模型&#xff09; 公式 P ( Z k ) π k P(Zk) \pi_k P(Zk)πk​ 在高斯混合模型 (GMM) 中&#xff0c;公式 P ( Z k ) π k P(Zk) \pi_k P(Zk…...

vue中动态渲染静态图片资源

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

管伊佳ERP,原名华夏ERP,一个简约易上手的国产ERP系统

JSH_ERP&#xff08;管伊佳ERP&#xff09;是一款开源、模块化的企业资源计划系统&#xff0c;旨在为中小企业提供高效的管理工具。它基于SpringBoot框架和SaaS模式&#xff0c;支持进销存、财务、生产等业务模块&#xff0c;包括零售、采购、销售、仓库和报表管理。 核心特点…...

学习虚幻C++开发日志——委托(持续更新中)

委托 官方文档&#xff1a;Delegates and Lamba Functions in Unreal Engine | 虚幻引擎 5.5 文档 | Epic Developer Community | Epic Developer Community 简单地说&#xff0c;委托就像是一个“函数指针”&#xff0c;但它更加安全和灵活。它允许程序在运行时动态地调用不…...

开窗函数 - first_value/last_value

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

「一」HarmonyOS端云一体化概要

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

nodejs21: 快速构建自定义设计样式Tailwind CSS

Tailwind CSS 是一个功能强大的低级 CSS 框架&#xff0c;只需书写 HTML 代码&#xff0c;无需书写 CSS&#xff0c;即可快速构建美观的网站。 1. 安装 Tailwind CSS React 项目中安装 Tailwind CSS&#xff1a; 1.1 安装 Tailwind CSS 和相关依赖 安装 Tailwind CSS: npm…...

从JSON数据提取嵌套字段并转换为独立列的简洁方法

从JSON数据提取嵌套字段并转换为独立列的简洁方法 在数据处理和数据分析的日常工作中&#xff0c;我们经常遇到复杂的嵌套数据结构&#xff0c;特别是嵌入在JSON字段中的数据。这些数据往往需要解析并展开成独立的列&#xff0c;以便后续分析和建模。本文将详细介绍如何在Pyth…...

湘潭大学软件工程算法设计与分析考试复习笔记(四)

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

特征交叉-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&#xff0c;低秩矩阵的维度&#xff0c;应该小…...

stm32cubemx+VSCODE+GCC+makefile 开发环境搭建

title: stm32cubemxVSCODEGCCmakefile 开发环境搭建 tags: FreertosHalstm32cubeMx 文章目录 内容往期内容导航第一步准备环境vscode 插件插件配置点灯 内容 往期内容导航 第一步准备环境 STM32CubeMXVSCODEMinGWOpenOcdarm-none-eabi-gcc 然后把上面下载的软件 3 4 5 bin 文…...

Go语言中的Defer机制详解与示例

在Go语言中&#xff0c;defer是一个关键字&#xff0c;用于确保资源的清理和释放&#xff0c;特别是在函数中创建的资源。defer语句会将其后的函数调用推迟到包含它的函数即将返回时执行。这使得defer成为处理文件关闭、数据库连接释放、解锁等资源清理操作的理想选择。 Defer…...

XML Group端口详解

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

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

招商蛇口 | 执笔CID,启幕低密生活新境

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

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

医疗AI模型可解释性编程研究:基于SHAP、LIME与Anchor

1 医疗树模型与可解释人工智能基础 医疗领域的人工智能应用正迅速从理论研究转向临床实践,在这一过程中,模型可解释性已成为确保AI系统被医疗专业人员接受和信任的关键因素。基于树模型的集成算法(如RandomForest、XGBoost、LightGBM)因其卓越的预测性能和相对良好的解释性…...

LangChain【6】之输出解析器:结构化LLM响应的关键工具

文章目录 一 LangChain输出解析器概述1.1 什么是输出解析器&#xff1f;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来袭&#xff01;_哔哩哔哩_bilibili GitHub - lucidrains/meshgpt-pytorch: Implementation of MeshGPT, SOTA Me…...