Lexi's Leetcode solutions

Posts Tagged ‘easy

就是merge sort那个n-way merge,轮流出牌。这个题的重点是要用heap,这样每次新加一个元素的时侯能很快的找到新的min。还有,这是第一次真的implement priority queue,需要自己写comparator(小于号说明是MinHeap)。

public ListNode mergeKLists(ArrayList<ListNode> lists) {
  ListNode result = null;
  ListNode curr = result;
  Comparator<ListNode> comp = new Comparator<ListNode>() {
    public int compare(ListNode a, ListNode b) {
      return a.val - b.val;
    }
  };
  PriorityQueue<ListNode> minHeap = new PriorityQueue<ListNode>(lists.size(), comp);
  for (int i = 0; i < lists.size(); i++) {
    ListNode currHead = lists.get(i);
    if (currHead != null)
      minHeap.add(currHead);
  }
  while (!minHeap.isEmpty()) {
    ListNode smallest = minHeap.poll();
    if (result == null) {
      result = smallest;
      curr = result;
    } else {
      curr.next = smallest;
      curr = curr.next;
    }
    ListNode nextEnqueue = smallest.next;
    if (nextEnqueue != null)
      minHeap.add(nextEnqueue);
  }
  return result;
}
Tags: ,

今天又被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,说明这两个能连起来)。做的过程中发现几个问题:

  1. 本来是想直接循环list,然后不断吞噬,删掉被吞噬的。但是这样就一边iterate一边modify array了,会挂。所以还得用另一个list,然后决定是不断删list2里的东西,还是不断往list2里加东西。这个要拿例子试试哪种好使。
  2. 一开始写的是if (curr.end >= next.start) then curr.end = next.end。然后挂了几个test case,才注意到忘记了curr本身包括了next的情况。应该是curr.next = Math.max(curr.end, next.end)
  3. 第一次写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;
}
Tags: , ,