精华内容
下载资源
问答
  • 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 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

    2019-07-18 09:57:00
    //先排序,将左区间小的放在前面,然后如果前一个的右区间大于下一个的左区间,则可以合并,分别用两个下标指向当前的大区间和将要考察的小区间 class Solution { public int[][] merge(int[][] intervals) { if...

    //先排序,将左区间小的放在前面,然后如果前一个的右区间大于下一个的左区间,则可以合并,分别用两个下标指向当前的大区间和将要考察的小区间

    class Solution {
        public int[][] merge(int[][] intervals) {
            if(intervals.length<=1)
                return intervals;
            quickSort(intervals,0,intervals.length-1);
            int j=0;
            for(int i=0;i<intervals.length;i++)
            {
                if(intervals[j][1]>=intervals[i][0])
                {
                    intervals[j][1]=Math.max(intervals[j][1],intervals[i][1]);
                }
                else
                {
                    j++;
                    intervals[j][0]=intervals[i][0];
                    intervals[j][1]=intervals[i][1];
                }
            }
            int[][] res = Arrays.copyOfRange(intervals, 0, j+1);
            return res;
        }
        public void quickSort(int[][] arr,int l,int r)
        {
            if(l>=r)
                return ;
            int p=partition(arr,l,r);       //执行partition操作将数组分成两份
            quickSort(arr,l,p-1);
            quickSort(arr,p+1,r);
        }
        public int partition(int[][] arr,int l,int r)
        {
            int v=arr[l][0];
            int i=l;        //[l-i]为左半部分 初始为0,小于i的部分包括i
            for(int k=l+1;k<=r;k++)
            {
                if(arr[k][0]<v)
                {
                     swap(arr,k,i+1);
                     i++;
                }
              
            }
            swap(arr,l,i);
            return i;
        }
        public void swap(int[][] arr,int i,int j)
        {
            int temp=arr[i][0];
            arr[i][0]=arr[j][0];
            arr[j][0]=temp;
            int y=arr[i][1];
            arr[i][1]=arr[j][1];
            arr[j][1]=y;
        }
    }

    转载于:https://www.cnblogs.com/cold-windy/p/11205287.html

    展开全文
  • 给出一个区间的集合,请合并所有重叠的区间。 示例 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] 可被视为重叠区间。

    思路:

    先将给出的数组,对其按照start属性大小排序,然后当后者的start小于前者的end时,修改temp的start、end的值,否者result.add(temp).

    /**
     * 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) {
            List<Interval> result = new ArrayList<>();
    
            if (intervals.size() <= 0) {
                return result;
            }
            Collections.sort(intervals, new Comparator<Interval>() { //按照start属性升序排序
                @Override
                public int compare(Interval o1, Interval o2) {
                    return o1.start - o2.start;
                }
            });
            
            //这里用一个临时变量存储合并的interval
            Interval temp = intervals.get(0);
            for (int i = 1; i < intervals.size(); ++i) {
                if (intervals.get(i).start <= temp.end) {
                    temp = new Interval(temp.start, Math.max(temp.end,intervals.get(i).end));
                } else {
                    result.add(temp);
                    temp = intervals.get(i);
                }
            }
            result.add(temp);
            return result;
        }
    }

     

    转载于:https://www.cnblogs.com/yanhowever/p/10588764.html

    展开全文
  • 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]] 输出:...
  • 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],[4,5]]...
  • 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]...
  • 对于要进行合并的所有区间我们需要预处理排序一下 排序后我们遍历的时候判断前一个区间的右区间是否大于等于当前区间的左区间 1.如果大于等于取前一个右区间和当前右区间的最大值 2.如果小于则再放入list中一个新的...
  • leetcode56 合并区间

    2020-02-21 22:30:04
    合并区间 解题步骤: 首先对区间进行排序(排序按照区间开始端大小) 遍历区间,如果下一个区间的开始端小于当前区间的结束端,则两区间之间有overlap,将当前区间结束端调整为Math.max(curr_end, next_end) ...
  • 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: intervals = [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2: 输入: ...
  • 请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。 思路: 如果数组的长度为0或者1,则直接返回该数组 初始化count用于计数合并了多少次 遍历数组,相邻两个元素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]] 输出:...
  • LeetCode区间合并

    2017-08-09 16:39:00
    给定一组区间,将所有区间重叠的部分合并起来。 e.g. 给出 { [1, 3], [2, 6], [8, 10], [15, 18] },返回 { [1, 6], [8, 10], [15, 18] } 区间使用结构体(C++)或类(Java)表示 struct Interval { int ...
  • =后一个区间的左边界,则表示它们有重叠,进行合并。 注意:前一个区间的右边界可能>当前区间的右边界, 所以要Math.max(list.get(list.size()-1)[1],intervals[i][1]) 选较大值。 不然就会出现这样的错误↓ ...
  • 文章目录题目代码 题目 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] ... * @lc app=leetcode.cn id=56 lang=java * *
  • 给出一个区间的集合,请合并所有重叠的区间。 示例 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]]...
  • 题目解读:我们的目的是将多个区间,根据覆盖的情况,相互合并成多个大的区间。每一个数组只会有两种状态,一种是保持原样,一种是和其他的数组结合成一个大数组。 解题思路 : 我们目前没有一个很好的方法,可以...
  • 56. Merge Intervals合并区间题目描述Given a collection of intervals, merge all overlapping intervals.Example 1:Input: [[1,3],[2,6],[8,10],[15,18]]Output: [[1,6],[8,10],[15,18]]Explanation: Since ...
  • LeetCode.56 合并区间

    2021-02-03 16:38:49
    按照每个区间的起点进行排序,然后逐一比较合并 题解 package com.leetcode.code; import java.util.Arrays; import java.util.Comparator; /** * @ClassName Code56 * @Author ZK * @Description * @Date ...

空空如也

空空如也

1 2 3 4 5 6
收藏数 113
精华内容 45
关键字:

leetcode区间合并java

java 订阅