LeetCode:1184. 公交站间的距离 一次遍历数组,复杂度O(n)
1184. 公交站间的距离
today 1184 公交站间的距离
题目描述
环形公交路线上有 n 个站,按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离,distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。
环线上的公交车都可以按顺时针和逆时针的方向行驶。
返回乘客从出发点 start 到目的地 destination 之间的最短距离。
示例 1:
输入:distance = [1,2,3,4], start = 0, destination = 1
输出:1
解释:公交站 0 和 1 之间的距离是 1
示例 2:
输入:distance = [1,2,3,4], start = 0, destination = 2
输出:3
解释:公交站 0 和 2 之间的距离是 3
示例 3:
输入:distance = [1,2,3,4], start = 0, destination = 3
输出:4
解释:公交站 0 和 3 之间的距离是 4
提示:
1 <= n <= 10^4distance.length == n0 <= start, destination < n0 <= distance[i] <= 10^4
题目解析
这道题目是一道关于环形公交路线的题目。
首先,我们可以将环形公交路线看作是一个环,然后我们可以从 start 出发,沿着顺时针方向行驶,直到到达 destination,这样得到的距离为sum1。
我们再从 destination 出发,沿着逆时针方向行驶,直到到达 start,这样得到的距离为sum2,最后我们返回 min(sum1, sum2)。
值得注意的是,sum1和sum2的和为整个环路的距离。因此我们可以通过一次遍历,解决问题。
复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( 1 ) O(1) O(1)
代码实现
Python版本:
class Solution(object):def distanceBetweenBusStops(self, distance, start, destination):if start>destination:start,destination=destination,startsum1=sum(distance[start:destination])sum2=sum(distance[:])-sum1return min(sum1,sum2)
C++版本:
class Solution {
public:int distanceBetweenBusStops(vector<int>& distance, int start, int destination) {if (start > destination) {swap(start, destination);}int sum1=0,sum2=0;for(int i=0;i<distance.size();i++){if(i>=start&&i<destination)sum1+=distance[i];elsesum2+=distance[i];}return min(sum1,sum2);}
};
Go版本:
func distanceBetweenBusStops(distance []int, start, destination int) int {if start > destination {start, destination = destination, start}sum1, sum2 := 0, 0for i, j := range distance {if start <= i && i < destination {sum1 += j} else {sum2 += j}}return min(sum1, sum2)
}相关文章:
LeetCode:1184. 公交站间的距离 一次遍历数组,复杂度O(n)
1184. 公交站间的距离 today 1184 公交站间的距离 题目描述 环形公交路线上有 n 个站,按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离,distance[i] 表示编号为 i 的车站和编号为 (i 1) % n 的车站之间的距离。 环线上的公交车都…...
牛客周赛 Round 60(A,B,C,D,E,F)
比赛链接 官方题解 这场基本都是数学题,官方题解讲的还不错,F能听懂的话其实不难。E是一个球盒模型的组合问题,F是化简递推式,成环时的解决方法很不错。 A 困难数学题 思路: 一个数异或两次结果为 0 0 0ÿ…...
vueCropper裁剪图片(不模糊)以及记录使用方法
需求:上传限定比例的图片。前端框架是vue3 element plus。 问题:使用vueCropper后比例固定。但是上传后的图片很模糊 vueCropper官网 解决办法 vueCropper中有一个full和high两个参数,记得开启 const options: any reactive({img: , // 原…...
【HTML】HTML页面和常见标签
文章目录 什么是前端HTML 页面编写如何快速生成代码框架常见标签注释标签标题标签段落标签换行标签格式化标签 什么是前端 Web 前端,用来直接给以用户呈现的一个一个的网页。一个软件通常是由 后端前端 完成的 后端:通过 Java/C等语言,完成相…...
鸿蒙 ArkUI组件二
ArkUI组件(续) 文本组件 在HarmonyOS中,Text/Span组件是文本控件中的一个关键部分。Text控件可以用来显示文本内容,而Span只能作为Text组件的子组件显示文本内容。 Text/Span组件的用法非常简单和直观。我们可以通过Text组件来显…...
PHP 实现 redis 分布式锁
分布式锁 如果是强一致性保证,在获取锁或者失败后引入数据库存储扫表、mq 等方式进行补偿 如果可以容忍少量异常就不需要考虑了 像这里的代码,没吃建立一个链接铺货,性能损耗时间延迟也是很大的,也可在一块代码中进行服务&…...
vue3 自定义el-tree树形结构样式
这里样式设置主要用到了 windcss 实现效果 模拟数据 这里也可以用模拟的数据,下面用的是后端请求的真实数据 [{"id": 5,"rule_id": 0,"status": 1,"create_time": "2019-08-11 13:36:09","update_time": "…...
【网络安全】分享4个高危业务逻辑漏洞
未经许可,不得转载。 文章目录 正文逻辑漏洞1逻辑漏洞2逻辑漏洞3逻辑漏洞4其它正文 该目标程序是一家提供浏览器服务的公司,其核心功能是网页抓取和多账户登录操作,类似于浏览器中的隐身模式,但更加强大和高效。通过该平台,用户可以轻松管理并同时运行数百个隐身浏览器实…...
【装机教程】Visual Studio Community 2019离线安装
Visual Studio 2019离线安装 由于现在 官网只支持在线安装最新版的Visual Studio 2022,因此 Visual Studio Community 2019需要离线安装。 下载离线安装镜像,并解压。点击vs_setup.exe运行。 选择安装位置,四处位置需要确定。 选择语言包&…...
NumPy 线性代数
NumPy 线性代数 NumPy 是 Python 中用于科学计算的核心库之一,它提供了一个强大的数学函数库,特别是在处理大型多维数组和矩阵时表现出色。线性代数是 NumPy 的一个重要组成部分,它包含了大量的函数和运算符,用于执行矩阵和向量的…...
家装材料之水泥,最容易被忽视的基础材料!
由于水泥在装修中扮演辅料的角色,很多业主往往会忽视它们的质量。事实上,装修无小事,不能抱有抓大放小的态度。 更何况水泥是装修工程的基础材料,在家居装修中,地面、墙面的找平以及瓷砖、大理石的铺贴&#…...
openstack之keystone介绍
功能 keystone在OpenStack中负责: 管理:用户、租户和权限; 认证:组件相互访问的身份认证; 鉴权:提供 RBAC(Role Based Access Control) 权限体系; 服务注册与发现&#…...
【图像拼接】基于SIFT/SURF特征算法的图像拼接,matlab实现
博主简介:matlab图像代码项目合作(扣扣:3249726188) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 本次案例是基于SIFT/SURF特征算法的图像拼接,用matlab实现。 一、案例背景和算法介…...
《微信小程序实战(2) · 组件封装》
📢 大家好,我是 【战神刘玉栋】,有10多年的研发经验,致力于前后端技术栈的知识沉淀和传播。 💗 🌻 CSDN入驻不久,希望大家多多支持,后续会继续提升文章质量,绝不滥竽充数…...
LaTex2024 下载安装运行HelloWorld—全流程笔记
LaTex安装教程🚀 这是读博之后写的第一篇文章,来到新课题组之后,新课题组主要是用Latex,在之前的课题组,还是比较常用world,所以就研究了一下Latex的下载和安装,虽然网上已经有了不少教程&#…...
Golang | Leetcode Golang题解之第404题左叶子之和
题目: 题解: func isLeafNode(node *TreeNode) bool {return node.Left nil && node.Right nil }func sumOfLeftLeaves(root *TreeNode) (ans int) {if root nil {return}q : []*TreeNode{root}for len(q) > 0 {node : q[0]q q[1:]if no…...
基于yolov8+lprnet的中文车牌识别系统python源码+pytorch模型+精美GUI界面
【算法介绍】 基于YOLOv8和LPRNet的中文车牌识别系统是一种高效且准确的解决方案,结合了目标检测与字符识别的先进技术。YOLOv8作为最新的实时目标检测算法,以其高速度和精确度著称,能够迅速在图像或视频中定位车牌位置。LPRNet则是一种专为…...
电信创维光猫DT741超级密码
正常的D740系是创维系列光猫如:SK-D740 之类的超密获取办法-光猫/adsl/cable无线一体机-恩山无线论坛 但是我这个固件是DT741v1.0 我只能说很S -B,这个版本如果是1.02那就可以很轻松的去用通用办法解决,但是呢!还有办法就是用最传…...
PostgreSQL的流复制断点续传
PostgreSQL的流复制断点续传 PostgreSQL的流复制(Streaming Replication)具有断点续传的能力,这意味着当主节点和备用节点之间的连接由于网络故障等原因中断后,备用节点会自动从中断点继续接收WAL(Write-Ahead Loggin…...
【bug】通过lora方式微调sdxl inpainting踩坑
报错内容 ValueError: Attempting to unscale FP16 gradients. 报错位置 if accelerator.sync_gradients:params_to_clip (itertools.chain(unet_lora_parameters, text_lora_parameters_one, text_lora_parameters_two)if args.train_text_encoderelse unet_lora_parameters…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
