Dx's Tech Notes

2._合并区间

6 min read

  • 2.25
    • 等于时也合并，如果发生了合并，则存储 current，来继续合并后面的
    • 末尾记得添加 current（需要最后手动添加
    • 拿着一个区间到处去“吃”别人，等确定再也吃不下去了，才把它收录进结果集。所以最后手里捏着的那个区间，因为循环结束了，没机会触发收录动作，必须在循环外手动加一次。
class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new ArrayList<>();
 
        Arrays.sort(intervals,(a,b)->(a[0]-b[0]));
 
        int[] current = intervals[0];
        for(int i=1;i<intervals.length;i++){
            if(current[1]>=intervals[i][0]){
                current[1] = Math.max(current[1],intervals[i][1]);
            }else{
                res.add(current);
                current = intervals[i];
            }
 
        }
        res.add(current);
        return res.toArray(new int[res.size()][]);
    }
}

  • 2.7

    • 修改的是 current 的右边界（对比 current 和 now 的右边界谁大）
    • 将 current 添加到 List 后是引用状态，在 for 循环修改 current 的右边界时，是可以牵连到 list 中的
    • 返回 list 的《 int【】》变为 int【】时，先将 list 变为 Array，在指定大小。Arrays 与 collections 总结中有

  • 1.23

    • current 和 now 一一对比，看情况更新 current
    • 比较器比较小集合的第一个元素

  • 1.12

    • 其实和下面的代码一样
    • 中等偏上难度，第一次有点没头绪
    • 排序后，合并区间
    • 需要新建一个 res 的 list《int【】》列表，存储每个序列
    • 之后放入第一个序列，for 循环第二个序列开始比较头尾
    • 最后用到 list 的 toArray 的 API

（不需要最后手动添加）

  • 遇到新区间，先直接挂在结果集上。然后拿着这个挂在墙上的区间去对比，能合并就直接把墙上这个区间的尾巴拉长。所以无论循环什么时候结束，所有的区间都已经挂在墙上了，绝对不会漏掉最后一个。
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);
 
        List<int[]> res = new ArrayList<>();
        int[] current = intervals[0];
        res.add(current);
        for(int i=1;i<intervals.length;i++){
            int[] next = intervals[i];
            if(next[0]<=current[1]){
                current[1] = Math.max(next[1],current[1]);
            }else{
                current = next;
                res.add(current);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}
  • 先排序
  • 再合并区间

//如果当前区间的 起点 ≤ 上一个合并区间的 终点 //newEnd = max(当前区间.end, 上一个区间.end)

如果要实现第一个元素为锚点的升序，用(a,b) -> b[0]-a[0])

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(a,b) -> a[0]-b[0]);
            // if (compare(a, b) < 0) {
            //     // a 应排在 b 前面
            // } else {
            //     // a 应排在 b 后面   
        //}   
//         如果你想让“小的在前面”，就返回负数；
//         如果想让“大”的在前面”，就返回正数（或者把减号反过来）
        List<int[]> res = new ArrayList<>();
        int[] current = intervals[0];
        res.add(current);
        for(int i = 1;i<intervals.length;i++){
            int[] next = intervals[i];
            //如果当前区间的 起点 ≤ 上一个合并区间的 终点
            //newEnd = max(当前区间.end, 上一个区间.end)
            if(next[0]<=current[1]){
                current[1] = Math.max(current[1],next[1]);
            }else{
                current = next;
                res.add(current);
            }
        }
        //List<int[]> → int[][]
        return res.toArray(new int[res.size()][]);
    }
}

1. 过去：痛苦的“匿名内部类”写法 (Java 7 及以前)

在以前，如果你想自定义排序，必须规规矩矩地写一个 Comparator（比较器）对象。代码长得像一座大山：

Java

// Java 7 的老写法：极其冗长
Arrays.sort(intervals, new Comparator<int[]>() {
    @Override
    public int compare(int[] a, int[] b) {
        return a[0] - b[0];
    }
});

你看，为了表达一句核心的 a[0] - b[0]，我们被迫写了 5 行的“废话”代码（创建对象、重写方法等）。

2. 变革：Lambda 表达式的诞生 (Java 8)

Java 的设计者觉得上面的写法太蠢了。既然 Comparator 接口里只有一个 compare 方法，那何必写那么多样板代码呢？

于是，Lambda 表达式诞生了。它的核心思想就是**“去伪存真，只留核心”**。

Java 编译器变得非常聪明，它会做以下自动推导：

  1. 它知道 Arrays.sort 的第二个参数需要一个比较器。

  2. 它知道你要比较的元素类型是 int[]（整型数组）。

  3. 它知道比较器里唯一需要你实现的方法接收两个参数，并返回一个 int。

既然编译器全都知道，那你只需要告诉它**“参数是什么”和“怎么算”**就行了。

3. 语法大解剖：(a, b) -> a[0] - b[0]

这行代码被分成了三个部分：

  • (a, b)：输入参数。

    • 编译器会自动推导出 a 和 b 的类型是 int[]。你连类型声明都省了。

  • ->：Lambda 箭头符号。

    • 读作 “goes to” 或 “变成了”，它是一座桥梁，把左边的输入传给右边的处理逻辑。

  • a[0] - b[0]：函数体（返回值）。

    • 这里甚至省去了 {} 和 return 关键字。因为只有一行代码，Java 允许你直接写结果，它会自动帮你 return。

Graph View

Backlinks