Archive for October 1st, 2013
这题看似很难，因为树的rotation完全不会；但是咬牙想了五分钟就bug free的写出来了，一遍过，看来树的recursive理解已经挺到位了。
算法：1～n中每个数字都可以是root，定了谁是root之后（比如k），他的左子树只能是1～k-1组成的，右子树只能是k+1～n组成的。左子树的variation数目×右子树的就是k作为root的有几种rotation。有点要注意：终止条件有两种：
- p == q，说明就一个节点了，没啥可转的，就一种return 1
- 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;
}
这个没想到用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();
}
Tags: stack/queue
