Lexi's Leetcode solutions

Archive for October 8th, 2013

subset 1:  array本身都是distinct number,所以往里一个一个插不用担心重复。{}, 放第一个,放第二个。。

//inintialize a {}, keep inserting, mark as used (distinct nums)
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
    Arrays.sort(S);
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    result.add(new ArrayList<Integer>());
    for (int i = 0; i < S.length; i++) {
        ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>();
        for (ArrayList<Integer> prevSubset : result) {
            ArrayList<Integer> newSubset = new ArrayList<Integer>();
            newSubset.addAll(prevSubset);
            newSubset.add(S[i]);
            temp.add(newSubset);
        }
        result.addAll(temp);
    }
    return result;
}

subset 2————————————-
先sort,然后往后加。重点是怎么保证不重复?比如array[] = {1, 2, 2}

  1. {}
  2. {}, {1}
  3. {}, {1}, {2}, {12}
  4. {}, {1}, {2}, {12} 这时要是还往{}和{1}里面插2就会产生重复。所以要想办法把他们skip过去。skip到哪为止呢?毕竟还是想往{2}和{12}里插的。
  5. 所以是arr[i] == arr[i + 1]的时候,不要往arr[i]之前那一层插了。要往i这一层新插的里面插。
public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
  Arrays.sort(num);
  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    result.add(new ArrayList<Integer>());
  int start = 0;
  for (int i = 0; i < num.length; i++) {
    int prevSize = result.size();
    //上一层的size,是数字可以用来循环,避免modification exception
    for (int j = start; j < prevSize; j++) {
      ArrayList<Integer> newSubset = new ArrayList<Integer>();
      newSubset.addAll(result.get(j));
      newSubset.add(num[i]);
      result.add(newSubset);
    }
    if (i + 1 < num.length && num[i] == num[i + 1])
      start = prevSize;
      //i + 1那层越过i - 1这层的所有subsets,因为第i层已经往i - 1层的所有subsets里插过了
    else
      start = 0;
  }
  return result;
}
Advertisements

倒是20分钟写出来了bugfree,比较喜欢这种利用data structure的题,感觉试一试总能想出来。

这个题就是基本BFS,要点是生成新节点的同时,怎么把新节点和其他新节点连起来呢?这就需要一个新旧节点对应map,每次生成新节点A’,要把dequeue的这个parent B对应的新节点B’和当前作为child的新节点A’连起来。注意单向连就行了(B’->A)’,因为下次把A当作root的时候,还会经历B作为child,这时再A’->B’。

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
  if (node == null)
    return null;
  Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>(); 
  Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
  enqueueAndClone(q, node, map);
  while (!q.isEmpty()) {
    UndirectedGraphNode parent = q.poll();
    for (UndirectedGraphNode child : parent.neighbors) {
      if (!map.containsKey(child))
        enqueueAndClone(q, child, map);
      map.get(parent).neighbors.add(map.get(child));//不管是否visit过,都要单向连接 
    }
  }
  return map.get(node);
}
private void enqueueAndClone(Queue<UndirectedGraphNode> q, UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> map) {
  q.add(node);
  UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
  map.put(node, newNode);
}

这个经典题居然submit了4遍才过,给33.8%的通过率拖后腿了。原因是忘记d[i]表示什么了就开始瞎写。就算做过的经典题,当场再想一想又有什么不好的?

d[i]表示到第i级台阶有几种走法。d[0]必须是1,这个是用i=1试出来的。最后返回d[n]不是d[n – 1]!

public int climbStairs(int n) {
  if (n == 0)
    return 0;
  int[] d = new int[n + 1];
  d[0] = 1;
  for (int i = 1; i <= n; i++) {
    d[i] += d[i - 1];
    if (i >= 2)
      d[i] += d[i - 2];
  }
  return d[n];
}

只用三个变量,不用array的做法(既然只看d[i – 1], d[i -2]往前看两个,那keep三个变量就够了。

public int climbStairs(int n) {
  if (n == 0)
    return 0;
  int prevPrev = 0;
  int prev = 1;
  for (int i = 1; i <= n; i++) {
    int curr = 0;
    curr += prev;
    if (i >= 2)
      curr += prevPrev;
    prevPrev = prev;
    prev = curr;
  }
  return prev;
}
Tags:

一维DP。

  • d[i] 是给第i个小孩最少几块糖
    • rank[i] > rank[i – 1],必须比前一个多给一块,d[i] = d[i – 1] + 1
    • rank[i] == rank[i – 1],两个排名一样,第二个就给一块就行了, d[i] = 1
    • rank[i] < rank[i – 1],比上一个排名低,应该少给一块,但是若上一个已经只给一块了,就得往前推一个一个多给。推到什么时候为止呢?若排名比下一个高,糖还一样多,就得再给;直到这个关系打破(排名一样或比下一个还低,或是糖已经满足关系)就不用再往前推了。
public int candy(int[] ratings) {
    if (ratings.length == 0)
        return 0;
    int[] d = new int[ratings.length];
        d[0] = 1;
    for (int i = 1; i < ratings.length; i++) {
        if (ratings[i] == ratings[i - 1])
            d[i] = 1;
        else if (ratings[i] > ratings[i - 1])
            d[i] = d[i - 1] + 1;
        else {// should give less candy than prev child
            d[i] = 1;
            if (d[i - 1] == 1) {
                int j = i;
                while (j > 0 && ratings[j - 1] > ratings[j] && d[j - 1] == d[j]) {
                    //only push backwards when ratings diff but candy are same
                   d[j - 1]++;
                   j--;
                }
            }
        }
    }
    int sum = 0;
    for (int i = 0; i < ratings.length; i++) {
        sum += d[i];
    }
    return sum;
}
Tags:

用两个stack O(n)的方法:

  1. 一个stack s1 push root。
  2. 一边pop s1进s2,一边把pop的left, right push进s1(先左后右,这先进s2的是右边,左边在s2靠前部分,所以最后先print出来)
  3. 这样最后s2就是一个正好从上到下是post order的traversal,一边pop一边print就行了。
public void postOrderTwoStacks(TreeNode root) {
  Stack<TreeNode> s1 = new Stack<TreeNode>();
  Stack<TreeNode> s2 = new Stack<TreeNode>();
  s1.push(root);
  while (!s1.isEmpty()) {
    TreeNode pop = s1.pop();
    s2.push(pop);
    if (pop.left != null)
      s1.push(pop.left);
    if (pop.right != null)
      s1.push(pop.right);
  }
  while (!s2.isEmpty()) {
    System.out.print(s2.pop().val + ", ");
  }
}

用一个stack O(h)的方法:

  1. 一个stack,先push root
  2. keep一个prev variable表示刚才试过的node(在stack里尝试来着,不管最后是否把它pop出去了),一直在更新。
  3. stack.peek() == curr,每次用curr和prev比较
    • 如果prev是空或者prev是curr的parent,说明在top down的traverse,这时候可不能print prev(那就变成preorder了);而应该push curr的左子,木有才push右子,全都木有说明curr是leaf,就pop print就行了。
    • 如果prev是curr的左子,说明在从左下角往上traverse,这时若curr有右子,则push右子(应该traverse右子)- prev应该是已经pop出来的了。
    • 如果prev是curr的右子,说明从右下角往左上traverse,这时直接pop print curr就行了,因为这时root也该出来了。
public void postOrder(TreeNode root) {
  Stack<TreeNode> s = new Stack<TreeNode>();
  s.push(root);
  TreeNode prev = null;
  while (!s.isEmpty()) {
    TreeNode curr = s.peek();
    if (prev == null || prev.left == curr || prev.right == curr) { // top down
      if (curr.left != null)
        s.push(curr.left);
      else if (curr.right != null)
        s.push(curr.right);
      else {// is leaf
        popAndPrint(s, curr);
      }
    } else if (prev == curr.left) { // from left child to parent
      if (curr.right != null)
        s.push(curr.right);
      else {
        popAndPrint(s, curr);
      }
    } else { // prev.right == curr, from right child to parent
      popAndPrint(s, curr);
    }
    prev = curr;
  }
}
private void popAndPrint(Stack<TreeNode> s, TreeNode curr) {
  System.out.print(curr.val + ", ");
  s.pop();
}