记录

Monday

2. Convert BST to Greater 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 sum = 0;
    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return root;
        }
        convertBST(root.right);
        root.val = root.val + sum;
        sum = root.val;
        convertBST(root.left);
        return root;
    }
}
TODO:
1. better understand traversal. Traversal is different from recursion. Traversal is like iterator and iteration, all it matters is to visit elements in a specific order. Whether you use iteration or recursion to implement it is totally your own choice. So __traversal__ is about visiting in a specific order. And this one just happens to make use of recursion.
Visiting in a specific order. Then you just care about the visiting part. That's it.
To make it more clear, let's state it this way:
__Traversal is all about visiting elements in a specific order. Wheter you use loop or recursion to implement it is totally your own choice. __

Shit. In the end we made it for the second week. So tired. Next time shouldn't be like this. Procrastination!!!

Tuesday

1. Sort Characters By Frequency

public class Solution {
    public String frequencySort(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        char[] chars = s.toCharArray();
        // build a map
        // loop the map value lists and sort by size
        Map<Character, Integer> map = new HashMap();
        for (char c : chars) {
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }
        List<Map.Entry<Character, Integer>> entries = new LinkedList();
        entries.addAll(map.entrySet());
        Collections.sort(entries, (entry1, entry2) -> entry2.getValue() - entry1.getValue());
        int index = 0;
        for (Map.Entry<Character, Integer> entry : entries) {
            char c = entry.getKey();
            int count = entry.getValue();
            for (int i = 0; i < count; i++) {
                chars[index] = c;
                index++;
            }
        }
        return new String(chars);
    }
}

Learnt some more interfaces about Java. Good for work, not convenient.

TODO:
1. could just use list.sort()
2. could just feed the constructor with a collection instead of using `addAll()`

Tuesday

2. Construct String from 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 String tree2str(TreeNode t) {
        // end: null, return empty
        // get self,
        // get left,
        // get right, ignore if empty
        // combine three and return
        if (t == null) {
            return "";
        }
        String self = Integer.toString(t.val);
        if (t.left == null && t.right == null) {
            return self;
        }
        String left = tree2str(t.left);
        String right = tree2str(t.right);
        left = "(" + left + ")";
        right = right.isEmpty() ? right : "(" + right + ")";
        return self + left + right;
    }
}
NOTES:
1. the description is misleading. When you read the results it is preorder traversal, but the solution is not a pre-order traversal. It is a traditional recursion.
2. Special case::::: when it has no children

Wednesday

1. Find the Difference

public class Solution {
    public char findTheDifference(String s, String t) {
        // check
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        Map<Character, Integer> sMap = new HashMap();
        Map<Character, Integer> tMap = new HashMap();
        putIntoMap(sMap, ss);
        putIntoMap(tMap, tt);
        for (Map.Entry<Character, Integer> tEntry : tMap.entrySet()) {
            if (!sMap.containsKey(tEntry.getKey()) || sMap.get(tEntry.getKey()) != tEntry.getValue()) {
                return tEntry.getKey();
            }
        }
        throw new IllegalArgumentException("No such thing in t");
    }
   
    private void putIntoMap (Map<Character, Integer> map, char[] chars) {
        for (char c : chars) {
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
            } else {
                map.put(c, 1);
            }
        }
    }
}
NOTES:
1. iterate hashmap

TODO:
1. better solution:

public class Solution {
    public char findTheDifference(String s, String t) {
        // check
        char[] ss = s.toCharArray();
        char[] tt = t.toCharArray();
        char result = 0;
        for (char sc: ss) {
            result = (char)(result ^ sc);
        }
        for (char tc : tt) {
            result = (char)(result ^ tc);
        }
        return result;
    }
}


NOTE
1. int and char conversion, char < int, char 1 byte, int 2 bytes
2. others all the same, just one different, could use xor
WHY?
result ^= c;   -- good
result = result ^ c; -- error

Wednesday

2. Move Zeroes

public class Solution {
    public void moveZeroes(int[] nums) {
        int count = 0;
        int last = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                count++;
            } else {
                nums[i - count] = nums[i];
                last = i - count;
            }
        }
        for (int i = last + 1; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

TODO: there is another solution with 2 pointers.

Thursday

1. Minesweeper

public class Solution {
    public char[][] updateBoard(char[][] board, int[] click) {
        // stop: 1. self is mine, change self to x
        // 2. count surroundings, surroundings have mine -> change self to that number
        // 3. self is out of range, return
        // not have, then recurse all surroundings
        if (click[0] < 0 || click[0] >= board.length || click[1] < 0 || click[1] >= board[0].length ) {
            return board;
        }
        if (board[click[0]][click[1]]== 'M') {
            board[click[0]][click[1]] = 'X';
            return board;
        } else if (board[click[0]][click[1]] == 'E') {
            // how to check surroundings?
            int count = 0;
            for (int i = click[0] - 1; i <= click[0] + 1; i++) {
                for (int j = click[1] - 1; j <= click[1] + 1; j++) {
                    if (i >= 0 && i < board.length && j >= 0 && j < board[0].length && !(i == click[0] && j == click[1])) {
                        if (board[j] == 'M') {
                            count++;
                        }
                    }
                }
            }
            if (count == 0) {
                board[click[0]][click[1]] = 'B';
                for (int i = click[0] - 1; i <= click[0] + 1; i++) {
                    for (int j = click[1] - 1; j <= click[1] + 1; j++) {
                        if (!(i == click[0] && j == click[1])) {
                            updateBoard(board, new int[]{i, j});
                        }
                    }
                }
                return board;
            } else {
                board[click[0]][click[1]] = Integer.toString(count).charAt(0);
                return board;
            }
        }
        // already visited!!
        return board;
    }
}
妈的，丧心病狂的题目。写了很久。还好没怎么调就通过了。以后用js开写了，不管了。

TODO:
1. 这哥们有个方法可以简化第二次循环：
http://www.cnblogs.com/grandyang/p/6536694.html

Thursday

2. Friend Circles

/**
* @param {number[][]} M
* @return {number}
*/

var findCircleNum = function(M) {
    let count = 0
    M.forEach((rows, rowIndex) => {
        rows.forEach((val, colIndex) => {
            if (rowIndex <= colIndex && val === 1) {
                count++
                markSameGroup(rowIndex, colIndex);
            }
        })
    })
    return count
   
   
    function markSameGroup (i, j) {
        M[i][j] = 0;
        for (var index = 0; index <= j; index++) {
            if (M[index][j] === 1) {
                markSameGroup(index, j)
            }
        }
        for (var index = i; index < M[0].length; index++) {
            if (M[i][index] === 1) {
                markSameGroup(i, index)
            }
        }
    }
};

Using js has its pros and cons.
Why leetcode always report the wrong line number for js errors? f***!

Friday

1. Array Nesting

/**
* @param {number[]} nums
* @return {number}
*/
var arrayNesting = function(nums) {
    // check
    let max = 0
    nums.forEach((num, index) => {
        let size = 0
        markUsed(index)
        max = Math.max(size, max)
        
        function markUsed (index) {
            if (nums[index] >= 0) {
                size++
                const value = nums[index]
                nums[index] = -1
                markUsed(value)
            }
        }
    })
    return max
};
TODO:
1. could do with loops
2. could declare the function outside of loop, but how to deal with the global counter:   declare a `state = {size: 0}` and update `state.size++`

Friday
2. Product of Array Except Self

Naive:

/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function(nums) {
    const before = []
    const after = []
    before[0] = 1
    for (let i = 1; i < nums.length; i++) {
        before = before[i - 1] * nums[i - 1]
    }
    after[nums.length - 1] = 1
    for (let i = nums.length - 2; i >= 0; i--) {
        after[i] = after[i + 1] * nums[i + 1]
    }
    const result = []
    for (let i = 0; i < nums.length; i++) {
        result[i] = before[i] * after[i]
    }
    return result
};[/i][/i][/i][/i][i][i][/i][/i]
[i][i][i][i]Follow up:[/i][/i][/i][/i]
[i][i][/i][/i]
[i][i][i][i]/**
* @param {number[]} nums
* @return {number[]}
*/
var productExceptSelf = function(nums) {
    const result = []
    result[0] = 1
    for (let i = 1; i < nums.length; i++) {
        result[i] = result[i - 1] * nums[i - 1]
    }
    let product = 1
    for (let j = nums.length - 2; j >= 0; j--) {
        product = nums[j + 1] * product
        result[j] = product * result[j]
    }
    return result
};

TODO: tricky, practice more
[/i][/i][/i][/i]