Paste_Image.png
My code:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
/**
* 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; }
* }
*/
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
ArrayList<Interval> result = new ArrayList<Interval>();
if (intervals == null || intervals.size() == 0)
return result;
if (intervals.size() == 1) {
result.add(intervals.get(0));
return result;
}
int[] begin = new int[intervals.size()];
HashMap<Integer, Integer> range = new HashMap<Integer, Integer>();
range.put(intervals.get(0).start, intervals.get(0).end);
begin[0] = intervals.get(0).start;
for (int i = 1; i < intervals.size(); i++) {
begin[i] = intervals.get(i).start;
if (range.containsKey(intervals.get(i).start) && intervals.get(i).end <= range.get(begin[i]))
continue;
else
range.put(intervals.get(i).start, intervals.get(i).end);
}
Arrays.sort(begin);
Interval interval = new Interval(begin[0], range.get(begin[0]));
for (int i = 1; i <= begin.length; i++) {
if (i == begin.length)
result.add(interval);
else if (begin[i] > interval.end) {
result.add(interval);
interval = new Interval(begin[i], range.get(begin[i]));
}
else if (begin[i] < interval.start) {
if (range.get(begin[i]) <= range.get(begin[i - 1]))
interval = new Interval(begin[i], range.get(begin[i - 1]));
else
interval = new Interval(begin[i], range.get(begin[i]));
}
else if (range.get(begin[i]) > interval.end)
interval = new Interval(interval.start, range.get(begin[i]));
else
continue;
}
return result;
}
public static void main(String[] args) {
Solution test = new Solution();
Interval a0 = new Interval(1, 4);
Interval a1 = new Interval(1, 4);
ArrayList<Interval> result = new ArrayList<Interval>();
result.add(a0);
result.add(a1);
System.out.println(test.merge(result));
}
}
My test result:
Paste_Image.png
这道题目不算很难。一直在思考一个问题，如何保存这种范围的映射，这种start和end的映射。最后还是决定用HashMap， key -> start, value -> end.
将所有的数据保存在哈希表中，
同时，将所有的开头数字，保存在begin数组中。注意保存哈希表的时候，如果当前头在哈希表中已经存在的话，需要判断下其尾是否大于哈希表对应的val。如果不是，则跳过，如果是，则更新哈希表。
然后对 begin[] 排序。
然后按照一定的规则，处理这个数组，不断地插入新的interval到结果中去。
差不多就这样了。
**
总结： Array, sort, hash table
今天总算把三道题目的量完成了。中午和初中同学吃饭。突然明白了那么一句话。
我努力了这么久，就是为了和你喝一杯咖啡。
感觉他们的世界，和我的不同。他们对知识的掌握程度，也远高于我。但同样的，他们也需要考虑汽车在哪里买便宜。租的房子干不干净。这些他们也不能幸免。
然后，我要潜下心来，默默地，变强。
最后，希望选课顺利！
**
Anyway, Good luck, Richardo!
My code:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
/**
* 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; }
* }
*/
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
if (intervals == null || intervals.size() == 0)
return intervals;
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval o1, Interval o2) {
// int start1 = o1.start;
// int start2 = o2.start;
// int end1 = o1.end;
// int end2 = o2.end;
// if (start1 == start2 && end1 == end2)
// return 0;
// else if (start1 <= start2 && end1 <= end2)
// return -1;
// else
// return 1;
return o1.start - o2.start;
}
});
for (int i = 1; i < intervals.size(); i++) {
int frontStart = intervals.get(i - 1).start;
int frontEnd = intervals.get(i - 1).end;
int backStart = intervals.get(i).start;
int backEnd = intervals.get(i).end;
if (backStart > frontEnd)
continue;
else {
intervals.get(i - 1).start = Math.min(frontStart, backStart);
intervals.get(i - 1).end = Math.max(frontEnd, backEnd);
intervals.remove(i);
i--;
}
}
return intervals;
}
public static void main(String[] args) {
Interval a1 = new Interval(1, 3);
Interval a2 = new Interval(2, 5);
Interval a3 = new Interval(6, 7);
Interval a4 = new Interval(3, 4);
ArrayList<Interval> intervals = new ArrayList<Interval>();
intervals.add(a1);
intervals.add(a2);
intervals.add(a3);
intervals.add(a4);
Solution test = new Solution();
System.out.println(test.merge(intervals));
}
}
这是我自己写的，直接在里面改元素。
但是速度较慢。
为什么呢？
因为我有一个删除操作。链表的删除操作复杂度是O(n),所以如果测试案例的重合元素很多，我的速度会很慢很慢。
于是有了一个改进方法，就是新建一个ArrayList<...> ret,
然后把需要塞进去的，已经更新好了的interval放进去，这样就不会再有删除操作了。同样也是遍历整个链表。链表的.add()并不是很消耗时间的操作。我就懒得写了，但是速度应该会更快。
然后就出现了一个问题，以前从来没有碰到过：
Line 19: java.lang.IllegalArgumentException: Comparison method violates its general contract!
我查了下，大概是，
如果 A = B, 那么 B = A, 而我的comparator方法写得可能违背了这一点。
Collections.sort(intervals, new Comparator() {
public int compare(Object o1, Object o2) {
int start1 = ((Interval) o1).start;
int start2 = ((Interval) o2).start;
if (start1 <= start2)
return -1;
else
return 1;
}
});
这是那段错误的代码。我改了下，
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval o1, Interval o2) {
// int start1 = o1.start;
// int start2 = o2.start;
// int end1 = o1.end;
// int end2 = o2.end;
// if (start1 == start2 && end1 == end2)
// return 0;
// else if (start1 <= start2 && end1 <= end2)
// return -1;
// else
// return 1;
return o1.start - o2.start;
}
});
如果直接用注释的部分，是对的。用当前部分也是对的。
我还是不能很好地理解这个错误。等回了学校再仔细研究下。
然后我看了以前的做法，竟然可以用HashMap来做，也果真是巧妙！
我又自己重写了下，错了好几次才AC。思路和代码比之前要简洁很多。
但其实和我上面的版本差不多的。就是一个排序。一个用Comparator实现，一个用HashMap实现。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
/**
* 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; }
* }
*/
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
ArrayList<Interval> result = new ArrayList<Interval>();
if (intervals == null || intervals.size() == 0)
return result;
int[] begin = new int[intervals.size()];
HashMap<Integer, Integer> range = new HashMap<Integer, Integer>();
for (int i = 0; i < intervals.size(); i++) {
int start = intervals.get(i).start;
int end = intervals.get(i).end;
begin[i] = start;
if (range.containsKey(start) && range.get(start) >= end)
continue;
else
range.put(start, end);
}
Arrays.sort(begin);
result.add(new Interval(begin[0], range.get(begin[0])));
for (int i = 1; i < begin.length; i++) {
if (begin[i] == begin[i - 1])
continue;
else {
if (begin[i] > result.get(result.size() - 1).end)
result.add(new Interval(begin[i], range.get(begin[i])));
else
result.get(result.size() - 1).end = Math.max(result.get(result.size() - 1).end, range.get(begin[i]));
}
}
return result;
}
public static void main(String[] args) {
Solution test = new Solution();
Interval a0 = new Interval(2, 3);
Interval a1 = new Interval(4, 5);
Interval a2 = new Interval(6, 7);
Interval a3 = new Interval(8, 9);
Interval a4 = new Interval(1, 10);
ArrayList<Interval> result = new ArrayList<Interval>();
result.add(a0);
result.add(a1);
result.add(a2);
result.add(a3);
result.add(a4);
System.out.println(test.merge(result));
}
}
**
记住了，链表的remove操作很费时间，决定性浪费时间！
能不用就不用把！
还有一个comparator 问题没有搞清楚！
**
Anyway, Good luck, Richardo!
More efficient solution:
My code:
/**
* 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; }
* }
*/
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
ArrayList<Interval> ret = new ArrayList<Interval>();
if (intervals == null || intervals.size() == 0)
return ret;
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval o1, Interval o2) {
return o1.start - o2.start;
}
});
Interval preInterval = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
Interval curr = intervals.get(i);
if (curr.start > preInterval.end) {
ret.add(preInterval);
preInterval = curr;
}
else {
Interval merge = new Interval(preInterval.start, Math.max(preInterval.end, curr.end));
preInterval = merge;
}
}
ret.add(preInterval);
return ret;
}
}
Anyway, Good luck, Richardo!
My code:
/**
* 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; }
* }
*/
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
List<Interval> ret = new ArrayList<Interval>();
if (intervals == null || intervals.size() == 0) {
return ret;
}
ret.add(intervals.get(0));
for (int i = 1; i < intervals.size(); i++) {
Interval curr = intervals.get(i);
int j = ret.size() - 1;
for (; j >= 0; j--) {
Interval cmp = ret.get(j);
if (cmp.end < curr.start) {
ret.add(j + 1, curr);
break;
}
else if (cmp.start <= curr.start) {
cmp.end = Math.max(cmp.end, curr.end);
break;
}
else if (cmp.start <= curr.end) {
cmp.start = curr.start;
cmp.end = Math.max(cmp.end, curr.end);
curr = cmp;
ret.remove(j);
}
else {
continue;
}
}
if (j < 0) {
ret.add(0, curr);
}
}
return ret;
}
}
自己写了出来。应该是 Insert sort 的一种变形。
注意地方是，如果在向左遍历途中，更新了一个Interval导致他的start变小了，那么很有可能这个interval会覆盖他前面一个interval。这个时候就要把当前Interval从链表里面删除掉。然后更新curr指针。让他和下一个interval再次进行比较。
list remove 操作。一般情况下，时间复杂度是O(n)
如果删的是头部或者尾部，时间复杂度是O(1)
以前的那个用HashMap实现sort的方法也是很有意思的。
Anyway, Good luck, Richardo! -- 09/02/2016
