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

Leetcode Hot 100刷题记录 -Day10（合并区间）

article 2024/11/15 19:35:31

合并区间

问题描述：

以数组 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] 可被视为重叠区间。
解题思路：

56. 合并区间 - 力扣（LeetCode）https://leetcode.cn/problems/merge-intervals/solutions/203562/he-bing-qu-jian-by-leetcode-solution/?envType=study-plan-v2&envId=top-100-liked

//提交版
class Solution {
    public int[][] merge(int[][] intervals) {
         if(intervals.length == 0)
            return new int[0][0];
        //Arrays.sort为给数组排序
        //new Comparator<int[]>()：自定义排序方式
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override//重写方法标签
            public int compare(int[] o1, int[] o2) {
                //比较两个二维数组的左端点，若是o1[0]>o2[0],则返回正直，否则返回负值或者0
                //完成二维数组排序
                return o1[0] - o2[0];
            }
        });
        //创建一个空列表
        List<int[]> merged = new ArrayList<>();
        for (int i =0 ; i<intervals.length;i++){
            //用L和R分别存储二维数组的左右端点
            int L = intervals[i][0];
            int 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()][]);
}
}


//带有输入输出版
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class hot11_merge {
    public int[][] merge(int[][] intervals){
        //二维数组为空，返回空列表
        if(intervals.length == 0)
            return new int[0][0];
        //Arrays.sort为给数组排序
        //new Comparator<int[]>()：自定义排序方式
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override//重写方法标签
            public int compare(int[] o1, int[] o2) {
                //比较两个二维数组的左端点，若是o1[0]>o2[0],则返回正直，否则返回负值或者0
                //完成二维数组排序
                return o1[0] - o2[0];
            }
        });
        //创建一个空列表
        List<int[]> merged = new ArrayList<>();
        for (int i =0 ; i<intervals.length;i++){
            //用L和R分别存储二维数组的左右端点
            int L = intervals[i][0];
            int 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()][]);
    }

    public static void main(String[] args){
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
        //deepToString:将二维数组转换为字符串
        System.out.println("输入:" + Arrays.deepToString(intervals));
        hot11_merge hot11Merge = new hot11_merge();
        int[][] result = hot11Merge.merge(intervals);
        System.out.println("输出：" + Arrays.deepToString(result));
    }
}

知识点总结：

重写排序方式的函数：

Arrays.sort(intervals, new Comparator<int[]>() { @Override//重写方法标签
public int compare(int[] o1, int[] o2)

return }

deepToString：将二维数组转换为字符串

查看全文

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