7/6, LinkedIn 面经
Find Leaves of Binary Tree
这题本身不难，但是有一个常见错误：
在 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 造成任何影响。
public List<List<Integer>> findLeaves(TreeNode root) {
List<List<Integer>> ans= new ArrayList<List<Integer>>();
addRemove(ans, root);
return ans;
}
public int addRemove(List<List<Integer>> ans, TreeNode root){
if(root==null){
return 0;
}
int left = addRemove(ans, root.left);
int right = addRemove(ans, root.right);
int depth = Math.max(left,right)+1;
if(ans.size()<depth) ans.add(new ArrayList<Integer>());
ans.get(depth-1).add(root.val);
root.left=null; root.right=null;
return depth;
}
Find the Celebrity
对于两个人 A 与 B, 有如下可能：
knows(A, B)
A --> B ( A knows B )
A 一定不是明星
A <-- B ( B knows A)
B 一定不是明星
A ... B ( 互相不认识 )
B 一定不是明星
因为给定条件“所有人都认识明星，而明星不认识任何人”，对于任意一对 A 和 B，我们仅仅做一次 knows 比较就可以排除掉一个人，我们就可以存一个 ptr 依次扫描整个数组。
当最后只剩下一个可能性的时候，我们依然有必要检查一下，因为我们不确定这个 cur 是不是认识数组里的其他人，或者是不是其他人都认识 cur. 因此再一次循环进行判断 + 记录认识 cur 的人数就可以了。
int a = 0; int b=n-1;
while(a<b){
if(knows(a,b)) a++;
else
b--;
}
for(int i=0;i<n;i++)
if(i!=b &&( knows(b,i) || !knows(i,b))) return -1;
return a;
int candidate = 0;
for(int i=1;i<n;i++){
if(knows(candidate, i))
candidate = i;
}
for(int i=0;i<n;i++){
if(i!=candidate && (knows(candidate, i) || !knows(i,candidate))) return -1;
}
return candidate;
Product of Array Except Self
老题了，前缀积数组的应用。
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;
}
}
Factor Combinations
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
[16,2]
[8, 4]
[8, 2, 2]
[4, 4, 2]
[4, 2, 2, 2]
[2, 2, 2, 2, 2]
我们可以发现把解按照递减顺序排列之后，这是一个类似 combination 的问题，因为：
每一个解是若干个元素的组合，解与解之间大小不等
同一组解之间，元素的选取有单调性 (去重)
具体实现上，为了保证不盲目把初始 n 加到结果中，第一层 dfs 里传进去的 prev 是 n - 1.
这题的 dfs 里 base case 还不太一样，我们做的是试图直接把 n 加进去作为一个解，同时要注意不能直接 return ，否则后面的解就都看不到了。
真正的 return ，是在对于 n 来讲从大到小连 i = 2 都尝试过作为 factor 之后自然结束搜索。
public class Solution {
public List<List<Integer>> getFactors(int n) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
dfs(list, new ArrayList<Integer>(), 2, n);
return list;
}
public void dfs(List<List<Integer>> list, List<Integer> cur, int start, int n){
if(n==1){
if(cur.size()>1)
list.add(new ArrayList<Integer>(cur));
return;
}
for(int i=start;i<=n;i++){
if(n%i==0){
cur.add(i);
dfs(list, cur, i, n/i);
cur.remove(cur.size()-1);
}
}
}
}
Repeated DNA Sequences
我想了半天怎么用 KMP 做这题复杂度比较低，看到 tag 里有 hashtable 就直接用 hashmap 套用了一下，然后不但 AC 了还在运行速度上超过了 76% 的人。。。这题的用意到底是什么。。。+
唯一需要注意的是对于出现超过 2 次的 str 不要重复添加，因此 hashmap 里留一个 count ，根据 count 行事。
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.
实际上是我们自己建立了hash的算法
因为字母只有四种可能，我们可以用 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 值数量。
注意: n>>2 这种表达方式是不对;n=n>>2
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();
}
}
Evaluate Reverse Polish Notation
轻松愉快，一次 AC.
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;
}
}