记录

Wednesday

2. Find Duplicate File in System

public class Solution {
    public List<List<String>> findDuplicate(String[] paths) {
        List<List<String>> list = new LinkedList();
        if (paths == null || paths.length == 0) {
            return list;
        }
        // for each path
        // split by space, get first one,
        // for the rest, get path and content, build the map content -> path list
        // then, just return the values of the map
        Map<String, List<String>> map = new HashMap();
        for (String path : paths) {
            String[] parts = path.split(" ");
            for (int i = 1; i < parts.length; i++) {
                // 2.txt(abcd) -> 2.txt, abcd)
                String[] subParts = parts.split("\\(");
                List<String> l;
                if (map.containsKey(subParts[1])) {
                    l = map.get(subParts[1]);
                } else {
                    l = new LinkedList<String>();
                    map.put(subParts[1], l);
                }
                l.add(parts[0] + "/" + subParts[0]);
            }
        }
        map.values().forEach(l -> {
            if (l.size() > 1) {
                list.add(l);
            }
        });
        return list;
    }
}
1. Debugged for a while to pass, sign. But we catch up anyway. Good, celebrate!
2. Miss js!!!
3. to escape (, need two \\

Thursday

1. Maximum Depth of Binary Tree

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
    private int max = 0;
    public int maxDepth(TreeNode root) {
        count(root, 0);
        return max;
    }
   
    private void count (TreeNode node, int count) {
        if (node == null) {
            max = Math.max(max, count);
            return;
        }
        count++;
        count(node.left, count);
        count(node.right, count);
    }
}

Cleaner solution:

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}



Thoughts:

1. iterative recursion -- traversal/backtracking -- usuallly needs to maintain and modify a global -- usually from top down
2. pure recursion -- divide and conqure, break into sub problems of same concept -- build on the return value, no side effects -- usually bottom up

Pure recursion is tricker for me but I like it more -- it is much cleaner.

Thursday

2. Most Frequent Subtree Sum

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
    public int[] findFrequentTreeSum(TreeNode root) {
        Map<Integer, Integer> countOfSum = new HashMap();
        calculateSum(root, countOfSum);
        int max = Integer.MIN_VALUE;
        List<Integer> list = new LinkedList();
        for (Map.Entry<Integer, Integer> entry : countOfSum.entrySet()) {
            int count = entry.getValue();
            System.out.println(count);
            if (count == max) {
                list.add(entry.getKey());
                System.out.println("value" + count);
            } else if (count > max) {
                System.out.println(count + ", " +  max);
                list.clear();
                list.add(entry.getKey());
                max = count; // this!!!! forgot to update it! shit!
            }
        }
        System.out.println(countOfSum);
        int[] results = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            results = list.get(i);
        }
        return results;
    }
   
    private int calculateSum (TreeNode node, Map<Integer, Integer> countOfSum) {
        // end: null, return 0
        // self = left + right
        // update
        // return self
        if (node == null) {
            return 0;
        }
        int left = calculateSum(node.left, countOfSum);
        int right = calculateSum(node.right, countOfSum);
        int self = left + right + node.val;
        if (countOfSum.containsKey(self)) {
            countOfSum.put(self, countOfSum.get(self) + 1);
        } else {
            countOfSum.put(self, 1);
        }
        return self;
    }
}

It was painful.

1. remember to include self for divide and conquer
2. no straightforward way to convert list<Integer> to int[]
3. update max when comparing using if statements4. Java for each doesn't have the index parameter.
  - a functional interface would have exactly one abstract method, but any number of default methods.


Read some solutions online and mostly the same. Either loop the map twice or do it like above, ugly. Still not used to Java' s style.

Friday

1.  Detect Capital

public class Solution {
    public boolean detectCapitalUse(String word) {
        char[] chars = word.toCharArray();
        if (chars.length == 1) {
            return true;
        }
        char first = chars[0];
        boolean restHasUpper = false;
        boolean restHasLower = false;
        // first
        // if upper, all lower or all upper
        // if lower, all lower
        for (int i = 1; i < chars.length; i++) {
            if (isUpper(chars)) {
                restHasUpper = true;
            } else {
                restHasLower = true;
            }
        }
        if (isUpper(first)) {
            return restHasUpper ^ restHasLower;
        } else {
            return !restHasUpper;
        }
    }
   
    private boolean isUpper (char c) {
        return c >= 'A' && c <= 'Z';
    }
}

TODO: 1. short-circuit.
2. a better solution by counting # of upper cases.

Friday

2. Invert Binary Tree

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode tmp = invertTree(root.left);
        root.left = invertTree(root.right);
        root.right = tmp;
        return root;
    }
}

Saturday

1. Find All Numbers Disappeared in an Array

public class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int value = Math.abs(nums);
            // use value - 1 as index
            // get the value turn into negative
            int asIndex = value - 1;
            if (nums[asIndex] > 0) {
                nums[asIndex] = -nums[asIndex];
            }
        }
        List<Integer> list = new LinkedList();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                list.add(i + 1);
            }
        }
        return list;
        // then loop again,
        // find the one that is not negative,
        // the index + 1 is the number that has not appeared,
        // add it to the list
    }
}[/i]
[i]TODO:[/i]
1. this one is not hard, very error-prone. Need to find a solution that would prevent errors.
2. there are other solutions

Saturday

2. Teemo Attacking

public class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        if (timeSeries == null || timeSeries.length == 0) {
            return 0;
        }
        // init end is [0] - 1
        // get new start is max[end + 1, start]
        // new end is start + d - 1
        // count
        int end = timeSeries[0] - 1;
        int total = 0;
        for (int i = 0; i < timeSeries.length; i++) {
            int current = timeSeries[i];
            int newStart = Math.max(end + 1, current);
            end = current + duration - 1;
            total += end - newStart + 1;
        }
        return total;
    }
}

TODO:
1. same as last one, need to find a foolproof solution

Sunday

1. Minimum Moves to Equal Array Elements II

public class Solution {
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int index = nums.length / 2;
        int middle = nums[index];
        int sum = 0;
        for (int num : nums) {
            sum += Math.abs(num - middle);
        }
        return sum;
    }
}

TODO:
there exists an o(n) solution.

Sunday

2. Single Number III

public class Solution {
    public int[] singleNumber(int[] nums) {
        // first, get the xor
        // then, find the first 1 bit
        // then & each one to see if it is 0
        // is 0, xor one
        // not 0, xor another
        // return the two
        int xor = 0;
        for (int num : nums) {
            xor = xor ^ num;
        }
        int one = 0;
        int another = 0;
        int mask = xor & (-xor);
        for (int num : nums) {
            if ((num & mask) == 0) { // !!! this, shit! binary always use parens!!!
                one = one ^ num;
            } else {
                another = another ^ num;
            }
        }
        return new int[]{one, another};
        // explain the trick of a & -a
    }
}

Monday

1. Sum of Two Integers

public class Solution {
    public int getSum(int a, int b) {
        if (a == 0) {
            return b;
        } else if (a > 0) {
            while (a > 0) {
                b++;
                a--;
            }
        } else {
            while (a < 0) {
                b--;
                a++;
            }
        }
        return b;
    }
}
This might seem cheating.

The real solution:

public class Solution {
    public int getSum(int a, int b) {
        if (b == 0) {
            return a;
        }
        int sum = a ^ b;
        int carry = (a & b) << 1;
        return getSum(sum, carry);
    }
}
TODO:
1. explain the trick of a & (-a)