首页 > 其他分享 >Leetcode 3244. Shortest Distance After Road Addition Queries II

Leetcode 3244. Shortest Distance After Road Addition Queries II

时间:2024-08-04 20:25:08浏览次数:14  
标签:Distance arr Addition After bisect ans Shortest

1. 解题思路

这一题的话由于题目限制了road不会交叉,因此我们只需要在每次增加road之后将中间节点删除,剩余的路径节点数目即为路径长度。

2. 代码实现

给出python代码实现如下:

class Solution:
    def shortestDistanceAfterQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        ans = []
        arr = [i for i in range(n)]
        for u, v in queries:
            i, j = bisect.bisect_left(arr, u), bisect.bisect_left(arr, v)
            if arr[i] == u and arr[j] == v:
                while arr[i+1] != v:
                    arr.pop(i+1)
            ans.append(len(arr)-1)
        return ans

提交代码评测得到:耗时4402ms,占用内存53MB。

标签:Distance,arr,Addition,After,bisect,ans,Shortest
From: https://blog.csdn.net/codename_cys/article/details/140911391

相关文章

  • Digitwise_addition:超出限制:如果超出 -> 代码超时
    我正在研究kata。按位加法是一种特殊的加法,它不是通常向数字加1,而是向该数字的每个数字加1。如果数字是9,我们将其替换为10,而不保留到下一个数字。示例123->234任务编写一个接受两个数字n和k的函数,并在应用数字加法k次后输出n中的位数。由于答......
  • 易优CMS模板标签beafter上下篇获取下一篇内容
    【基础用法】标签:beafter描述:获取当前文档上一篇、下一篇内容。用法:{eyou:beafterget='pre'}<ahref="{$field.arcurl}"title="{$field.title}">上一篇:{$field.title}</a>{eyou:else/}上一篇:暂无{/eyou:beafter}{eyou:beafterget='next&......
  • LeetCode | 370 RangeAddition
    https://github.com/dolphinmind/datastructure/tree/datastructure-array-02分析数组本身的递归性,差分数组的不变性和可逆性,在left索引上对当前及后续所有元素产生影响,在right+1索引上进行反操作,消除这种影响,再进行还原即可数组本身具有递归性差分数组性质:对于任何常数c......
  • centos7 解决docker 拉取镜像错误 error pulling image configuration: download fai
    为什么会出现i/otimeout错误?i/otimeout错误主要是由于网络连接不稳定或者服务器响应慢导致的。当Docker尝试从镜像仓库拉取镜像时,如果在规定时间内没有得到响应,就会出现i/otimeout错误。“错误的根源在于网络连接和镜像仓库的响应速度” 解决方案:换源为了解决这个......
  • golang 如从一个通道(channel)接收数据时在预期时间没接收到,可以使用select语句和time.A
    在Go语言中,如果希望在从一个通道(channel)接收数据时设置超时,可以使用select语句和time.After函数。以下是一个示例代码,演示了如何实现这个功能:packagemainimport("fmt""time")funcmain(){//创建一个通道ch:=make(chanstring)//启动一......
  • docker 拉取镜像超时:error pulling image configuration: download failed after atte
    之前是正常的,今天就罢工了,可能原因是国外镜像不稳定,被针对了吧。errorpullingimageconfiguration:downloadfailedafterattempts=6:dialtcp168.143.171.189:443:i/otimeout那就改为国内镜像:1.创建/etc/docker目录(已有的跳过)sudomkdir-p/etc/docker 2.修改......
  • 图像生成中图像质量评估指标—Chamfer Distance介绍
    文章目录1.背景介绍2.实际应用3.总结和讨论1.背景介绍ChamferDistance是一种用于度量两个集合之间相似性的方法,尤其在计算机视觉和图像处理中,它常用于比较图像或形状的二值表示。ChamferDistance基于局部邻域的概念,通过计算一个集合中每个点到另一个集合最近......
  • Exhaust Aftertreatment Diagnosis for Cummins Diesel Engines
    ToperformexhaustaftertreatmentdiagnosisonCumminsenginesusingCumminsInsite,youwillneedtousespecializedsoftwaretodiagnoseandtroubleshootissuesrelatedtotheexhaustaftertreatmentsystem.Theexhaustaftertreatmentsystemincludescom......
  • 每日一题- Jump Distance Sum
    https://www.luogu.com.cn/problem/AT_abc351_e*这是我的第一个随笔,请大佬们指正。数学知识:https://oi-wiki.org/geometry/distance/*曼哈顿距离:在二维空间内,两个点之间的曼哈顿距离(Manhattandistance)为它们横坐标之差的绝对值与纵坐标之差的绝对值之和。设点A(x1,y1),B(x2,......
  • P9058 [Ynoi2004] rpmtdq 与 P9678 [ICPC2022 Jinan R] Tree Distance
    思路:注意到点对数量有\(N^2\)个,考虑丢掉一些无用的点对。对于点对\((x_1,y_1),(x_2,y_2)\),满足\(x_1\lex_2<y_2\ley_1\),即区间\([x_2,y_2]\)被\([x_1,y_1]\)包含,此时满足若询问到了\([x_1,y_1]\),则一定会询问到\([x_2,y_2]\)。若满足\(\operatorname{dis}(x_1......