当前位置: 首页 > news >正文

LeetCode56.合并区间

这道题我想了一会儿,实在想不到比较好的算法,只能硬着头皮写了,然后不断的debug,经过我不懈的努力,最后还是AC,不过效率确实低。

我就是按照最直接的方法来,先把intervals数组按照第一个数start来排序,这个是通过定义一个sort方法用冒泡排序实现的,然后用一个List<int[]>来装答案,先把intervals[0]放进答案,用index表示list中最新放入的那个答案的索引(ans.get(index)),然后从i=1开始遍历intervals[i],因为我这个intervals是排过序的,所以后面的intervals[i]的start一定大于等于前面的intervals[i]的start,但是如果intervals[i][0]比最新放入答案的intervals[i][1](ans.get(index)[1])还小,说明intervals[i][0]应该在刚放入的最新答案(ans.get(index))的区间之中,所以我们要去更改那个最新的答案(ans.get(index))的end,把ans.get(index)[1]改为当前元素的end和他自己的end的最大值,这样就可以确保区间无重叠且完整,以下是我的代码:

class Solution {public int[][] merge(int[][] intervals) {int n = intervals.length;int index =-1;sort(intervals);List<int[]> ans = new ArrayList<int[]>();ans.add(intervals[0]);index++;for(int i=1;i<n;i++){if(intervals[i][0] <= ans.get(index)[1]){ans.get(index)[1] = Math.max(ans.get(index)[1],  intervals[i][1]);}else{ans.add(intervals[i]);index++;}}int size = ans.size();int[][] res = new int[size][2];for(int i=0;i<size;i++){res[i] = ans.get(i);}return res;}public void sort(int[][] intervals){int n = intervals.length;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++){if(intervals[i][0] > intervals[j][0]){int[] tmp = new int[]{intervals[i][0], intervals[i][1]};intervals[i][0] =intervals[j][0];intervals[i][1] = intervals[j][1];intervals[j][0] = tmp[0];intervals[j][1]=tmp[1];}}}}
}

一看题解我都惊了,我去,和我的想法一摸一样,我还以为我这种方法很low,原来这是官方解法,以下是题解代码:

class Solution {public int[][] merge(int[][] intervals) {if (intervals.length == 0) {return new int[0][2];}Arrays.sort(intervals, new Comparator<int[]>() {public int compare(int[] interval1, int[] interval2) {return interval1[0] - interval2[0];}});List<int[]> merged = new ArrayList<int[]>();for (int i = 0; i < intervals.length; ++i) {int L = intervals[i][0], R = intervals[i][1];if (merged.size() == 0 || merged.get(merged.size() - 1)[1] < L) {merged.add(new int[]{L, R});} else {merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], R);}}return merged.toArray(new int[merged.size()][]);}
}

原理和我的算法是一模一样的,不一样的是他没有自己定义排序方法而是用了Array.sort()方法,然后重写compare()方法,比较数组中第一个元素也就是strat就可以,然后他也没用index来记录刚放进去的最新答案,而是通过merged.get(merged.size()-1)来获得这个刚放进去的最新答案。

相关文章:

LeetCode56.合并区间

这道题我想了一会儿&#xff0c;实在想不到比较好的算法&#xff0c;只能硬着头皮写了&#xff0c;然后不断的debug&#xff0c;经过我不懈的努力&#xff0c;最后还是AC&#xff0c;不过效率确实低。 我就是按照最直接的方法来&#xff0c;先把intervals数组按照第一个数star…...

【内推码:NTAMW6c】 MAXIEYE智驾科技2024校招启动啦

MAXIEYE智驾科技2024校招启动啦【内推码&#xff1a;NTAMW6c】 【招聘岗位超多&#xff01;&#xff01;公司食堂好吃&#xff01;&#xff01;】 算法类&#xff1a;感知算法工程师、SLAM算法工程师、规划控制算法工程师、目标及控制算法工程师、后处理算法工程师 软件类&a…...

Python框架【模板继承 、继承模板实战、类视图 、类视图的好处 、类视图使用场景、基于调度方法的类视图】(四)

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是爱敲代码的小王&#xff0c;CSDN博客博主,Python小白 &#x1f4d5;系列专栏&#xff1a;python入门到实战、Python爬虫开发、Python办公自动化、Python数据分析、Python前后端开发 &#x1f4e7;如果文章知识点有错误…...

对于前端模块化的理解与总结(很全乎)

目录 模块化的好处 模块化的commonJS导入导出 暴露(导出)模块&#xff1a;module.exports value或exports.xxx value 导入模块——使用 es6模块化 方法一逐个导出 方法二默认导出 方法三 方法四 方法五 export 和import 同时存在 多个文件导出到一个文件后在相关文件…...

NewStarCTF 2022 web方向题解 wp

----------WEEK1---------- BUU NewStarCTF 公开赛赛道 WEEK1 [NotPHP] 先看题目&#xff0c;要传参加绕过。 分析一下代码&#xff1a;首先get一个datadata://test/plain,Wel…。然后key1和2用数组可以绕过。num2077a可以绕过弱类型。eval()中的php语句被#注释了&#xff0c…...

WebGL矩阵变换库

目录 矩阵变换库&#xff1a; Matrix4对象所支持的方法和属性如表所示&#xff1a; 方法属性规范&#xff1a; 虽然平移、旋转、缩放等变换操作都可以用一个44的矩阵表示&#xff0c;但是在写WebGL程序的时候&#xff0c;手动计算每个矩阵很耗费时间。为了简化编程&#xf…...

block层:8. deadline调度器

deadline 源码基于5.10 0. 私有数据 struct deadline_data {/** run time data*//** requests (deadline_rq s) are present on both sort_list and fifo_list*/struct rb_root sort_list[2];struct list_head fifo_list[2];/** next in sort order. read, write or both ar…...

DTO,VO,PO的意义与他们之间的转换

DTO&#xff08;Data Transfer Object&#xff09;&#xff1a;数据传输对象&#xff0c;这个概念来源于J2EE的设计模式&#xff0c;原来的目的是为了EJB的分布式应用提供粗粒度的数据实体&#xff0c;以减少分布式调用的次数&#xff0c;从而提高分布式调用的性能和降低网络负…...

Java 集合框架2

一、关于set接口的常用类 1.HashSet类 用来处理无序的单列数据&#xff0c;没有重复的元素,重复的元素算一个 i.构造方法 //HashSet类是set接口的子类&#xff0c;是无序的单列数据&#xff0c;没有重复的元素&#xff0c;重复的元素算一个 //HashSet的构造方法 //HashSet() …...

2024王道408数据结构P144 T16

2024王道408数据结构P144 T16 思考过程 首先看题目&#xff0c;要求我们把二叉树的叶子结点求出来并且用链表的方式存储&#xff0c;链接时用叶结点的右指针来存放单链表指针。我们很清楚可以看出来能用中序遍历递归的方式实现&#xff0c;因为第一个叶子结点在整棵树的最左下…...

【ARM Coresight 系列文章 22 -- linux frace 与 trace-cmd】

文章目录 ftrace 介绍trace-cmd 介绍trace-cmd 常用跟踪事件ftrace 与 trace-cmd 关系ftrace 编译依赖 ftrace 介绍 ftrace 是 Linux 内核中的一个跟踪工具&#xff0c;主要用于帮助开发者分析和调试内核的行为。ftrace 的名字来源于 “function tracer”&#xff0c;它最初是…...

MyBatis的一级缓存和二级缓存是怎么样的?

目录 1. 一级缓存 2. 一级缓存失效的几种情况 3. 二级缓存 4.二级缓存失效的情况 5. 二级缓存的相关配置 6. 缓存的查询顺序 MyBatis 的缓存共分为一级缓存和二级缓存。 1. 一级缓存 一级缓存是 SqlSession 级别的&#xff0c;通过同一个 SqlSession 查询到的数据会被缓…...

下载的文件被Windows 11 安全中心自动删除

今天从CSDN上下载了自己曾经上传的文件&#xff0c;但是浏览器下载完之后文件被Windows安全中心自动删除&#xff0c;说是带病毒。实际是没有病毒的&#xff0c;再说了即便有病毒也不应该直接删除啊&#xff0c;至少给用户一个保留或删除的选项。 研究了一番&#xff0c;可以暂…...

【Java List与数组】List<T>数组和数组List<T>的区别(124)

List数组&#xff1a;存储List的数组&#xff0c;即&#xff1a;数组中的元素是&#xff1a;List&#xff1b; 数组List&#xff1a;存储数组的List&#xff0c;即&#xff1a;List中的数据是类型的数组&#xff1b; 测试案例&#xff1a; import java.util.ArrayList; impor…...

Nuxt 菜鸟入门学习笔记四:静态资源

文章目录 public 目录assets 目录全局样式导入 Nuxt 官网地址&#xff1a; https://nuxt.com/ Nuxt 使用以下两个目录来处理 CSS、fonts 和图片等静态资源&#xff1a; public 目录 public 目录用作静态资产的公共服务器&#xff0c;可通过应用程序定义的 URL 公开获取。 换…...

C语言 - 结构体、结构体数组、结构体指针和结构体嵌套

结构体的意义 问题&#xff1a;学籍管理需要每个学生的下列数据&#xff1a;学号、姓名、性别、年龄、分数&#xff0c;请用 C 语言程序存储并处理一组学生的学籍。 单个学生学籍的数据结构&#xff1a; 学号&#xff08;num&#xff09;&#xff1a; int 型姓名&#xff08;…...

python安装playwright问题记录

python安装playwright这个时候,有得时候会https timeout 有的时候会 not found。 我最后使用的方法三&#xff0c;挺好用的。 PyPI The Python Package Index 可以尝试使用的方法 1. 更换pip源&#xff1a;使用国内的pip源可以提高下载速度并减少超时问题。例如&#xff0c…...

关于gRPC微服务利弊之谈

gRPC微服务架构包括以下几个主要组件&#xff1a; 服务定义&#xff1a;定义服务的接口和消息格式&#xff0c;使用Protocol Buffers或其他的消息格式进行描述。服务实现&#xff1a;实现定义的服务接口和消息处理逻辑。服务器端实现&#xff1a;在服务器端&#xff0c;需要实…...

【Terraform学习】使用 Terraform创建Lambda函数启动EC2(Terraform-AWS最佳实战学习)

本站以分享各种运维经验和运维所需要的技能为主 《python》&#xff1a;python零基础入门学习 《shell》&#xff1a;shell学习 《terraform》持续更新中&#xff1a;terraform_Aws学习零基础入门到最佳实战 《k8》暂未更新 《docker学习》暂未更新 《ceph学习》ceph日常问题解…...

Mac软件删除方法?如何删除不会有残留

Mac电脑如果有太多无用的应用程序&#xff0c;很有可能会拖垮Mac系统的运行速度。因此&#xff0c;卸载电脑中无用的软件是优化Mac系统运行速度的最佳方式之一。Mac卸载应用程序的方式是和Windows有很大的区别&#xff0c;特别对于Mac新用户来说&#xff0c;如何无残留的卸载删…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

Python第七周作业

Python第七周作业 文章目录 Python第七周作业 1.使用open以只读模式打开文件data.txt&#xff0c;并逐行打印内容 2.使用pathlib模块获取当前脚本的绝对路径&#xff0c;并创建logs目录&#xff08;若不存在&#xff09; 3.递归遍历目录data&#xff0c;输出所有.csv文件的路径…...

数据库管理与高可用-MySQL故障排查与生产环境优化

目录 #1.1MySQL单案例故障排查 1.1.1MySQL常见的故障排查 1.1.2MySQL主从故障排查 #2.1MySQL优化 2.1.1硬件方面的优化 2.1.2进程方面的优化 #3.1MySQL存储引擎 3.1.1 MyISAM存储引擎 3.1.2 InnoDB存储引擎 1.1MySQL单案例故障排查 1.1.1MySQL常见的故障排查 &#xff08;1&…...