精华内容
下载资源
问答
  • leetcode 合并区间 java

    2019-11-07 20:52:48
    给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2: 输入: [[1,4],[4,5]] 输出:...

    题干

    给出一个区间的集合,请合并所有重叠的区间。

    示例 1:

    输入: [[1,3],[2,6],[8,10],[15,18]]
    输出: [[1,6],[8,10],[15,18]]
    解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
    示例 2:

    输入: [[1,4],[4,5]]
    输出: [[1,5]]
    解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

    想法

    最暴力的做法就是每一个数组都比较一下,但是这种想法过于愚蠢,相信聪明的你都完全不会考虑的。
    我们可以假设,如果输入的数组是排好序的,就会变得很简单。
    好,我们按照每个数组的第一个元素来进行排序:
    这样前一个数组的第一个数一定小于后一个数组的第一个数
    如果:
    前一个数组的第二个数大于等于后一个数组的第一个数,那么这两个集合就有交集。
    并集的左边界为前一个数组的第一个数,右边界为第一个数组的第二个数和第二个数组的大的那个。
    直接讲我的代码,参考了https://blog.csdn.net/HaleyDong/article/details/90489902
    他的讲解也很清楚,但是 它的代码是错的,错在了判断合并条件那一步。

    官方解答

    https://leetcode-cn.com/problems/merge-intervals/solution/he-bing-qu-jian-by-leetcode/

    java代码

    class Solution {
        public int[][] merge(int[][] intervals) {
           List <int[]> res=new ArrayList<>();
            if(intervals==null){//判断空
                return res.toArray(new int[0][]);
            }
            Arrays.sort(intervals,(a,b)->a[0]-b[0]);
            int i=0;
            int left=0;//左边界
            int right=0;//右边界
            while(i<intervals.length){
             left=intervals[i][0];//为每个数组的第一个
               right=intervals[i][1];//为每个数组的第二个
                while(i<intervals.length-1&&right>=intervals[i+1][0]){//后一个的第一个必须小于之前的有边界
                    i++;
                    right=Math.max(right,intervals[i][1]);//右边界更新为两个数组第二个数中的大的
                }
                res.add(new int[]{left,right});//加到数组
                    i++;
            }
            return res.toArray(new int[0][]);
        }
    }
    

    leetcode上最快的代码:思路差不多,数据结构更简练

    class Solution {
        public int[][] merge(int[][] intervals) {
            if(intervals == null || intervals.length<=1){
                return intervals;
            }
            int mergeCount = 0;
            for(int i = 0;i<intervals.length;i++){
                for(int j = i+1;j<intervals.length;j++){
                    if(intervals[i][1]>=intervals[j][0] && intervals[i][0]<=intervals[j][1]){
                        if(intervals[i][1]>intervals[j][1]){
                            intervals[j][1] = intervals[i][1];
                        }
                        if(intervals[i][0]<intervals[j][0]){
                            intervals[j][0] = intervals[i][0];
                        }
                        intervals[i] = null;
                        mergeCount++;
                        break;
                    }
                }
            }
            int[][] result = new int[intervals.length-mergeCount][];
            for(int i = 0,j = 0;j<intervals.length;j++){
                if(intervals[j] != null){
                    result[i++] =intervals[j];
                }
            }
            return result;
        }
    }
    

    总结

    这道题的官方解答是更新题目之前的,所以我这个应该是写的最全的

    展开全文
  • leetcode 合并区间 java(新操作)

    千次阅读 2019-05-23 23:07:58
    给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例2: 输入: [[1,4],[4,5]]...

    给出一个区间的集合,请合并所有重叠的区间。

    示例 1:

    输入: [[1,3],[2,6],[8,10],[15,18]]
    输出: [[1,6],[8,10],[15,18]]
    解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
    

    示例 2:

    输入: [[1,4],[4,5]]
    输出: [[1,5]]
    解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间

    参考:

    https://leetcode-cn.com/problems/merge-intervals/solution/pai-xu-by-powcai

    这道题很好理解,但有些操作我第一次见,所以这里直接copy了参考里的代码。

    思路:

    1. 首先将数组按照每个内层[ , ]的第一个元素升序排列。

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

      这句代码这样理解:

          将interval按照(a, b) -> a[0] - b[0]这个规则来排序。

          而这个规则是,a和b分别代表一个[ , ],a[0]和b[0]分别代表[ , ]的第一个值。

              当a[0] - b[0]>0,相当于交换二者的位置;

              当a[0] - b[0]=0,不做实际操作;

              当a[0] - b[0]<0,相当于没有操作。

    2. 比如相邻的数组a[1,4]和b[2,5],当我们发现a[1]>b[0]时,两个数组表示的范围存在重合,数组的左值一定是a[0](更小的值做范围起点),而右值则为a[1] b[1]二者中更大的值。

     

    最后解释一下res.toArray(new int[0][]);

    toArray(T)方法,T参数表示将res按照T模板转换,new int[0][]用最少的内存提供了二维数组模板。

    还有改成return res.toArray(new int[5][]);后输出错误:

    输入

    [[1,3],[2,6],[8,10],[15,18]]

    输出

    [[1,6],[8,10],[15,18],null,null]

     

    成功

    显示详情

    执行用时 : 81 ms, 在Merge Intervals的Java提交中击败了27.25% 的用户

    内存消耗 : 45.2 MB, 在Merge Intervals的Java提交中击败了50.10% 的用户

    class Solution {
        public int[][] merge(int[][] intervals) {
            List<int[]> res = new ArrayList<>();
            if (intervals.length == 0 || intervals == null) return res.toArray(new int[0][]);
            Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
            int i = 0;
            while (i < intervals.length) {
                int left = intervals[i][0];
                int right = intervals[i][1];
                //可以用连续的不止两个数组重合,所以用while循环
                while (i < intervals.length - 1 && intervals[i][0] <= right) {
                    i++;
                    right = Math.max(right, intervals[i][1]);
                }
                res.add(new int[]{left, right});
                i++;
            }
            return res.toArray(new int[0][]);
        }
    }

     

    展开全文
  • 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2: 输入: [[1,4],[4,5]] 输出...

    LeetCode56. 合并区间

    给出一个区间的集合,请合并所有重叠的区间。

    示例 1:

    输入: [[1,3],[2,6],[8,10],[15,18]]
    输出: [[1,6],[8,10],[15,18]]
    解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
    

    示例 2:

    输入: [[1,4],[4,5]]
    输出: [[1,5]]
    解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
    

    解题思路:

    这个题目其实代码比较好理解,难点是其中有几个关于集合的api方法需要好好熟悉一下。具体看下面的代码:

    class Solution {
        public int[][] merge(int[][] intervals) {
            if(intervals==null || intervals.length==0) return new int[][]{};
            //保存的结果集
            List<int[]> result=new ArrayList<>();
            //将原集合进行排序
            Arrays.sort(intervals,(a,b)->(a[0]-b[0]));
            int currentA=intervals[0][0];
            int currentB=intervals[0][1];
            for(int i=1;i<intervals.length;i++){
            //两个单独的没有重叠的话,直接加入结果集
                if(currentB<intervals[i][0]){
                    result.add(new int[]{currentA,currentB});
                    currentA=intervals[i][0];
                    currentB=intervals[i][1];
                }
                else{
                    //两个结合有重叠的地方
                    currentB=Math.max(currentB,intervals[i][1]);
                }
            }
            //下面这一步骤很重要,就是当所有的集合都有重复的交集元素的时候,左后需要将currentA和currentB加入到结果集里面
            result.add(new int[]{currentA,currentB});
            int[][] returnResult=new int[result.size()][2];
            //集合转数组
            result.toArray(returnResult);
            //注意转换到的结果是到括号里的数组里面
            return returnResult;
        }
    }
    
    展开全文
  • Leetcode 56 合并区间 涉及到重写compare 记录一下 /** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int ...

    Leetcode 56 合并区间


    涉及到重写compare 记录一下

    /**
     * Definition for an interval.
     * public class Interval {
     *     int start;
     *     int end;
     *     Interval() { start = 0; end = 0; }
     *     Interval(int s, int e) { start = s; end = e; }
     * }
     */
    class Solution {
        public List<Interval> merge(List<Interval> intervals) {
            ArrayList<Interval>arr=new ArrayList<Interval>();
            if(intervals.size()<=1) return intervals;
            Collections.sort(intervals,new Comparator<Interval>(){
               public int compare(Interval i1,Interval i2)
               {
                   return i1.start-i2.start;
               }
            });
            Interval inter=new Interval();//获取第一个
            inter.start=intervals.get(0).start;
            inter.end=intervals.get(0).end;
            for(int i=1;i<intervals.size();i++)
            {
                if(intervals.get(i).start<=inter.end)
                {
                    if(intervals.get(i).end>inter.end)
                    {
                        inter.end=intervals.get(i).end;
                    } 
                }                              
                else 
                {
                    Interval res=new Interval();//获取第一个
                    res.start=inter.start;
                    res.end=inter.end;
                    arr.add(res);
                    inter.start=intervals.get(i).start;
                    inter.end=intervals.get(i).end;
                }
            }
            arr.add(inter);
            return arr;
            
        }
    }
    
    展开全文
  • leetcode 56 合并区间 Java o(n)解法

    千次阅读 2018-11-13 17:31:46
    给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2: 输入: [[1,4],[4,5]] 输出:...
  • =后一个区间的左边界,则表示它们有重叠,进行合并。 注意:前一个区间的右边界可能>当前区间的右边界, 所以要Math.max(list.get(list.size()-1)[1],intervals[i][1]) 选较大值。 不然就会出现这样的错误↓ ...
  • 经验:区间类的问题,一般而言是需要画图思考的。因为只有建立直观的感觉,才能更有效的去思考解决问题的方案。 还有需要画图思考的相关算法问题有(其实绝大部分都需要打草稿,大神除外): 和物理现象相关的:第 ...
  • LeetCode 56. 合并区间

    千次阅读 多人点赞 2020-04-16 13:32:50
    合并区间 难度 中等 ## 题目 给出一个区间的集合,请合并所有重叠的区间。 **示例 1:** ``` 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为...
  • Java实现 LeetCode 56 合并区间

    万次阅读 多人点赞 2020-02-15 18:11:28
    56. 合并区间 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2: 输入: [[1,4]...
  • LeetCode第56题:合并区间Java实现)

    千次阅读 2019-05-27 14:38:50
    给出一个区间的集合,请合并所有重叠的区间。 示例 示例1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例2: 输入: [[1,4],[4,5]]...
  • 合并区间,从官方给的示例可以看出合并的条件是将区间重合部分合并。 首先我们先将二维数组进行左端点升序排列,使得我们在判断是否重合时只需要判断右端点即可。 右端点判断是否可以合并的条件: 当第一个数组的...
  • 对于要进行合并的所有区间我们需要预处理排序一下 排序后我们遍历的时候判断前一个区间的右区间是否大于等于当前区间的左区间 1.如果大于等于取前一个右区间和当前右区间的最大值 2.如果小于则再放入list中一个新的...
  • 请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。 (二)解题思路 这道题把自己给绕晕了,因为做题之前没认真考虑合并区间涉及的各种因素,所以后面编写的代码就需要进行...
  • leetcode 56合并区间 java

    2019-07-18 09:57:00
    //先排序,将左区间小的放在前面,然后如果前一个的右区间大于下一个的左区间,则可以合并,分别用两个下标指向当前的大区间和将要考察的小区间 class Solution { public int[][] merge(int[][] intervals) { if...
  • 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例2: 输入: [[1,4],[4,5]...
  • https://leetcode-cn.com/problems/minimum-cost-to-merge-stones/ 文章目录分析区间动态规划三部曲 分析 这道题是一道经典的区间dp问题,旨在通过动态规划去求一个区间的最优解,通过将大区间划分为很多个小区间,...
  • 文章目录题目代码 题目 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] ... * @lc app=leetcode.cn id=56 lang=java * *
  • LeetCode 56 合并区间

    2019-08-23 16:31:33
    // LeetCode 56 合并区间 // 二维排序,依次取出区间进行比较,O(nlogn))复杂度 class Solution { public int[][] merge(int[][] intervals) { int n = intervals.length; if (n == 0) return new int[0][0]; ....
  • 合并区间做题博客链接题目链接描述示例初始代码模板代码 做题博客链接 https://blog.csdn.net/qq_43349112/article/details/108542248 题目链接 https://leetcode-cn.com/problems/merge-intervals/ 描述 以数组 ...
  • 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2: 输入: [[1,4],[4,5]] 输出...
  • 将给出的区间集合进行排序,将其左闭区间按照从小到大的顺序进行排列; 设置一个list集合,进行遍历和判断: 将能合并的进行合并,再add进list中; 不能合并的就直接add进list中; 将最终得到的list利用toArray方法...
  • 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2: 输入: [[1,4],[4,5]] 输出...
  • 给出一个区间的集合,请合并所有重叠的区间。 示例1 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例2 输入: [[1,4],[4,5]] 输出: ...
  • Leetcode027--插入区间

    2017-01-25 22:03:19
    将小的区间合并到大的区间中

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,082
精华内容 832
关键字:

leetcode区间合并java

java 订阅