【算法】插入区间
难度:中等
题目:
给你一个 无重叠的 ,按照区间起始端点排序的区间列表 intervals,其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束,并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
在 intervals 中插入区间 newInterval,使得 intervals 依然按照 starti 升序排列,且区间之间不重叠(如果有必要的话,可以合并区间)。
返回插入之后的 intervals。
注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
示例 1:
输入:intervals = [[1,3],[6,9]], newInterval = [2,5]
输出:[[1,5],[6,9]]
示例 2:
输入:intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出:[[1,2],[3,10],[12,16]]
解释:这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
提示:
0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 105
intervals 根据 starti 按 升序 排列
newInterval.length == 2
0 <= start <= end <= 105
解题思路:
这道题目的解题思路主要是遍历给定的区间列表,并根据新插入的区间newInterval与当前遍历到的区间的关系,决定如何合并或插入新区间。具体步骤如下:
- 初始化:创建一个新的结果数组result,用于存放合并后的区间。
- 处理新区间前的区间:遍历区间列表,直到遇到第一个结束点大于等于newInterval的开始点的区间。在此之前的所有区间可以直接加入结果数组,因为它们与newInterval不重叠。
- 合并重叠区间:当遇到与newInterval重叠的区间时,更新newInterval的起始和结束点,以覆盖所有重叠的区间。继续遍历,直到不重叠为止。
- 将合并后的区间加入结果:将经过更新后的newInterval加入结果数组。
- 处理新区间后的区间:将剩余的区间(即结束点小于newInterval结束点的所有区间已处理完毕)直接加入结果数组。
- 返回结果:返回合并后的区间列表result。
JavaScript 实现:
function insert(intervals, newInterval) {const result = [];let i = 0; // 用于遍历intervals的指针// 步骤2:处理新区间前的区间while (i < intervals.length && intervals[i][1] < newInterval[0]) {result.push(intervals[i]);i++;}// 步骤3:合并重叠区间while (i < intervals.length && intervals[i][0] <= newInterval[1]) {newInterval[0] = Math.min(newInterval[0], intervals[i][0]);newInterval[1] = Math.max(newInterval[1], intervals[i][1]);i++;}result.push(newInterval);// 步骤4:将合并后的区间加入结果// 步骤5:处理新区间后的区间while(i < intervals.length){result.push(intervals[i]);i++;}return result;
}
// 示例
// const intervals = [[1,3],[6,9]];
// const newInterval = [2,5];
// console.log(insert(intervals, newInterval)); // 输出: [[1,5],[6,9]]
这段代码首先定义了insert函数,它接收一个区间列表intervals和一个新插入的区间newInterval作为参数,然后按照上述步骤处理并返回合并后的区间列表。
相关文章:
【算法】插入区间
难度:中等 题目: 给你一个 无重叠的 ,按照区间起始端点排序的区间列表 intervals,其中 intervals[i] [starti, endi] 表示第 i 个区间的开始和结束,并且 intervals 按照 starti 升序排列。同样给定一个区间 newInte…...
C++ 代码实现socket 类使用TCP/IP进行通信 (windows 系统)
C 代码实现socket 类使用TCP/IP进行通信 (windows 系统) TCP客户端通信常规步骤: 1.初始换socket环境 2.socket()创建TCP套接字。 3.connect()建立到达服务器的连接。 4.与客户端进行通信,recv()/send()接受/发送信息࿰…...
前后端分离项目部署,vue--nagix发布部署,.net--API发布部署。
目录 Nginx免安装部署文件包准备一、vue前端部署1、修改http.js2、npm run build 编译项目3、解压Nginx免安装,修改nginx.conf二、.net后端发布部署1、编辑appsetting.json,配置跨域请求2、配置WebApi,点击发布3、配置文件发布到那个文件夹4、配置发布相关选项5、点击保存,…...
【BUG】已解决:UnicodeDecodeError: ‘utf-8’ codec can’t decode bytes in position 10
UnicodeDecodeError: ‘utf-8’ codec can’t decode bytes in position 10 目录 UnicodeDecodeError: ‘utf-8’ codec can’t decode bytes in position 10 【常见模块错误】 【解决方案】 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 欢迎来到我的主页&#x…...
C++ | QQ后端暑期实习面试
tcp三次握手,四次挥手 断点续传 文件断点续传是一种机制,允许在网络传输中的文件传输过程中出现断开连接或传输中断的情况下,能够恢复传输并继续传输未完成的部分。其原理如下: 检测支持:首先,服务器端和…...
实用网站推荐
学习 前端 精简CSS格式 Font Awesome 图标库 BootCDN 加速服务 合集 AI工具集 动漫、音乐 娱乐 嗷呜动漫 奈飞同步 视频下载 B站视频解析下载 文件操作 ioDraw制作图 Convertio — 文件转换器 PDF处理 LOGO...
Linux |Nethogs 监控网络使用情况
引言 互联网上为 Linux 系统提供了许多开源的网络监控工具。例如,你可以利用 iftop 命令来监测网络带宽的消耗,使用 netstat 或 ss 命令来获取网络接口的统计信息,或者通过 top 命令来查看系统中正在运行的进程。 然而,如果你真正…...
大语言模型训练过程中,怎么实现算力共享,采用什么分片规则和共享策略
目录 大语言模型训练过程中,怎么实现算力共享,采用什么分片规则和共享策略 一、算力共享的实现 二、分片规则与共享策略 三、总结 DeepSpeed、Megatron-LM是什么 DeepSpeed ZeRO技术一般不实现调参的 ZeRO技术的实现方式 ZeRO与调参的关系 NCCL是什么 一、NCCL概…...
JCR一区级 | Matlab实现TTAO-Transformer-LSTM多变量回归预测
JCR一区级 | Matlab实现TTAO-Transformer-LSTM多变量回归预测 目录 JCR一区级 | Matlab实现TTAO-Transformer-LSTM多变量回归预测效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.【JCR一区级】Matlab实现TTAO-Transformer-LSTM多变量回归预测,三角拓扑聚合…...
斐波那契数列(Fibonacci)数列 c++详解
Fibonacci数列是一个在数学和计算机科学中非常著名的数列。这个数列以其特殊的递推关系而闻名,也因其在自然界中的多次出现而引人注目。 定义: Fibonacci数列的定义如下: F(0) 0F(1) 1对于 n > 1,F(n) F(n-1) F(n-2) 也就…...
第三届人工智能、物联网和云计算技术国际会议(AIoTC 2024,9月13-15)
第三届人工智能、物联网与云计算技术国际会议(AIoTC 2024)将于2024年9月13日-15日在中国武汉举行。 本次会议由华中师范大学伍伦贡联合研究院与南京大学联合主办、江苏省大数据区块链与智能信息专委会承办、江苏省概率统计学会、江苏省应用统计学会、Sir Forum、南京理工大学、…...
家具购物小程序的设计
管理员账户功能包括:系统首页,个人中心,用户管理,家具分类管理,家具新品管理,订单管理,系统管理 微信端账号功能包括:系统首页,家具新品,家具公告࿰…...
测试面试宝典(三十四)—— token是做什么用的?
Token 在软件系统中通常具有多种重要用途。 首先,它用于身份验证和授权。用户登录成功后,系统会生成一个唯一的 token 并返回给客户端,客户端后续的请求携带这个 token 来证明其身份和访问权限,避免了每次请求都需要重新输入用户…...
计算机网络基础:4.HTTP与HTTPS
一、回顾设定 想象你在经营一家繁忙的餐厅,顾客们通过点餐系统(网卡)下单,订单被前台(路由器)接收并分发到各个厨房区域(网络设备)。光猫像是食材供应商,通过高效的物流系…...
【深度学习入门】安装conda/miniconda、所需包类、CUDA与conda/Miniconda间的关系
深度学习入门 须知 本教程跟随李沐老师课程随笔,课程链接点击此处。 CUDA和Anaconda的关系 CUDA Toolkit是由Nvidia官方提供的完整工具包,其中提供了Nvidia驱动程序、开发CUDA程序相关的开发工具包等。 Anaconda在安装Pytorch等会用到的CUDA的框架时…...
0725,进程间传递文件描述符,socketpair + sendmsg/recvmsg
我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎掉了我要碎…...
放大电路总结
补充: 只有直流移动时才有Rbe动态等效电阻 从RsUs看进去,实际上不管接了什么东西都能够看成是一个Ri(输入电阻) Ri Ui/Ii Rb//Rbe Ui/Us Ri/(RiRs) Aus (Uo/Ui)*(Ui/Us) Au *Ri/(RiRs) 当前面是一个电压源的信号 我们就需要输入电阻更大 Ro--->输出电阻--->将…...
深度学习1-简介
人工智能(AI)旨在打造模仿智能行为的系统。它覆盖了众多方法,涵盖了基于逻辑、搜索和概率推理的技术。机器学习是 AI 的一个分支,它通过对观测数据进行数学模型拟合来学习决策制定。这个领域近年来迅猛发展,现在几乎&a…...
Java基础语法 (基础介绍 二)
目录 Java 基础语法 第一个Java程序 基本语法 Java标识符 Java修饰符 Java变量 Java关键字 Java注释 Java 空行 Java 对象和类 Java中的对象 Java中的类 构造方法 创建对象 访问实例变量和方法 实例 源文件声明规则 Java包 Import语句 一个简单的例子 Java…...
SAPUI5基础知识18 - 自定义CSS和主题色
1. 背景 在上一篇博客中,我们通过使用SAPUI5提供的CSS类实现元素间距的调整。在本篇博客中,让我们看一下如何实现自定义的CSS样式。 2. 背景知识 2.1 CSS基础语法 CSS,全称为级联样式表(Cascading Style Sheets)&a…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...
go 里面的指针
指针 在 Go 中,指针(pointer)是一个变量的内存地址,就像 C 语言那样: a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10,通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...
LeetCode - 148. 排序链表
目录 题目 思路 基本情况检查 复杂度分析 执行示例 读者可能出的错误 正确的写法 题目 148. 排序链表 - 力扣(LeetCode) 思路 链表归并排序采用"分治"的策略,主要分为三个步骤: 分割:将链表从中间…...
Linux系统:进程间通信-匿名与命名管道
本节重点 匿名管道的概念与原理匿名管道的创建命名管道的概念与原理命名管道的创建两者的差异与联系命名管道实现EchoServer 一、管道 管道(Pipe)是一种进程间通信(IPC, Inter-Process Communication)机制,用于在不…...
