Archive for August 1st, 2013
- In: leetcode
- 3 Comments
尼玛这破题居然跑了好几遍才对！
一开始错的方法：
public int minDepth(TreeNode root) {
if (root == null)
return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return Math.min(left, right) + 1;
}
比如a#b这种左子树为空的树，我直接认为左子树的depth为0了，那当然左子树的depth小，然后parent直接取了0+1。问题在于，某个子树是null的时候，它不是叶子节点啊！这个时候就算没形成一个叶子到root的path，则认为depth为正无穷。改进：
public int minDepth(TreeNode root) {
if (root == null)
return Intger.MAX_VALUE;
if (root.left == null && root.right == null)
return 1; //说明是个leaf了！
int left = minDepth(root.left);
int right = minDepth(root.right);
return Math.min(left, right) + 1;
}
忍不住回忆为啥做maxdepth的时候就没遇见问题呢？（如下）因为求的是max，所以那种某个子树为0的情况就被Math.max给解决了。总之这种题最好做完了试一试，一试就能立刻看出毛病了，自己干想还真想不到。
public int maxDepth(TreeNode root) {
if (root == null)
return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
今天又被assign了不归我的活，怒了。干脆上班不工作了，直接刷题。
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [2,6],[1,3],[8,10],[15,18],
return [1,6],[8,10],[15,18].
思路：先sort by start，然后不断判断当前的interval能不能吞噬下一个(curr.end >= next.start，说明这两个能连起来）。做的过程中发现几个问题：
- 本来是想直接循环list，然后不断吞噬，删掉被吞噬的。但是这样就一边iterate一边modify array了，会挂。所以还得用另一个list，然后决定是不断删list2里的东西，还是不断往list2里加东西。这个要拿例子试试哪种好使。
- 一开始写的是if (curr.end >= next.start) then curr.end = next.end。然后挂了几个test case，才注意到忘记了curr本身包括了next的情况。应该是curr.next = Math.max(curr.end, next.end)
- 第一次写java inline的comparator!
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
});
ArrayList<Interval> result = new ArrayList<Interval>();
for (int i = 0; i < intervals.size(); i++) {
Interval curr = intervals.get(i);
while (i < intervals.size() - 1 && curr.end >= intervals.get(i + 1).start) {
curr.end = Math.max(curr.end, intervals.get(i + 1).end);
i++;
}//while出来说明curr已经吃饱了，可以加入result了。
result.add(curr);
}
return result;
}
Lexi's Leetcode solutions 