lc56. 合并区间-编程思维

题目来源于力扣题库,题目链接:LC56.合并区间

Q:以数组 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 <= 104
  intervals[i].length == 2
  0 <= starti <= endi <= 104

A:思路:

  第一步,排序。排序是为了使得相邻的区间尽可能的挨着,为了后续的左或右边界的比较,这里根据左边界或右边界进行排序都可,笔者这里按照左边界进行升序排序。
  第二步,比较。将intervals[0]作为一个初始基准,从第二个开始比较,记start为待放入结果集的初始左边界,即start = intervals[0][0],同理待放入结果集的右边界为end = intervals[0][1];
  接着,从intervals[i](i∈[1, intervals.length - 1])开始跟前一个区间进行比较,假设i = 1,也就是说intervals[1]和intervals[0]进行比较,观察一下两个区间[start, end] 和[intervals[1][0], intervals[1][1]],它们是排序后的,故一定有start < intervals[1][0],也就是说待放入结果集的左边界一定是确定的,也就是start;
  那么如何待放入结果集的右边界呢?
  由于end和intervals[1][0]的大小关系是不确定的,可大可小,所以此时就分为了两种情况:
  若intervals[1][0] > end,表示不会出现重合区间,直接将[start, end]加入结果集即可,并更新下一次的start和end。
  若intervals[1][0] < end,表示会出现重合,则更新end即可。
  循环至终,也要记得将最后的[start, end]加入结果集。

  以下是Java代码,仅供参考:

 

package algo;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

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

        if(intervals.length == 1) return intervals; // 如果题目给出的二维数组长度为1,则不需要合并,直接返回intervals

        Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0])); // 现将多个区间按照其左边界排序,这样可以简化问题

        List<int[]> res = new LinkedList<>();
        int start = intervals[0][0];
        int end = intervals[0][1];

        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] > end){ // 不重合,说明该区间不需要与后面的区间进行比较了,即其为结果之一,加入结果集即可
                res.add(new int[]{start, end}); // 加入当前的 [start, end] 区间
                start = intervals[i][0]; // 更新start
                end = intervals[i][1]; // 更新end
            }else{
                end = Math.max(end, intervals[i][1]); // 重合,更新右边界
            }
        }
        res.add(new int[]{start, end});
        return res.toArray(new int[res.size()][]);
    }


    /* 测试 */
    public static void main(String[] args) {
        mergeSolution_56 solution_56 = new mergeSolution_56();
        int[][] intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
        int[][] answer = solution_56.merge(intervals);
        for (int[] is : answer) {
            System.out.println(Arrays.toString(is));
        }
    }
}

 

版权声明:本文版权归作者所有,遵循 CC 4.0 BY-SA 许可协议, 转载请注明原文链接
https://www.cnblogs.com/fxy0715/p/17444491.html

lc15. 三数之和-编程思维

 题目来源于力扣题库,题目链接:LC15. 三数之和 Q:给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请 你返回所有和为 0

lc1171. 从链表中删去总和值为零的连续节点-编程思维

题目来源于力扣题库,题目链接:LC1171.从链表中删去总和值为零的连续节点 Q:给你一个链表的头节点 head,请你编写代码,反复删去链表中由 总和 值为 0 的连续节点组成的序列,直到不存在这样的序列为止。 删除完毕后,请你返回最终结果链表的头节点。  你可以返回任何满足题目要求的答案。 (注意,下面示例中的所有序