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