Java - LeetCode面试经典150题(三)
区间
228. 汇总区间
题目
给定一个 无重复元素 的 有序 整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说,nums 的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出:
"a->b" ,如果 a != b
"a" ,如果 a == b
提示:
0 <= nums.length <= 20
-2^31 <= nums[i] <= 2^31 - 1
nums 中的所有值都 互不相同
nums 按升序排列
示例 1:
输入:nums = [0,1,2,4,5,7]
输出:["0->2","4->5","7"]
解释:区间范围是:
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"
示例 2:
输入:nums = [0,2,3,4,6,8,9]
输出:["0","2->4","6","8->9"]
解释:区间范围是:
[0,0] --> "0"
[2,4] --> "2->4"
[6,6] --> "6"
[8,9] --> "8->9"
解析:
因为是有序数组,直接按照题意模拟即可。
遍历数组,连续则继续;不连续就断开,记录。
代码:
class Solution {public List<String> summaryRanges(int[] nums) {int n=nums.length;boolean flag=false;int l=-1,r=-1;ArrayList<String> ans = new ArrayList<>();for (int i=0;i<n;i++){if (!flag) {l=nums[i];r=l;flag=true;}else{if (nums[i]==nums[i-1]+1){r=nums[i];}else{if (l==r) ans.add(r+"");else ans.add(l+"->"+r);i--;flag=false;}}}if (flag) {if (l==r) ans.add(r+"");else ans.add(l+"->"+r);}return ans;}
}
56. 合并区间
题目
以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。
请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
提示:
1 <= intervals.length <= 1e4
intervals[i].length == 2
0 <= starti <= endi <= 1e4
示例 1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。
解析:
首先先对二维数组进行排序,按照左端点从小到大排序;
之后,就是判断上个区间的右端点和下个区间的左端点是否能接上,能接上就说明是同一个区间的,继续遍历;否则就断开,将上个区间的左端点和右端点记录在答案中;
之后就是处理其他问题,如判断最后的一块区间是否已经在答案中,答案的格式转化等。
代码:
class Solution {public int[][] merge(int[][] intervals) {int n=intervals.length;Arrays.sort(intervals,(a,b)->{if (a[0]!=b[0]) return a[0]-b[0];return a[1]-b[1];});int l=-1,r=-1,l1=-1,r1=-1;ArrayList<List<Integer>> res = new ArrayList<>();for (int i=0;i<n;i++){int a=intervals[i][0],b=intervals[i][1];if (r<a){if (l==-1){l=a;r=b;}else{res.add(List.of(l,r));l1=l;r1=r;l=a;r=b;}}else {r=Math.max(r,b);}}if (r1!=r){res.add(List.of(l,r));}int[][] ans= new int[res.size()][];for (int i=0;i<res.size();i++){var k=res.get(i);ans[i]=new int[k.size()];for (int j=0;j<k.size();j++){ans[i][j]=k.get(j);}}
// for (int i=0;i<res.size();i++){
// for (int j=0;j<2;j++) System.out.print(ans[i][j]+" ");
// System.out.println();
// }return ans;}
}
57. 插入区间
题目
给你一个 无重叠的 ,按照区间起始端点排序的区间列表 intervals,其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束,并且 intervals 按照 starti 升序排列。
同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
在 intervals 中插入区间 newInterval,使得 intervals 依然按照 starti 升序排列,且区间之间不重叠(如果有必要的话,可以合并区间)。
返回插入之后的 intervals。
注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
提示:
0 <= intervals.length <= 1e4
intervals[i].length == 2
0 <= starti <= endi <= 1e5
intervals 根据 starti 按 升序 排列
newInterval.length == 2
0 <= start <= end <= 1e5
示例 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种情况。假设newInterval的值是l和r。
遍历数组时,数组的右端点小于l,说明数组第i区间与[l,r]无重叠;
之后,可能会出现l>intervals[i][1]的情况,根据这种情况,有判断好几种可能性,部分重叠,完全覆盖,不重叠。但是有一个共同特点,如果有覆盖的地方,那么r一定在第i区间的左端点的右边(可以相等)!!此时判断一下,判断成功就更新l和r,继续遍历;
直到r小于一个区间的左端点,此时后续的空间就跟[l,r]无关了。
代码:
class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {List<int[]> ans = new ArrayList<>();int l=newInterval[0],r=newInterval[1];int n=intervals.length;boolean flag=true;for (int i=0;i<n;i++){if (!flag) {int[] a=new int[2];a=intervals[i];ans.add(a);continue; }if (l>intervals[i][1]){int[] a=new int[2];a=intervals[i];ans.add(a);continue;}if (r>=intervals[i][0]){l=Math.min(l,intervals[i][0]);r=Math.max(r,intervals[i][1]);continue;}int[] a={l,r};ans.add(a);flag=false;i--;}if (flag){int[] a={l,r};ans.add(a);}return ans.toArray(new int[ans.size()][]);}
}
452. 用最少数量的箭引爆气球
题目
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭,若有一个气球的直径的开始和结束坐标为 xstart,xend, 且满足 xstart ≤ x ≤ xend,则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后,可以无限地前进。
给你一个数组 points ,返回引爆所有气球所必须射出的 最小 弓箭数 。
提示:
1 <= points.length <= 1e5
points[i].length == 2
-2^31 <= xstart < xend <= 2^31 - 1
示例 1:
输入:points = [[10,16],[2,8],[1,6],[7,12]]
输出:2
解释:气球可以用2支箭来爆破:
-在x = 6处射出箭,击破气球[2,8]和[1,6]。
-在x = 11处发射箭,击破气球[10,16]和[7,12]。
示例 2:
输入:points = [[1,2],[3,4],[5,6],[7,8]]
输出:4
解释:每个气球需要射出一支箭,总共需要4支箭。
示例 3:
输入:points = [[1,2],[2,3],[3,4],[4,5]]
输出:2
解释:气球可以用2支箭来爆破:
- 在x = 2处发射箭,击破气球[1,2]和[2,3]。
- 在x = 4处射出箭,击破气球[3,4]和[4,5]。
解析:
这是个贪心题,按照左端点从小到大排好序后,观察区间的特点,就可以发现如果上个区间的右端点比这个区间的左端点大(可以相等),这两个区间就可以被一条箭引爆,左端点就没有考虑的必要了,都排序好了。之后,就是将上个区间右端点不断更新,和这个区间的左端点不断地比较,直到不合法了,就结束上一个区间,将现在的区间作为新的“起点” !
但有一个问题,就是将数组排序的问题,有点坑人!因为数据范围,进行比较时,不能在int的类型下进行做差比较,可能会出现溢出的情况。所以可以转化为Long型做差比较,或者Integer.compare()方法进行比较。
代码:
class Solution {public int findMinArrowShots(int[][] points) {int n=points.length;Arrays.sort(points,(s1,s2)->{if (s1[0]!=s2[0])return Integer.compare(s1[0], s2[0]);return Integer.compare(s1[1], s2[1]);});int l=-1,r=-1;int cnt=0;for (int i=0;i<n;i++){if (i==0){cnt++;r=points[i][1];continue;}if (r>=points[i][0]){r=Math.min(r,points[i][1]);}else{cnt++;r=points[i][1];}}return cnt;}
}
相关文章:
Java - LeetCode面试经典150题(三)
区间 228. 汇总区间 题目 给定一个 无重复元素 的 有序 整数数组 nums 。 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说,nums 的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于 nums 的数字 x 。 列表中…...

基于SpringBoot+Vue+MySQL的民宿预订平台
系统展示 用户前台界面 管理员后台界面 商家后台界面 系统背景 随着旅游业的蓬勃发展,民宿作为一种独特的住宿方式,受到了越来越多游客的青睐。然而,传统的民宿预定方式往往存在信息不对称、效率低下等问题,难以满足游客的个性化需…...
Hadoop krb5.conf 配置详解
krb5.conf文件是Kerberos认证系统中的一个关键配置文件,它包含了Kerberos的配置信息,如KDC(Key Distribution Centers)和Kerberos相关域的管理员服务器位置、当前域和Kerberos应用的默认设置、以及主机名与Kerberos域的映射等。以…...
工程师 - DNS请求过程
DNS(Domain Name System,域名系统)是互联网的重要基础设施之一,其主要功能是将人们容易记忆的域名(例如 www.example.com)转换为计算机能识别的IP地址(例如 192.0.2.1),类…...
Solidity智能合约中的事件和日志
1. Solidity 中的事件和日志概述 1.1 什么是事件? 在 Solidity 中,事件(Event)是一种允许智能合约与外部世界进行通信的机制。通过触发事件,可以记录合约执行中的关键操作,并将这些操作发送到链上。事件的…...
第四十一篇-Docker安装Neo4j
创建目录 mkdir /opt/neo4j-data创建 docker run \ -d --name neo4j \ -p 7474:7474 -p 7687:7687 \ -v /opt/neo4j-data/data:/data \ -v /opt/neo4j-data/logs:/logs \ -v /opt/neo4j-data//conf:/var/lib/neo4j/conf \ -v /opt/neo4j-data/plugins:/plugins \ --env NEO4J…...

数电基础(组合逻辑电路+Proteus)
1.组合逻辑电路 1.1组合逻辑电路的分析 1.1.1组合逻辑电路的定义 组合逻辑电路的定义 (1)对于一个逻辑电路,其输出状态在任何时刻只取决于同一时刻的输入状态,而与电路的原来状态无关,这种电路被定义为组合逻辑电路…...

自给自足:手搓了一个睡眠监测仪,用着怎么样?
很久不分享手搓党作品拉! 今天分享一个“基于毫米波雷达的睡眠监测仪”作品! 用Air700E开发板毫米波雷达,手搓一个开箱即用的睡眠监测仪,不花冤枉钱! 来仔细瞧瞧! 一、项目原理及硬件制作 毫米波是指频率…...

Miniforge详细安装教程(macOs和Windows)
(注:主要是解决商业应用anaconda收费问题,这是轻量级的代替,个人完全可以使用anaconda和miniconda) Miniforge 是一个轻量级的包管理器,类似于 Anaconda 和 Miniconda。它主要用于安装基于 conda 的 Python 环境,专注于…...
HDFS Shell作业1
1.在HDFS上建立/user/stu/自己学号,和/user/stu/input目录。 命令: hdfs dfs -mkdir -p /user/stu/22 hdfs dfs -mkdir /user/stu/input 2.用两种不同的方法上传albums.csv至HDFS的学号目录和input目录中。 命令: hdfs dfs -put par…...

工业交换机一键重启的好处
在当今高度自动化和智能化的工业环境中,工业交换机作为网络系统中至关重要的一环,其稳定性和可靠性直接影响到整个生产过程的顺利进行。为了更好地维护这些设备的健康运行,一键重启功能应运而生,并呈现出诸多显著的好处。 首先&am…...
滚雪球学Oracle[4.2讲]:PL/SQL基础语法
全文目录: 前言一、PL/SQL基础语法1.1 变量声明变量声明示例: 二、记录类型与集合类型的使用2.1 记录类型记录类型的定义与使用 2.2 集合类型 三、PL/SQL表与关联数组3.1 PL/SQL表(嵌套表)嵌套表的定义与使用 3.2 关联数组关联数组…...

springboot系列--web相关知识探索二
一、映射 指的是与请求处理方法关联的URL路径,通过在Spring MVC的控制器类(使用RestController注解修饰的类)上使用注解(如 RequestMapping、GetMapping)来指定请求映射路径,可以将不同的HTTP请求映射到相应…...

Oracle 12c在Windows环境下安装
适合初学者使用的Oracle 12c在Windows环境下安装步骤、参数配置、常见问题及参数调优的详细补充说明。 一、Oracle 12c安装步骤 1. 准备工作 在安装Oracle 12c之前,确保你的系统满足以下要求: 操作系统:Oracle 12c支持的Windows版本包括Wi…...

Stable Diffusion绘画 | 来训练属于自己的模型:打标处理与优化
上一篇完成的打标工作,是为了获取提示词,让AI认识和学习图片的特征。 因此,合适、恰当、无误的提示词,对最终模型效果是相当重要的。 Tag 如何优化 通过软件自动生成的 Tag 只是起到快速建立大体架构的作用,里面会涉…...

【论文笔记】Visual Instruction Tuning
🍎个人主页:小嗷犬的个人主页 🍊个人网站:小嗷犬的技术小站 🥭个人信条:为天地立心,为生民立命,为往圣继绝学,为万世开太平。 基本信息 标题: Visual Instruction Tunin…...

ubuntu 设置静态IP
一、 ip addresssudo nano /etc/netplan/50-cloud-init.yaml 修改前: 修改后: # This file is generated from information provided by the datasource. Changes # to it will not persist across an instance reboot. To disable cloud-inits # ne…...

Java 每日一刊(第19期):泛型
文章目录 前言1. 泛型概述1.1 不使用泛型 vs 使用泛型1.2 泛型的作用 2. 泛型的基本语法2.1 定义带类型参数的泛型类2.2 使用泛型类2.3 泛型方法 3. 泛型类型推断与钻石操作符3.1 类型推断3.2 钻石操作符 4. 通配符的使用4.1 无界通配符 <?>4.2 上界通配符 <? exten…...

windows下安装rabbitMQ并开通管理界面和允许远程访问
如题,在windows下安装一个rabbitMQ server;然后用浏览器访问其管理界面;由于rabbitMQ的默认账号guest默认只能本机访问,因此需要设置允许其他机器远程访问。这跟mysql的思路很像,默认只能本地访问,要远程访…...

深度剖析音频剪辑免费工具的特色与优势
是热爱生活的伙伴或者想要记录美好声音的普通用户,都可能会需要对音频进行剪辑处理。而幸运的是,现在有许多优秀的音频剪辑软件提供了免费版本,让我们能够轻松地施展音频剪辑的魔法。接下来,就让我们一同深入了解这些音频剪辑免费…...

Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...

DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
Xen Server服务器释放磁盘空间
disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...

uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...