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 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;
    }
}

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 的人数就可以了。

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;
    }
}

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>> 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);
            }
        }
    }
}

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.

因为字母只有四种可能，我们可以用 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 值数量。

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;
    }
}