这题本身不难，但是有一个常见错误：
在 dfs 中直接 root = null 是无法删除 root 的.
因为对于 object， java 是 pass by value, 传递过去的是 object reference.
在
换句话讲，dfs 中作为参数的 TreeNode root 是一个新建的 reference，默认指向的是原参数 root 的同一个位置。因此我们可以对它指向的 object 进行各种操作.
但是当我们更改这个 reference 指向时，我们只是改了函数自己的那个 copy 所指向的 object，而对原始参数指向的东西没有任何改变。
于是这题如果试图在 dfs 中用 root = null 删除节点，实际上我们不会删除任何节点，只会更改在自己这层 call 中， root 指向的节点而已。因此我们之前可以用其他 method call 在 dfs 中对各种 list, set, map 和 collection 里面的值进行修改，但是改 method call 里面的 reference 并不会对原 object 造成任何影响。
Copy public class Solution {
public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> rst = new ArrayList<List<Integer>>();
while(root != null) {
List<Integer> list = new ArrayList<Integer>();
if(dfs(list, root)) root = null;
rst.add(list);
}
return rst;
}
private boolean dfs(List<Integer> list, TreeNode root){
if(root == null) return false;
if(root.left == null && root.right == null){
list.add(root.val);
return true;
}
if(dfs(list, root.left)) root.left = null;
if(dfs(list, root.right)) root.right = null;
return false;
}
} 对于两个人 A 与 B, 有如下可能：
knows(A, B)
因为给定条件“所有人都认识明星，而明星不认识任何人”，对于任意一对 A 和 B，我们仅仅做一次 knows 比较就可以排除掉一个人，我们就可以存一个 ptr 依次扫描整个数组。
当最后只剩下一个可能性的时候，我们依然有必要检查一下，因为我们不确定这个 cur 是不是认识数组里的其他人，或者是不是其他人都认识 cur. 因此再一次循环进行判断 + 记录认识 cur 的人数就可以了。
Copy public class Solution extends Relation {
public int findCelebrity(int n) {
int cur = 0;
for(int i = 1; i < n; i++){
if(knows(cur, i)) cur = i;
}
int knowCount = 0;
for(int i = 0; i < n; i++){
if(i == cur) continue;
if(knows(cur, i)) return -1;
else if(knows(i, cur)) knowCount ++;
}
return knowCount == n - 1 ? cur: -1;
}
} 老题了，前缀积数组的应用。
Copy public class Solution {
public int[] productExceptSelf(int[] nums) {
int N = nums.length;
int[] leftCumProd = new int[N + 1];
int[] rightCumProd = new int[N + 1];
leftCumProd[0] = 1;
rightCumProd[N] = 1;
for(int i = 0; i < N; i++){
leftCumProd[i + 1] = leftCumProd[i] * nums[i];
}
for(int i = N - 1; i >= 0; i--){
rightCumProd[i] = rightCumProd[i + 1] * nums[i];
}
int[] rst = new int[N];
for(int i = 0; i < N; i++){
rst[i] = leftCumProd[i] * rightCumProd[i + 1];
}
return rst;
}
} Word Search II 之后留下了后遗症，看到这种问题也想用记忆化搜索加快速度。
不过这题的 subproblem 不太一样。 因为当最开始的 n 真的等于质数时，我们返回 empty list; 但是如果这是个 dfs 嵌套的 method call，我们却要把这个质数加到 list 里。 换句话说，同样 size / interval 的 subproblem， 返回的结果却要依情况而定，这是违反了记忆化搜索和动态规划性质的。
简单说就是，这题的 subproblem 之间，不具有 optimal substructure.
dfs(12) 并不等于 2 + dfs(6) 和 3 + dfs(4) 与 4 + dfs(3) ..
于是我们仔细观察 sample output 中，n = 32 的正解，重新排列顺序之后得到：
n = 32
我们可以发现把解按照递减顺序排列之后，这是一个类似 combination 的问题，因为：
具体实现上，为了保证不盲目把初始 n 加到结果中，第一层 dfs 里传进去的 prev 是 n - 1.
这题的 dfs 里 base case 还不太一样，我们做的是试图直接把 n 加进去作为一个解，同时要注意不能直接 return ，否则后面的解就都看不到了。
真正的 return ，是在对于 n 来讲从大到小连 i = 2 都尝试过作为 factor 之后自然结束搜索。
Copy public class Solution {
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> rst = new ArrayList<List<Integer>>();
dfs(rst, new ArrayList<Integer>(), n, n - 1);
return rst;
}
private void dfs(List<List<Integer>> rst,
List<Integer> list, int n, int prev){
if(n <= prev){
list.add(n);
rst.add(new ArrayList<Integer>(list));
list.remove(list.size() - 1);
//return ;
}
for(int i = n / 2; i >= 2; i--){
if(n % i == 0 && i <= prev){
list.add(i);
dfs(rst, list, n / i, i);
list.remove(list.size() - 1);
}
}
}
} 我想了半天怎么用 KMP 做这题复杂度比较低，看到 tag 里有 hashtable 就直接用 hashmap 套用了一下，然后不但 AC 了还在运行速度上超过了 76% 的人。。。这题的用意到底是什么。。。
唯一需要注意的是对于出现超过 2 次的 str 不要重复添加，因此 hashmap 里留一个 count ，根据 count 行事。
Copy public class Solution {
public List<String> findRepeatedDnaSequences(String s) {
HashMap<String, Integer> map = new HashMap<>();
List<String> list = new ArrayList<>();
int N = s.length();
for(int i = 0; i <= N - 10; i++){
String str = s.substring(i, i + 10);
if(map.containsKey(str)){
int count = map.get(str);
if(count == 1) list.add(str);
map.put(str, count + 1);
} else {
map.put(str, 1);
}
}
return list;
}
} 去地里看了一圈，这题更有意思的解法是利用 DNA 只有四种字母的性质去做 encode / decode.
因为字母只有四种可能，我们可以用 2 bits 表示任意字母；同时因为 sequence 长度为 10，所以我们只需要 20 bits 就可以 Uniquely represent 一个 sequence，即自己实现无 collision 的 hashing. 简便起见，一个 32-bit int 就够了。
encode 时，对于每一个给定的 substring，遍历每个字母，然后根据字母决定其数字，给最后两位赋值之后 << 2.
decode 时，每次把当前数字除以 4 看余数，根据余数决定字母，而后 >> 2.
这样对于每一个 string / int ，其 encode / decode 都是唯一的。
空间占用为 2^20 = 1048576 个 int = 4.194304 MB ，代表可能的 hash 值数量。
Copy public class Solution {
public List<String> findRepeatedDnaSequences(String s) {
List<String> list = new ArrayList<>();
int N = s.length();
int[] hash = new int[1048576];
for(int i = 0; i <= N - 10; i++){
String str = s.substring(i, i + 10);
int index = encode(str);
hash[index] ++;
if(hash[index] == 2) list.add(str);
}
return list;
}
private int encode(String s){
int num = 0;
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
num = num << 2;
if(c == 'A') num += 0;
if(c == 'C') num += 1;
if(c == 'G') num += 2;
if(c == 'T') num += 3;
}
return num;
}
private String decode(int num){
StringBuilder sb = new StringBuilder();
for(int i = 0; i < 10; i++){
if(num % 4 == 0) sb.append('A');
if(num % 4 == 1) sb.append('C');
if(num % 4 == 2) sb.append('G');
if(num % 4 == 3) sb.append('T');
num = num >> 2;
}
return sb.reverse().toString();
}
} 轻松愉快，一次 AC.
Copy public class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for(String str : tokens){
if(!isOperator(str)){
stack.push(Integer.parseInt(str));
} else {
int num2 = stack.pop();
int num1 = stack.pop();
if(str.equals("+")) stack.push(num1 + num2);
if(str.equals("-")) stack.push(num1 - num2);
if(str.equals("*")) stack.push(num1 * num2);
if(str.equals("/")) stack.push(num1 / num2);
}
}
return stack.peek();
}
private boolean isOperator(String str){
if(str.equals("+") || str.equals("-")) return true;
if(str.equals("/") || str.equals("*")) return true;
return false;
}
} 
