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

LeetCode hot 100 每日一题(10)——56. 合并区间

这是一道难度为中等的题目,我们来看看题目描述:

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间


示例 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] 可被视为重叠区间。


提示:

  • 1 <= intervals.length <= 1 0 4 10^4 104
  • intervals[i].length == 2
  • 0 <= s t a r t i start_i starti <= endi <= 1 0 4 10^4 104

说人话解释:

求重叠的区间并集,然后返回所有的并集

题解

class Solution {

    public int[][] merge(int[][] intervals) {

        // 创建LinkedList存储合并后的空间,方便在尾部插入和删除元素

        LinkedList<int[]> res = new LinkedList<>();

        // 按照区间的起点进行排序

        Arrays.sort(intervals, (a, b) -> {return a[0] - b[0];});

        //先将第一个区间加入结果列表

        res.add(intervals[0]);

        //遍历剩下的所有区间,所以从i = 1开始

        for(int i = 1; i < intervals.length; i++){
  
            int[] curr = intervals[i]; // 当前遍历的区间,是列表

            int[] last = res.getLast(); // 获取结果列表中的最后一个区间


            // 如果当前区间起点小于或等于上一个区间的终点,说明区间有重叠

            if(curr[0] <= last[1]){

                // 更新结果列表中的最后一个区间的终点

                last[1] = Math.max(last[1], curr[1]);

            }else{

                // 如果没有重叠,直接将当前区间加入列表

                res.add(curr);

            }

        }

        //将LinkedList转换为二维数组返回

        return res.toArray(new int[1][1]);

    }

}

问题与解答

[NOTE] 问题1
Arrays.sort(intervals, (a, b) -> {return a[0] - b[0];});(a, b) -> {return a[0] - b[0];}这是什么用法?
解答:
(a, b) -> {return a[0] - b[0];}Lambda 表达式,用于 Java 8 及以上版本的简洁写法,相当于实现 Comparator<int[]> 接口的 compare 方法。
其作用是按照数组 intervals 的第一个元素(即起点 start_i)进行升序排序
等价于:

Arrays.sort(intervals, new Comparator<int[]>() {
   @Override
   public int compare(int[] a, int[] b) {
       return a[0] - b[0];
   }
});
  • a[0] - b[0] 返回负数(a[0] < b[0]),则 a 排在 b 前面;
  • a[0] - b[0] 返回正数(a[0] > b[0]),则 b 排在 a 前面;
  • a[0] - b[0] 返回 0,则 ab 位置不变(即视为相等)。

[NOTE] 问题2
int[] curr = intervals[i]; // 当前遍历的区间,是列表
int[] last = res.getLast(); // 获取结果列表中的最后一个区间
这里取出来的是列表还是数组?形如[i, j]的是列表还是数组?
curr[0]是当前区间的起点,curr[1]是当前区间的终点吗?
last[0]是结果列表中最后一个区间的起点,last[1]是结果列表中最后一个区间的终点吗?
解答:
取出的是数组,不是列表。这里 currlast 都是 int[] 类型的数组,表示一个区间 [start, end]。形如 [i, j] 的数据结构是 int[] 数组,而不是 List Java 里没有像 Python 那样的列表(list),int[] 是固定大小的数组,而 List<int[]> 则是存储多个 int[] 的动态集合。
在 Java 中,数组(Array) 和 列表(List,通常指 ArrayList) 是两种常见的数据结构

  • 数组(Array):大小是固定的,创建后不能更改长度。可以存储基本数据类型(如 intdouble) 也可以存储对象类型。
  • 列表(List):大小是动态的,可以根据需求增删元素。只能存储对象类型ArrayList<int> 不合法,必须使用 ArrayList<Integer>)。


    curr[0]curr[1] 代表当前区间的起点和终点。
    last[0]last[1] 代表 res 结果列表中最后一个区间的起点和终点

[NOTE] 问题3
res.toArray(new int[1][1]);中的toArray用法是什么?
解答:

  • res.toArray(new int[0][0]) 用于将 LinkedList<int[]> res 转换为 二维数组 int[][]

  • toArray() 方法作用

    • toArray(new int[0][0]) 方式可以将 LinkedList<int[]> 直接转换为 int[][] 数组。
    • 由于 resLinkedList<int[]>,需要转换为 int[][] 返回,因此 toArray() 适用于数组转换。

    等价于:

int[][] result = new int[res.size()][2];
for (int i = 0; i < res.size(); i++) {
   result[i] = res.get(i);
}
return result;

为什么用 new int[0][0]

  • 由于 toArray(T[] a) 需要传入一个 相同类型的数组,但不需要指定大小(JVM 会自动调整大小)。
  • new int[0][0] 只是一个占位符,toArray 会创建合适大小的 int[][] 并返回。

[NOTE] 问题4
LinkedList<int[]> res = new LinkedList<>();创建的是什么数据结构?是双链表LinkedList吗?
解答:
双向链表 LinkedListLinkedList<int[]> 代表一个 存储 int[] 数组的双向链表。

  • LinkedList<int[]> res = new LinkedList<>();
    • LinkedList<> 是 Java 的 双向链表实现,允许快速插入和删除元素。
    • 这里 res 存储的是 int[] 类型的数组,即每个元素都是形如 [start, end] 的区间。
  • 为什么用 LinkedList 而不是 ArrayList
    • LinkedListgetLast() 方法可以快速获取最后一个元素
    • 插入新区间的操作更快,因为 LinkedList 直接修改指针,而 ArrayList 可能需要扩容和移动数据。

http://www.kler.cn/a/589956.html

相关文章:

  • 【VSCode】VSCode常用插件
  • 合成复用原则
  • 云原生函数计算:无服务器架构的基因重组
  • Flask+Vue-Router+JWT实现登录验证
  • [网络] socket编程--udp_echo_server
  • 【自学笔记】Redis基础知识点总览-持续更新
  • 在本地跑通spark环境
  • 程序化广告行业(22/89):腾讯广告业务布局与广告效果评估基础
  • 无再暴露源站!群联AI云防护IP隐匿方案+防绕过实战
  • coding ability 展开第四幕(滑动指针——巩固篇)超详细!!!!
  • 【华为OD-E卷 - 字符统计及重排 100分(python、java、c++、js、c)】
  • jmeter 循环控制器遍历列表中的数据
  • 20250317笔记本电脑在ubuntu22.04下使用acpi命令查看电池电量
  • test skills
  • 【数据分析】数据筛选与访问行列元素3
  • 2020年蓝桥杯第十一届CC++大学B组(第二次)真题及代码
  • 从被动响应到主动防御——IT 应急演练平台 v3.0.1 重构企业安全免疫系统
  • RPC是啥?
  • 图论part3|101.孤岛的总面积、沉没孤岛、417. 太平洋大西洋水流问题
  • Vue3项目匹配PC端和移动端---一套组件