当前位置: 首页 > 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;如何无残留的卸载删…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...