Lexi's Leetcode solutions

Archive for October 1st, 2013

这题看似很难,因为树的rotation完全不会;但是咬牙想了五分钟就bug free的写出来了,一遍过,看来树的recursive理解已经挺到位了。

算法:1~n中每个数字都可以是root,定了谁是root之后(比如k),他的左子树只能是1~k-1组成的,右子树只能是k+1~n组成的。左子树的variation数目×右子树的就是k作为root的有几种rotation。有点要注意:终止条件有两种:

  1. p == q,说明就一个节点了,没啥可转的,就一种return 1
  2. p > q,说明这一段已经不存在了,这时不应该return 0,因为这正是子树是null的情况!所以还应该return 1
public int numTrees(int n) {
  return getWays(1, n);
}
int getWays(int p, int q) {
  if (p >= q)
    return 1;
  int ways = 0;
  for (int i = p; i <= q; i++) {
    int leftWays = getWays(p, i - 1);
    int rightWays = getWays(i + 1, q);
    ways += leftWays * rightWays;
  }
  return ways;
}
Tags: , ,

这个没想到用stack,还傻乎乎的用一种括号配对的方法做,结果设了l1, l2, l3, r1, r2, r3六个变量,然后发现解决不了([)]这种交错的invalid问题。无奈之下看答案,原来一个stack轻松搞定。其实仔细想想,valid的前提条件是“不会出现(]这种不配的抱在一起“的情况,所以当扫到右半边时,一个stack直接比较前一个是不是自己家的左半就好了。

 

public boolean isValid(String s) {
  Stack<Character> stack = new Stack<Character>();
  for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    switch (c) {
    case '(':
    case '{':
    case '[':
      stack.push(c);
      break;
    case ')':
      if (stack.isEmpty() || stack.pop() != '(')
        return false;
      break;
    case '}':
      if (stack.isEmpty() || stack.pop() != '{')
        return false;
      break;
    case ']':
      if (stack.isEmpty() || stack.pop() != '[')
        return false;
      break;
     }
   }
   return stack.isEmpty();
}

Blog Stats

  • 221,510 hits
October 2013
M T W T F S S
 123456
78910111213
14151617181920
21222324252627
28293031