今日总结

784. 字母大小写全排列

回溯；
class Solution {
List ans = new ArrayList<>();
public List letterCasePermutation(String s) {
dfs(s.toCharArray(), 0);
return ans;
}
public void dfs(char[] s, int pos) {
while(pos < s.length && Character.isDigit(s[pos])) pos++;//attention 是 while，不是if
if(pos == s.length) {
ans.add(new String(s));
return ;
}
s[pos] ^= 32;
dfs(s, pos + 1);
s[pos] ^= 32;还回去，继续分支
dfs(s, pos + 1);
}
}

106. 从中序与后序遍历序列构造二叉树 & 105. 从前序与中序遍历序列构造二叉树

因为先序遍历和后序遍历都能很容易的确定头节点是谁；
而中序遍历可以很容易的确定左右子树的长度；
所以可以把中序遍历存到HashMap中，从而达到快速确定左右子树长度的作用；
public TreeNode dnn(int[] postorder, int inFirst, int inLast, int posFirst, int posLast) {
if(inFirst > inLast || posFirst > posLast) return null;
int rootVal = postorder[posLast];
TreeNode root = new TreeNode(rootVal);
int index = map.get(rootVal);
root.left = dnn(postorder, inFirst, index - 1, posFirst, index - 1 - inFirst + posFirst);
root.right = dnn(postorder, index + 1, inLast, index - 1 - inFirst + posFirst + 1, posLast - 1);
return root;
}
&
public TreeNode dnn(int[] preorder, int preFirst, int preLast, int inFirst, int inLast) {
if(preFirst > preLast || inFirst > inLast) return null;
int rootVal = preorder[preFirst];
int index = map.get(rootVal);
TreeNode root = new TreeNode(rootVal);
root.left = dnn(preorder, preFirst + 1, index - 1 -inFirst + preFirst + 1, inFirst, index - 1);
root.right = dnn(preorder, index - 1 -inFirst + preFirst + 1 + 1, preLast, index + 1, inLast);
return root;
}

120. 三角形最小路径和

动态规划；
最左边的只有上面，也就是第零列；
最右边的只有左上，也就是对角线；
for(int i = 1; i < n; i++) {
ans[i][0] = ans[i - 1][0] + triangle.get(i).get(0);
for(int j = 1; j <= i; j++) {
ans[i][j] = Math.min(ans[i - 1][j], ans[i - 1][j - 1]) + triangle.get(i).get(j);
ans[i][i] = ans[i - 1][i - 1] + triangle.get(i).get(i);
}
}

121. 买卖股票的最佳时机

实时更新最小值和答案的最大值；
for(int i = 0; i < prices.length; i++) {
if(prices[i] < min) min = prices[i];
if(prices[i] - min > ans) ans = prices[i] - min;
}