5.11号刷题

第一题 56 Merge Intervals

算法

先将全部的start进行排序，然后查看每一个的start和end，如果满足相连的要求。就在result中插入新的结果。

public class mergeintervals56 {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals.size() <= 0) {
            return intervals;
        }

//        Collections.sort(intervals, new Comparator<Interval>(){
//            @Override
//            public int compare(Interval obj0, Interval obj1) {
//                return obj0.start - obj1.start;
//            }
//        });

        intervals.sort((i1, i2) -> Integer.compare(i1.start, i2.start));

        List<Interval> result = new LinkedList<>();
        int begin = intervals.get(0).start;
        int end = intervals.get(0).end;

        for (Interval interval : intervals) {
            if (interval.start <= end) {
                end = Math.max(end, interval.end);
            } else {
                result.add(new Interval(begin, end));
                begin = interval.start;
                end = interval.end;
            }
        }

        result.add(new Interval(begin, end));
        return result;
    }
    public class Interval {
    int start;
    int end;
    Interval() { start = 0; end = 0; }
    Interval(int s, int e) { start = s; end = e; }
    }
}

学到的东西

关于Java List 的常见用法:

• add(Object object)
  在集合末尾加入元素
  参数 object ： 要添加的值(Object类型)
  例如 list.add(“abc”); 向原集合末尾添加新元素值为”abc”
• add(int index, Object object)
  在集合中指定位置插入指定元素。如果插入位置本身已经元素那么从这个位置开始(包括原元素)自动向后移位，对应的索引依次加1
  参数 index: 索引 ， object: 要添加的值(Object类型)
  例如集合中已有”a”,”b”,”c”三个元素索引分别对应 0 , 1 ,2 ，这时在第1个位置加入”d” ，list.add(0, “d”);
  这时集合就变成了”d”,”a”,”b”,”c”， 原”a，b, c”对应的索引就从”0 ,1, 2” 就变成了 “1 ,2, 3”
• remove(int index)
  从集合中删除指定位置的元素
  参数 index： 目标元素的索引(最小从0开始)
  例如 list.remove(1)， 删除索引为1的元素
• remove(Object object)
  从集合中删除指定值的元素
  参数 object： 目标元素的值
  例如： list.remove(“hello”); 表示从集合中删除值为”hello”的元素， 如果多个元素具有相同的值则优先删除索引小的元素
• size()
  返回当前集合列表的元素总数量， 返回值： int类型

List中根据Object的类型进行排序

• 方法一，java7之前利用collections 进行排序

  Collections.sort(OBJECT, Comparator<Interval>(){
       @Override
       public int compare(OBJECT obj0, OBJECT obj1) {
            return obj0.start - obj1.start;
       }
  });

• 方法二，你用java8进行排序

  interval.sort((i1, i2) -> (i1.start, i2.start))