57. 插入区间(C++题解)
57. 插入区间
插入区间
给你一个无重叠的 ,按照区间起始端点排序的区间列表。
在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。
示例 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] 重叠。
示例 3:
输入:intervals = [], newInterval = [5,7]
输出:[[5,7]]
示例 4:
输入:intervals = [[1,5]], newInterval = [2,3]
输出:[[1,5]]
示例 5:
输入:intervals = [[1,5]], newInterval = [2,7]
输出:[[1,7]]
提示:
0 <= intervals.length <= 104
intervals[i].length = 2
0 <= intervals[i][0] <= intervals[i][1] <= 105
intervals 根据 intervals[i][0] 按 升序 排列
newInterval.length = 2
0 <= newInterval[0] <= newInterval[1] <= 105
思路
最开始的思路就是,先把新的区间按照起点的顺序插入到旧区间内,之后对所有区间进行判断,来将可以合并的区间合并起来。但是如果直接这样做的话,因为插入的时候需要将所有元素后移一位,而对于区间合并,每次合并后都需要删除一个元素,导致每次需要将所有元素前移一位,这样的在后面测试案例较大的时候是没法通过的。因此需要别的思路来解决这几个问题。 除此之外,还需要知道,有两个区间(a,b),(c,d),当发现c<b的时候,说明两个区间需要合并。并且合并后的区间是(a,max(b,d))。
解题方法
创建一个ans来保存最后的区间列表,第一步,将新的区间插入到旧区间内,这里采用,遍历旧区间intervals,通过判断newInterval的起点大小,把小于newInterval起点的区间放进ans中,当发现不满足的时候,就是该放入newInterval的位置了,这个时候就可以把newInterval加入ans中。这样就做到了将newInterval插入到旧区间内。 第二步,进行判断新插入的区间newInterval是否需要合并,与ans中最后一个区间进行判断(此时newInterval还没有插入ans中),如果需要合并那么直接合并就行了,也就不需要newInterval插入了。 第三步,在把新的区间newInterval放入(包括合并)后,就需要把intervals剩下的区间加入ans中了,不过在加入的时候需要进行判断,如果需要合并,那么直接合并。如果不需要合并,只需要加入剩下的区间了。 第四步,在第三步之前,考虑了一个特殊情况,也就是新区间是是放入最后一个位置,这个时候需要单独把newInterval放入ans后,并且判断是否需要合并。
复杂度
时间复杂度:
O(n)
空间复杂度:
O(n)
Code
class Solution {
public:vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {vector<vector<int>> ans;if(intervals.size()==0){intervals.push_back(newInterval);return intervals;}int i=0,k=0;//找到新区间应该放置在旧区间的位置for(;i<intervals.size();++i){if(newInterval[0]<=intervals[i][0]){if(i>0&&newInterval[0]<=intervals[i-1][1]){ans[i-1][1]=max(ans[i-1][1],newInterval[1]);k=i-1;}else{k=i;ans.push_back(newInterval);}break;}ans.push_back(intervals[i]);}//如果新的区间放在最后一个位置if(i==intervals.size()){if(newInterval[0]<=intervals[i-1][1]){ans[i-1][1]=max(ans[i-1][1],newInterval[1]);}else{ans.push_back(newInterval);}}//新的区间放在了旧区间中for(;i<intervals.size();++i){if(ans[k][1]>=intervals[i][0]){ans[k][1]=max(ans[k][1],intervals[i][1]);}else{ans.push_back(intervals[i]);}}return ans;}
};
相关文章:
57. 插入区间(C++题解)
57. 插入区间 插入区间 给你一个无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 示例 1: 输入&#x…...
【数据结构Java版】 初识泛型和包装类
目录 1.包装类 1.1基本数据类型以及它们所对应的包装类 1.2装箱和拆箱 1.3自动装箱和自动拆箱 2.什么是泛型 3.引出泛型 4.泛型类的使用 4.1语法 4.2示例 4.3类型推导 5.泛型是如何编译的 5.1擦除机制 5.2正确的写法 6.泛型的上届 6.1语法 6.2示例 …...
Spring中如何解决循环依赖问题的三种方法
什么是循环依赖问题 在 Spring 中,循环依赖问题指的是两个或多个 bean 之间相互依赖形成的闭环。具体而言,当 bean A 依赖于 bean B,同时 bean B 也依赖于 bean A,就形成了循环依赖。 循环依赖问题在 Spring 容器中是一个非常常…...
【ArcGIS Pro二次开发】(65):进出平衡SHP转TXT、TXT转SHP
最近一个小伙伴提了这么一个需求,需要把TXT和SHP进行互转。 这种TXT文件其实遇到了好几个版本,都有一点小差异。之前已经做过一个TXT转SHP的工具,但好像不适用。于是针对这个版本,做了互转的2个工具。 【SHP转TXT】 一、要实现的…...
Shell开发实践:服务器的磁盘、CPU、内存的占用监控
🏆作者简介,黑夜开发者,CSDN领军人物,全栈领域优质创作者✌,CSDN博客专家,阿里云社区专家博主,2023年6月CSDN上海赛道top4。 🏆数年电商行业从业经验,历任核心研发工程师…...
超详细 async和await 项目实战运用(附加文字解答+源码)
文章目录 问题描述async什么是 asyncasync 的作用async 的应用场景async 优点 await什么是 awaitawait 的作用await 的应用场景await 的优点async和 await结合使用 结束语 大家好!又到了愉快的周末假期,今天是2023年9月3日|农历七月十九,我最…...
Maven入门教程(三):Maven语法
视频教程:Maven保姆级教程 Maven入门教程(一):安装Maven环境 Maven入门教程(二):idea/Eclipse使用Maven Maven入门教程(三):Maven语法 Maven入门教程(四):Nexus私服 Maven入门教程(五):自定义脚手架 6.Mav…...
C++技术点,故事解析
语言的魅力 从人类诞生开始 ,南方古猿到现代人类经历了非常多变化; 南方古猿到能人 有什么变化? 能人会使用工具,由于会使用工具 就可以获得肉类食物,当然只能吃一些动物腐肉 直到进化成直立人的晚期,在东…...
数据结构(Java实现)-字符串常量池与通配符
字符串常量池 在Java程序中,类似于:1, 2, 3,3.14,“hello”等字面类型的常量经常频繁使用,为了使程序的运行速度更快、更节省内存,Java为8种基本数据类型和String类都提供了常量池。…...
python强化学习--gym安装与使用
最近开始学习强化学习,第一步肯定是要学会安装和使用pym,原本以为很简单,事实上确实很简单,但是遇到一个小问题,就是安装gym之后,在应用的过程中,游戏界面没有显示出来,了解后才知道…...
105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。 思路:题目给出了先序遍历和中序遍历的结果,因为先序遍历遵循根–>左–>…...
(第六天)初识Spring框架-SSM框架的学习与应用(Spring + Spring MVC + MyBatis)-Java EE企业级应用开发学习记录
SSM框架的学习与应用(Spring Spring MVC MyBatis)-Java EE企业级应用开发学习记录(第六天)初识Spring框架 昨天我们已经把Mybatis框架的基本知识全部学完,内容有Mybatis是一个半自动化的持久层ORM框架,深入学习编写动态SQL&a…...
如何使用『Nginx』配置后端『HTTPS』协议访问
前言 本篇博客主要讲解如何使用 Nginx 部署后端应用接口 SSL 证书,从而实现 HTTPS 协议访问接口(本文使用公网 IP 部署,读者可以自行替换为域名) 申请证书 须知 请在您的云服务平台申请 SSL 证书,一般来说证书期限…...
Git仓库简介
1、工作区、暂存区、仓库 工作区:电脑里能看到的目录。 暂存区:工作区有一个隐藏目录.git,是Git的版本库,Git的版本库里存了很多东西,其中最重要的就是称为stage(或者叫index)的暂存区…...
TensorRTC++ | INT8量化
Int8量化步骤 // 这是基本需要的组件 auto builder = make_nvshared(nvinfer1::createInferBuilder(logger)); auto config = make_nvshared(builder->createBuilderConfig())...
VS + qt环境使用QCustomPlot等三方库如何配置
文章目录 前言VS环境下引入第三方类库QCustomPlot方法一:解决办法: C中.dll与.lib文件的生成与使用1. 两种库:2.两种文件的区别 前言 Qt提供了显式和隐式导入第三方库方法,本文只介绍显示导入方法。 一般的第三方提供的库文件包…...
OS 段页结合的实际内存管理
虚拟内存承接段和页,从用户角度,虚拟内存提供段,从硬件角度,虚拟内存把段打散映射到页 先基于段的翻译,再基于页的翻译 p是pcb跟着进程换,64M一个段,set base就是建段表 因为每个进程虚拟地址…...
一种改进多旋翼无人机动态仿真的模块化仿真环境研究(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
02-请解释一下Java的内存模型和happens-before规则?【Java面试题总结】
请解释一下Java的内存模型和happens-before规则? 概念:Java内存模型,简称JMM,是一种定义了多线程程序中内存访问行为的规范。它定义了线程如何与主内存和工作内存进行交互,以及如何保证多线程程序的正确性和可见性。J…...
PVE 8 出现CPU 100% 冻结(卡死)
最近在研究PVE,然后下载官方最新版本系统8.x安装好后出现卡死问题,就连开个软件CPU也能飙到100%,开始我以为是硬件问题可能是资源不够,但是将系统切换回裸机(不用PVE启动)一点问题也没有,后来逐…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...
MySQL:分区的基本使用
目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区(Partitioning)是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分(分区)可以独立存储、管理和优化,…...
