Lexi's Leetcode solutions

Archive for the ‘classic’ Category

给一个Set<Node>,每个节点里面有个List<Node> children,求它的sorted list representation http://en.wikipedia.org/wiki/Topological_sorting。Google phone就挂这了。

比如下图,假设箭头全是向下的,则return list就是A->C->E->F->B->D,就是其中一个valid solution。所有dependent关系都满足,然后那些无dependent关系的(比如B和C, D和E就任意顺序就行)。

  A
/   \
B   C
\   /\
  D   E -> F

算法:

  1. 一个map<Node, Boolean>记录走过的节点,false表示visiting (gray), true表示visited (black),无环图说明不会遇见灰色节点(一个节点还没visit完呢就又遇见它了),否则就是有环了(circular dependent)。
  2. 每次从白色节点(set里)里挑一个,从它开始DFS。
  3. DFS就是把这个节点涂灰,然后顺次DFS它的孩子,每个先visited的孩子的list都插在dummy head的最前面,所以老二的孙子其实排在老大前面(比如C的老大是D,老二是E->F,结果就是CEFD(最后把父亲放最前面)。这样保证每个孩子序列都是原来顺序,各个孩子树之间反正没关系,就顺次排开就行了。
  4. 每次一个节点被涂黑,就从set里remove。直到set空了为止。
Node topoSort(Set<Node> set) {
    Map<Node, Boolean> map = new HashMap<Node, Boolean>;
    Node dummy = new Node();
    while (!set.isEmpty()) {
        Node node = set.iterator().next();
        dfs(node, dummy, set, map);
    }
    return dummy.next();
} 
void dfs(Node node, Node dummy, Set<Node> unBlacked, Map<Node, Boolean> map) {
    if (!map.containsKey(node)) {
        map.put(node, false);
        for (Node child : node.children) {     
            dfs(child, dummy, set, map);
        }
        Node break = dummy.next;
        dummy.next = node;
        node.next = break;
        map.put(node, true);//mark black
        set.remove(node);
     } else if (map.get(node) == false) {
        //gray, there's a loop
        throw new LoopExistException(); 
}
Advertisements
Tags: ,

比如abcdefg, defmnabs,最长公共subtring是def。

又是二维DP求String的最优解。居然还是算法课作业做过,真是一点印象也木有了。

  • d[i][j] : A[0…i]和B[0…j]的最长公共后缀的长度
  • d[i][j] =
    1. A[i] == B[j] : d[i][j] = d[i – 1][j – 1] + 1 //公共后缀多了当前这个char
    2. A[i] != B[j] : d[i][j] = 0//断开了,无公共后缀了

总结一下二维DP解String题的做法:

  • 一个String, d[i][j]表示A[i…j]的某个最优解
  • 两个String, d[i][j]表示A[0…i], B[0…j]的某个比较方式的最优解

这个经典题居然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:

用两个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();
}

经典题,注意balanced的定义:左右子树都balance,且高度差<=1。所以下面这个也是balanced的,即使a的做右子树都不是完全树。

    a
   / \ 
  b   d
 /     \
c       e

唯一的trick:不用生成新的data structure来保存“boolean isBalanced, int height”,直接用height = -1表示不平衡就行。

public boolean isBalanced(TreeNode root) {
  return getHeight(root) >= 0;
}
private int getHeight(TreeNode root) {
  if (root == null)
    return 0;
  int leftHeight = getHeight(root.left);
  if (leftHeight < 0)
    return -1;
  int rightHeight = getHeight(root.right);
  if (rightHeight < 0)
    return -1;
  if (Math.abs(leftHeight - rightHeight) > 1)
    return -1;
  return Math.max(leftHeight, rightHeight) + 1;
}
Tags: , ,

这题leetcode把关太松了,一个cache就让过了。实际上应该再加一个prefix tree把关,比如leetcode, le如果发现连个prefix都不是,那么lee, leet, leetc..都不要查了。所以算法是:

  1. 拿字典建prefix tree:O(字典大小*最长词的长度)
  2. i=0开始recurse, j=i开始一点点增长当前substring长度,若curr substring在字典里,就看看j + 1开头的剩下一半能不能成;能成就直接返回true,不能的话还得继续i++
  3. curr substring不在字典里,那应该j++的,但这时候先看一看curr是不是至少是个prefix,要是连prefix都不是,这个i直接作废,i++
  4. 每次做好了cache一下,boolean cache[i]表示以i开头到词尾的这个substring能不能用字典组成
public class Node {
  char c;
  Node[] children;
  public Node (char ch){
    c = ch;
    children = new Node[26];
  }
}
public boolean wordBreak(String s, Set<String> dict) {
  if (s == null || s.length() == 0)
    return false;
  return canSplit(s, dict, 0, new HashMap<Integer, Boolean>(), makePrefixTree(dict));
}
private Node makePrefixTree(Set<String> dict) {
  Node root = new Node('0');
  for (String s : dict) {
    insertWord(root, s);
  }
  return root;
}
private void insertWord(Node root, String s) {
  for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    if (root.children[c - 'a'] == null) {
      root.children[c - 'a'] = new Node(c);
    }
    root = root.children[c - 'a'];
  }
}
private boolean canSplit(String s, Set<String> dict, int i, HashMap<Integer, Boolean> cache, Node root) {
  if (i == s.length())
    return true;
  if (cache.containsKey(i))
    return cache.get(i);
  boolean canSplit = false;
  for (int j = i; j < s.length(); j++) {
    String first = s.substring(i, j + 1);
    if (dict.contains(first)) {
      if (canSplit(s, dict, j + 1, cache, root)) {
        canSplit = true;
        break;
      } //cannot split to the end, try split by i, j + 1
    } else {
      //does not contain first word, try split by i, j + 1
      if (!containsAsPrefx(first, root)) {
        //does not even contain first word as prefix, then can't start by i, split by i + 1
        break;
      }
    }
  }
  cache.put(i, canSplit);
  return cache.get(i);
}
private boolean containsAsPrefx(String s, Node root) {
  for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    if (root.children[c - 'a'] == null)
      return false;
    root = root.children[c - 'a'];
  }
  return true;
}
Tags:

DP是O(n2)的解法。新开一个数列B,B[i]表示以A[i]结尾的LIS的最大长度。每次在i处往前看,若j<i,则以i结尾的就只少>=B[j] + 1。

public int getLIS(int[] A) {
  int[] B = new int[A.length];
  int max = 1;
  B[0] = 1;
  for (int i = 1; i < A.length; i++) {
    B[i] = 1;
    for (int j = i - 1; j >= 0; j--) {
      if (A[i] > A[j]) {
        B[i] = Math.max(B[i], B[j] + 1);
        max = Math.max(B[i], max);
      }
    }
  }
  return max;
}
Tags: ,