Archive for July 14th, 2013
看http://blog.unieagle.net/2012/09/16/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Acontainer-with-most-water/才会的。
之前想的都是两两配对，然后update water最大值。但是这样有一些白做了的pair: 比如(i, j1), (i, j2), (i, j3)如果i比这几个j都小，那么短板就是i，j再怎么变也没用（j再大也没用，j要变小就更没用了），所以应该变i。这样i, j从两头逼近，所以一开始的宽是最大的，然后i，j越靠越近，就是说宽在不断变小，所以这个时候就指着arr[i], arr[j]没准能特大然后overcome宽小的缺陷了。因为是i, j不能一样，所以两头逼近这个方法始于本题。
private int maxWater(int[] arr) {
int maxWater = 0;
int i = 0, j = arr.length - 1;
while (i < j) {
maxWater = updateMax(maxWater, arr, i, j);
if (arr[i] < arr[j])
i++;
else
j--;
}
return maxWater;
}
[leetcode]Construct Binary Tree from Preorder and Inorder Traversal | 前序中序建树
Posted on: July 14, 2013
思路：
- pre的第一个肯定是root
- 在in里找root出现的位置m，那in的current subarray的左边就是左子树，右边就是右子树
- 左子树left size大小是m – a
- 那么pre里面root之后的left size个就是pre里面的左子树，可以将它作为一个subarray开始下一层递归了
- pre里面root + leftsize之后的那一半（到q为止）就是pre里面的右子树，可以将它作为一个subarray开始下一层递归，返回作为root的右子树。
- 所以一共三个变量:
- p the beginning of PRE’s current subarray (subtree)
- q the end of PRE’s current subarray (subtree)
- a the beginning of IN’s current subarray (subtree)
private TreeNode constructFromInAndPre(int[] PRE, int[] IN, int p, int q, int a) {
if (p > q)
return null;
TreeNode root = new TreeNode(PRE[p]);
int m = findIndex(PRE[p], IN); //the index of the current root in the IN order
if (m < 0)
System.out.println("not exist");
int leftSize = m - a; //the left subtree of root's size
root.left = constructFromInAndPre(PRE, IN, p + 1, p + leftSize, a);
root.right = constructFromInAndPre(PRE, IN, p + leftSize + 1, q, m + 1);
return root;
}
Tags: tree
Lexi's Leetcode solutions 