Thursday, October 29, 2015

Leetcode: Text Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly Lcharacters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left justified and no extra space is inserted between words.
For example,
words["This", "is", "an", "example", "of", "text", "justification."]
L16.
Return the formatted lines as:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]
Note: Each word is guaranteed not to exceed L in length.
Corner Cases:
  • A line other than the last line might contain only one word. What should you do in this case?
    In this case, that line should be left-justified.
Understand the problem:
The problem can be divided into two parts. The first part is to determine how many words can form in a line. Then the second part is to determine the length of white spaces between words. 

For the first part, since there must be at least one white space between each word, we can count the total length including one white space until the length is greater than the L. There is one corner case to consider: the last line where the total length might be smaller than L. 

For the second part, again, there are two cases to consider:
 -- If it is the last line, or if the line contains only one word. For this case, the line should be left-justified. 
-- Otherwise, we could calculate how many white spaces we should have, and divided by number of slots between words. 

Code (Java):
public class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> result = new ArrayList<>();
        if (words == null || words.length == 0 || maxWidth < 0) {
            return result;
        }
        
        if (maxWidth == 0) {
            result.add("");
            return result;
        }
        
        fullJustifyHelper(0, words, result, maxWidth);
        
        return result;
    }
    
    private void fullJustifyHelper(int start, String[] words, 
                  List<String> result, int L) {
        if (start >= words.length) {
            return;
        }
        
        int total = 0;
        int len = 0;
        int next = -1;
        int i = start;
        
        while (i < words.length && total < L) {
            total += words[i].length();
            
            if (total > L) {
                next = i;
                break;
            }
            
            len += words[i].length();
            total++;
            i++;
        }
        
        if (next == -1) {
            next = i;
        }
        
        addLists(words, start, next, result, len, L);
        
        fullJustifyHelper(next, words, result, L);
    }
    
    private void addLists(String[] words, int start, int next, 
                          List<String> result, int len, int L) {
        int slots = next - start - 1;
        StringBuffer sb = new StringBuffer();
        // Last line or only one word in a line
        if (slots == 0 || next == words.length) {
            for (int i = start; i < next; i++) {
                sb.append(words[i]);
                if (i == next - 1) {
                    break;
                }
                sb.append(" ");
            }
            
            int trailingSpace = L - len - slots;
            for (int i = 0; i < trailingSpace; i++) {
                sb.append(" ");
            }
            
            result.add(sb.toString());
        } else {
            int aveSpace = (L - len) / slots;
            int moreSpace = (L - len) % slots;
            for (int i = start; i < next; i++) {
                sb.append(words[i]);
                if (i == next - 1) {
                    break;
                }
                for (int j = 0; j < aveSpace; j++) {
                    sb.append(" ");
                }
                
                if (moreSpace > 0) {
                    sb.append(" ");
                    moreSpace--;
                }
            }   
            result.add(sb.toString());
        }
    }
}


Tuesday, October 27, 2015

Leetcode: Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
For example, you may serialize the following tree
    1
   / \
  2   3
     / \
    4   5
as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
Credits:
Special thanks to @Louis1992 for adding this problem and creating all test cases.


Update on 1/28/16:
BFS by removing the trailing "null" node strings.
One advantage of using BFS is we could safely removing the trailing last-level null nodes represented by the "#," string. This can save about half space (The # nodes in last-level of a binary tree is around half of the total number of trees). 

Code (Java):
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        StringBuffer sb = new StringBuffer();
        
        while (!queue.isEmpty()) {
            TreeNode curr = queue.poll();
            if (curr != null) {
                sb.append(curr.val + ",");
                queue.offer(curr.left);
                queue.offer(curr.right);
            } else {
                sb.append("#" + ",");
            }
        }
        
        // Remove the trailing #
        String result = sb.toString();
        int j = result.length() - 1;
        
        while (j > 0 && result.charAt(j) == ',' && result.charAt(j) == '#') {
            j -= 2;
        }
        
        result = result.substring(0, j);
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        String[] nodes = data.split(",");
        
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        queue.offer(root);
        int i = 1;

        while (!queue.isEmpty() && i < nodes.length) {
            TreeNode curr = queue.poll();
            if (nodes[i].equals("#")) {
                curr.left = null;
            } else {
                TreeNode leftNode = new TreeNode(Integer.parseInt(nodes[i]));
                curr.left = leftNode;
                queue.offer(leftNode);
            }
            
            i++;
            if (i >= nodes.length) {
                break;
            }
            
            // right node
            if (nodes[i].equals("#")) {
                curr.right = null;
            } else {
                TreeNode rightNode = new TreeNode(Integer.parseInt(nodes[i]));
                curr.right = rightNode;
                queue.offer(rightNode);
            }
            
            i++;
        }
        
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

DFS solution with using a Deque:
We can also solve the problem by using pre-order traversal of the binary tree. We need to use a deque because each time we need to remove one element from the top. Else we need to maintain a global index pointing to the current element we want to add into the tree.

Code (Java):
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        
        StringBuffer sb = new StringBuffer();
        serializeHelper(root, sb);
        
        return sb.toString();
    }
    
    private void serializeHelper(TreeNode root, StringBuffer sb) {
        if (root == null) {
            sb.append("#");
            sb.append(",");
            return;
        }
        
        sb.append(root.val + ",");
        serializeHelper(root.left, sb);
        serializeHelper(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        
        String[] strs = data.split(",");
        Deque<String> deque = new LinkedList<>(Arrays.asList(strs));
        
        return deserializeHelper(deque);
    }
    
    private TreeNode deserializeHelper(Deque<String> deque) {
        if (deque.isEmpty()) {
            return null;
        }
        
        String node = deque.removeFirst();
        if (node.equals("#")) {
            return null;
        }
        
        TreeNode root = new TreeNode(Integer.parseInt(node));
        root.left = deserializeHelper(deque);
        root.right = deserializeHelper(deque);
        
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

Another DFS without using a Deque, but a global index.
public class Solution2 {
    public String serialdfs(TreeNode root) {
        if (root == null) {
            return "";
        }
        
        StringBuilder sb = new StringBuilder();
        
        serialdfsHelper(root, sb);
        
        return sb.toString();
    }
    
    private void serialdfsHelper(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append("#");
            return;
        }
        
        sb.append(root.val);
        
        serialdfsHelper(root.left, sb);
        serialdfsHelper(root.right, sb);
    }
    
    public int i = 0;
    public TreeNode deserialdfs(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }
        
        return deserialdfsHelper(s);
    }
    
    private TreeNode deserialdfsHelper(String s) {
        if (i >= s.length() || s.charAt(i) == '#') {
            return null;
        }
        
        TreeNode root = new TreeNode(s.charAt(i) - '0');
        i++;
        root.left = deserialdfsHelper(s);
        i++;
        root.right = deserialdfsHelper(s);
        
        return root;
    }
    
    public static void main(String[] args) {
      Solution2 sol = new Solution2();

      TreeNode root = new TreeNode(1);
      root.left = new TreeNode(2);
      root.right = new TreeNode(3);
      root.left.left = new TreeNode(4);
      root.left.right = new TreeNode(5);


      String result = sol.serialdfs(root);
      
      TreeNode root2 = sol.deserialdfs(result);

      String result2 = sol.serialdfs(root2);

      System.out.println(result2);
    }
}

Compare between DFS and BFS:
I would like more BFS because BFS sometimes can save more space. For example,
      1
    /    \
   2    3
  / \    / \
 4 #  #  #
 / \ 
# #

By BFS: the serialized tree is 1,2,3,4
By DFS, the serialized tree is 1,2,4,#,#,#,3, which needs more space to store. 

Monday, October 26, 2015

Leetcode: Best Meeting Point

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.
For example, given three people living at (0,0)(0,4), and (2,2):
1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0
The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.
Hint:
  1. Try to solve it in one dimension first. How can this solution apply to the two dimension case?
Understand the problem:
http://segmentfault.com/a/1190000003894693

为了保证总长度最小,我们只要保证每条路径尽量不要重复就行了,比如1->2->3<-4这种一维的情况,如果起点是1,2和4,那2->31->2->3这两条路径就有重复了。为了尽量保证右边的点向左走,左边的点向右走,那我们就应该去这些点中间的点作为交点。由于是曼哈顿距离,我们可以分开计算横坐标和纵坐标,结果是一样的。所以我们算出各个横坐标到中点横坐标的距离,加上各个纵坐标到中点纵坐标的距离,就是结果了。
Code (Java):
public class Solution {
    public int minTotalDistance(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        
        List<Integer> rowIndex = new ArrayList<>();
        List<Integer> colIndex = new ArrayList<>();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    rowIndex.add(i);
                    colIndex.add(j);
                }
            }
        }
        
        int sum = 0;
        int mid = rowIndex.get(rowIndex.size() / 2);
        for (int x : rowIndex) {
            sum += Math.abs(x - mid);
        }
        
        Collections.sort(colIndex);
        mid = colIndex.get(colIndex.size() / 2);
        
        for (int y : colIndex) {
            sum += Math.abs(y - mid);
        }
        
        return sum;
    }
}

Leetcode: Flip Game II

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip twoconsecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.
Write a function to determine if the starting player can guarantee a win.
For example, given s = "++++", return true. The starting player can guarantee a win by flipping the middle "++" to become "+--+".
Follow up:
Derive your algorithm's runtime complexity.
Understand the problem:
At first glance, backtracking seems to be the only feasible solution to this problem. We can basically try every possible move for the first player (Let's call him 1P from now on), and recursively check if the second player 2P has any chance to win. If 2P is guaranteed to lose, then we know the current move 1P takes must be the winning move. The implementation is actually very simple:

Code (Java):
public class Solution {
    public boolean canWin(String s) {
        if (s == null || s.length() == 0) {
            return false;
        }
        
        char[] arr = s.toCharArray();
        
        return canWinHelper(arr);
    }
    
    private boolean canWinHelper(char[] arr) {
        int i = 0;
        
        for (i = 0; i < arr.length - 1; i++) {
            if (arr[i] == '+' && arr[i + 1] == '+') {
                arr[i] = '-';
                arr[i + 1] = '-';
                
               boolean win = !canWinHelper(arr);
                
                arr[i] = '+';
                arr[i + 1] = '+';
                
                if (win) {
                    return true;
                }
            }
        }
        
        return false;
    }
}


For most interviews, this is the expected solution. Now let's check the time complexity: Suppose originally the board of size N contains only '+' signs, then roughly we have:
T(N) = T(N-2) + T(N-3) + [T(2) + T(N-4)] + [T(3) + T(N-5)] + ... 
        [T(N-5) + T(3)] + [T(N-4) + T(2)] + T(N-3) + T(N-2)
     = 2 * sum(T[i])  (i = 3..N-2)
You will find that T(N) = 2^(N-1) satisfies the above equation. Therefore, this algorithm is at least exponential.

Update on 12/13/18:
class Solution {
    private Map<String, Boolean> map = new HashMap<>();
    public boolean canWin(String s) {
        if (s == null || s.length() == 0) {
            return false;
        }
        
        if (map.containsKey(s)) {
            return map.get(s);
        }
        
        char[] tokens = s.toCharArray();
        
        for (int i = 0; i < tokens.length - 1; i++) {
            if (tokens[i] == '+' && tokens[i + 1] == '+') {
                tokens[i] = '-';
                tokens[i + 1] = '-';
                
                boolean canWin = !canWin(new String(tokens));
                
                tokens[i] = '+';
                tokens[i + 1] = '+';
                
                if (canWin) {
                    map.put(new String(tokens), true);
                    return true;
                }
            }
        }
        
        map.put(new String(tokens), false);
        return false;
    }
}

Leetcode: Flip Game

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip twoconsecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.
Write a function to compute all possible states of the string after one valid move.
For example, given s = "++++", after one move, it may become one of the following states:
[
  "--++",
  "+--+",
  "++--"
]
If there is no valid move, return an empty list [].
Understand the problem:
The problem only asks for flipping "++" into "--", NOT -- to ++. So the solution is to move all consecutive "++" into "--".


Code (Java):
public class Solution {
    public List<String> generatePossibleNextMoves(String s) {
        List<String> result = new ArrayList<>();
        if (s == null || s.length() < 2) {
            return result;
        }
        
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == '+' && s.charAt(i + 1) == '+') {
                String s1 = s.substring(0, i);
                String s2 = "--";
                String s3 = s.substring(i + 2);
                String temp = s1 + s2 + s3;
                result.add(temp);
            }
        }
        
        return result;
    }
}

Leetcode: Nim Game

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.
For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.
Hint:
  1. If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
Naive Solution:
Simulate the process of the NIM game. Each time try to remove from 1 to 3 stones and go to the next round. 

Code (Java):
public class Solution {
    public boolean canWinNim(int n) {
        if (n <= 3) {
            return true;
        }
        
        return canWinNimHelper(n, 0);
    }
    
    private boolean canWinNimHelper(int n, int round) {
        if (round % 2 == 0 && n <= 3) {
            return true;
        } else if (round % 2 == 1 && n <= 3) {
            return false;
        }
        
        for (int i = 3; i >= 1; i--) {
            if (canWinNimHelper(n - i, round + 1)) {
                return true;
            }
        }
        
        return false;
    }
}

Analysis: 
It will get TLE error. There must be a clever way to solve this question. 

Better solution:
http://bookshadow.com/weblog/2015/10/12/leetcode-nim-game/

解题思路:

Nim游戏的解题关键是寻找“必胜态”。
根据题设条件:
当n∈[1,3]时,先手必胜。

当n == 4时,无论先手第一轮如何选取,下一轮都会转化为n∈[1,3]的情形,此时先手必负。

当n∈[5,7]时,先手必胜,先手分别通过取走[1,3]颗石头,可将状态转化为n == 4时的情形,此时后手必负。

当n == 8时,无论先手第一轮如何选取,下一轮都会转化为n∈[5,7]的情形,此时先手必负。
......
以此类推,可以得出结论:
当n % 4 != 0时,先手必胜;否则先手必负。

Code (Java):
public class Solution {
    public boolean canWinNim(int n) {
        return n % 4 > 0;
    }
}

Leetcode: Word Pattern II

Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.
Examples:
  1. pattern = "abab", str = "redblueredblue" should return true.
  2. pattern = "aaaa", str = "asdasdasdasd" should return true.
  3. pattern = "aabb", str = "xyzabcxzyabc" should return false.
Notes:
You may assume both pattern and str contains only lowercase letters.
Code (Java):
public class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        if ((pattern == null || pattern.length() == 0) && (str == null || str.length() == 0)) {
            return true;
        }
        
        if ((pattern == null || pattern.length() == 0) || (str == null || str.length() == 0)) {
            return false;
        }
        
        Map<Character, String> forwardMap = new HashMap<>();
        Map<String, Character> invertedMap = new HashMap<>();
        
        return wordPatternMatchHelper(0, pattern, 0, str, forwardMap, invertedMap);
    }
    
    private boolean wordPatternMatchHelper(int pStart, String pattern, 
                                      int sStart, String str, 
                                      Map<Character, String> forwardMap, 
                                      Map<String, Character> invertedMap) {
        if (pStart == pattern.length() && sStart == str.length()) {
            return true;
        }
        
        if (pStart >= pattern.length() || sStart >= str.length()) {
            return false;
        }
        
        char pChar = pattern.charAt(pStart);
        for (int i = sStart; i < str.length(); i++) {
            String curr = str.substring(sStart, i + 1);
            
            if ((!forwardMap.containsKey(pChar)) && (!invertedMap.containsKey(curr))) {
                forwardMap.put(pChar, curr);
                invertedMap.put(curr, pChar);
                
                if (wordPatternMatchHelper(pStart + 1, pattern, i + 1, 
                        str, forwardMap, invertedMap)) {
                    return true;
                }
                
                forwardMap.remove(pChar);
                invertedMap.remove(curr);
            } else if (forwardMap.containsKey(pChar) && invertedMap.containsKey(curr)) {
                String dict = forwardMap.get(pChar);
                char pCharDict = invertedMap.get(curr);
                
                // IMPORTANT !! If not equal, instead of returnning false immedidately,
                // We need to try other longer substrings. 
                if (!dict.equals(curr) || pCharDict != pChar) {
                    continue;
                }
                
                if (wordPatternMatchHelper(pStart + 1, pattern, i + 1, str, 
                        forwardMap, invertedMap)) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

Sunday, October 11, 2015

Leetcode: Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

Understand the problem:
The naive solution is to maintain a sliding window with size k, when we add an element nums[i], compare the nums[i] with each element in the window. If it is less or equal to t, return true. We return true because the distance between i and each element in the window must be less or equal to k. The complexity of this solution would be O(nk). 

We could use a treeSet to improve the complexity. The treeSet is essentially a balanced binary search tree. We put k elements in the treeSet, which is a sliding window. So when we insert an element to the treeSet, we need to remove one from the end. 

So the basic idea is for each element nums[i], we check if there is any element between [nums[i] - t, nums[i] + t]. If yes, return true.

Code (Java):
public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length <= 1 || k <= 0 || t < 0) {
            return false;
        }
        
        TreeSet<Integer> treeSet = new TreeSet<>();
        
        for (int i = 0; i < nums.length; i++) {
            Integer floor = treeSet.floor(nums[i] + t);
            Integer ceil = treeSet.ceiling(nums[i] - t);
            
            if ((floor != null && floor >= nums[i]) 
                || (ceil != null && ceil <= nums[i])) {
                return true;
            }
            
            treeSet.add(nums[i]);
            
            if (i >= k) {
                treeSet.remove(nums[i - k]);
            }
        }
        
        return false;
    }
}

Leetcode: Binary Tree Upside Down

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
For example:
Given a binary tree {1,2,3,4,5},
    1
   / \
  2   3
 / \
4   5
return the root of the binary tree [4,5,2,#,#,3,1].
   4
  / \
 5   2
    / \
   3   1  
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
Recursive solution:
The recursive solution could be bottom-up. Note that we need a parent node to save the node's parent. Also we use the return value just to store the new node. 

这个题的关键是反转以后的binary tree 的 root 是以前二叉树的 最左边的 leaf node. 利用这个性质,我们先一路走到最左边的那个leaf node, 并且记录一下当前节点和之前的parent node。找到这个节点以后,利用返回值一直把这个点传回来。在back tracking 的过程中,当前root 的 left child 是 parent.right. (注意要判断parent 是否为null)。如果parent == null, root.left = null; 如果没有这一句,树里面就有一个环!!root.right = parent

这个题的思路比较类似reverse linked list in recursive way. 

Code (Java):
/**
 * 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 upsideDownBinaryTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        
        return upsideDownBinaryTreeHelper(root, null);
    }
    
    private TreeNode upsideDownBinaryTreeHelper(TreeNode root, TreeNode parent) {
        if (root == null) {
            return parent;
        }
        
        TreeNode newNode = upsideDownBinaryTreeHelper(root.left, root);
        
        root.left = parent == null ? null : parent.right;
        root.right = parent;
        
        return newNode;
    }
}

Iterative solution:
这个属于自顶向下的方法。需要注意的是在向下走的过程中parent 其实已经被更新了,所以p.left 就不能指向parent.right, 因为 parent.right 已经在向下遍历的过程里面丢了!所以需要保存这个parent.right 这个node. 

/**
 * 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 upsideDownBinaryTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        
        TreeNode parent = null;
        TreeNode parentRightChild = null;
        TreeNode p = root;
        
        while (p != null) {
            TreeNode next = p.left;
            p.left = parentRightChild;
            parentRightChild = p.right;
            
            p.right = parent;
            
            parent = p;
            p = next;
        }
        
        return parent;
    }
}


Leetcode: Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
Hint:
  1. Beware of overflow.
Understand the problem:

Leetcode: Expression Add Operators

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +-, or * between the digits so they evaluate to the target value.
Examples: 
"123", 6 -> ["1+2+3", "1*2*3"] 
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

Understand the problem:
A classic DFS problem. 


Code (Java):
public class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> result = new ArrayList<>();
        
        if (num == null || num.length() == 0) {
            return result;
        }
        
        addOperatorHelper(num, 0, target, 0, 0, "", result);
        
        return result;
    }
    
    private void addOperatorHelper(String num, int start, int target, long curSum, 
                   long preNum, String curResult, List<String> result) {
        if (start == num.length() && curSum == target) {
            result.add(curResult);
            return;
        }
        
        if (start == num.length()) {
            return;
        }
        
        for (int i = start; i < num.length(); i++) {
            String curStr = num.substring(start, i + 1);
            if (curStr.length() > 1 && curStr.charAt(0) == '0') {
                break;
            }
            
            long curNum = Long.parseLong(curStr);
            
            if (curResult.isEmpty()) {
                addOperatorHelper(num, i + 1, target, curNum, curNum, curStr, result);
            } else {
                // Multiply
                addOperatorHelper(num, i + 1, target, curSum - preNum + preNum * curNum, 
                                  preNum * curNum, curResult + "*" + curNum, result);
                
                // Add
                addOperatorHelper(num, i + 1, target, curSum + curNum, curNum, 
                                  curResult + "+" + curNum, result);
                
                // Subtract
                addOperatorHelper(num, i + 1, target, curSum - curNum, -curNum, 
                                  curResult + "-" + curNum, result);
            }
        }
    }
}

Leetcode: Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Note:


  1. You must not modify the array (assume the array is read only).
  2. You must use only constant, O(1) extra space.
  3. Your runtime complexity should be less than O(n2).
  4. There is only one duplicate number in the array, but it could be repeated more than once.
Understand the problem:
The problem was simple if not comes with the constraints. Let's review the constraints. 
1. No change the array -- Otherwise, we could simply use the bucket sorting to put element i to A[i]. 
2. No extra memory -- Otherwise, we could use a hash map to count the freq of each number
3. Runtime complexity less than O(n^2) - Otherwise, we could use the brute-force solution to choose either 2 numbers and see if they are the same.

Solution:
Use binary search. 
http://www.cnblogs.com/grandyang/p/4843654.html

这道题给了我们n+1个数,所有的数都在[1, n]区域内,首先让我们证明必定会有一个重复数,这不禁让我想起了小学华罗庚奥数中的抽屉原理(又叫鸽巢原理), 即如果有十个苹果放到九个抽屉里,如果苹果全在抽屉里,则至少有一个抽屉里有两个苹果,这里就不证明了,直接来做题吧。题目要求我们不能改变原数组,即不能给原数组排序,又不能用多余空间,那么哈希表神马的也就不用考虑了,又说时间小于O(n2),也就不能用brute force的方法,那我们也就只能考虑用二分搜索法了,我们在区别[1, n]中搜索,首先求出中点mid,然后遍历整个数组,统计所有小于等于mid的数的个数,如果个数大于mid,则说明重复值在[mid+1, n]之间,反之,重复值应在[1, mid-1]之间,然后依次类推,知道搜索完成,此时的low就是我们要求的重复值,参见代码如下:

Code (Java):
public class Solution {
    public int findDuplicate(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int lo = 1;
        int hi = nums.length - 1;
        
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int count = countNumbers(nums, mid);
            
            if (count <= mid) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        
        return hi; // Or lo
    }
    
    private int countNumbers(int[] nums, int mid) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= mid) {
                count++;
            }
        }
        
        return count;
    }
}


Friday, October 9, 2015

Leetcode: Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.
Note: If the given node has no in-order successor in the tree, return null.
Brute-force solution: O(n)
The most straight-forward solution is to do a in-order traversal of the BST. When we found the target node, we look for the smallest number greater than the node.

Code (Java):
/**
 * 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 inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null || p == null) {
            return null;
        }
        
        if (p == root) {
            return p.right;
        }
        
        Stack<TreeNode> stack = new Stack<>();
        TreeNode q = root;
        
        while (!stack.isEmpty() || q != null) {
            if (q != null) {
                stack.push(q);
                q = q.left;
            } else {
                TreeNode curr = stack.pop();
                q = curr.right;
                
                if (curr == p) {
                    if (curr.right != null) {
                        TreeNode m = curr.right;
                        while (m.left != null) {
                            m = m.left;
                        }
                        return m;
                        
                    } else if (!stack.isEmpty()){
                        return stack.pop();
                    }
                }
            }
        }
        
        return null;
    }
}

An O(h) Solution:
Since the given p node is a node in the BST (not just a value), we can directly start from the node.  There are two cases to consider:
1. If the p.right != null. Then the successor of p must be the minimum number of the right subtree.
2. If the p.right == null, then the successor of p must be the minimum number which is greater than p's value. We could start from root, if the value of the root is greater than the p.val. Then we go to the left subtree because we wanna try a smaller one. However we need to save this node because it is possible that the root.left would be smaller than the p.val. If the root's val is less than the p.val, then we simply go to the right subtree. 

Code (Java):
/**
 * 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 inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null || p == null) {
            return null;
        }
        
        if (p.right != null) {
            return findMin(p.right);
        }
        
        // Case 2: p.right == null
        TreeNode succ = null;
        TreeNode q = root;
        
        while (q != null) {
            if (q.val > p.val) {
                succ = q;
                q = q.left;
            } else if (q.val < p.val) {
                q = q.right;
            } else {
                break;
            }
        }
        
        return succ;
    }
    
    private TreeNode findMin(TreeNode root) {
        TreeNode p = root;
        
        while (p.left != null) {
            p = p.left;
        }
        
        return p;
    }
}

Leetocde: Game of Life

ccording to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
  1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by over-population..
  4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Write a function to compute the next state (after one update) of the board given its current state.
Follow up
  1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
  2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
Understand the problem:
Since the problem asks for in-place solution. We could mark the 
 -- live-to-dead nodes as 2
 -- dead-to-live nodes as 3

In the second step, mark all 2 as 0 and 3 as 1

Code (Java):
public class Solution {
    public void gameOfLife(int[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        
        int m = board.length;
        int n = board[0].length;
        
        // If live to dead, mark 2
        // If dead to live, mark 3
        
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int liveNeighbors = getNumLiveNeighbors(i, j, board);
                
                if (board[i][j] == 1) {
                    if (liveNeighbors < 2 || liveNeighbors > 3) {
                        board[i][j] = 2;
                    }
                } else {
                    if (liveNeighbors == 3) {
                        board[i][j] = 3;
                    }
                }
            }
        }
        
        // Step 2: loop-over the board again and mark 2 as 0 and 3 as 1
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 2) {
                    board[i][j] = 0;
                } else if (board[i][j] == 3) {
                    board[i][j] = 1;
                }
            }
        }
    }
    
    private int getNumLiveNeighbors(int row, int col, int[][] board) {
        int result = 0;
        
        int m = board.length;
        int n = board[0].length;
        
        // Up
        if (row - 1 >= 0 && (board[row - 1][col] == 1 || board[row - 1][col] == 2)) {
            result += 1;
        }
        
        // Down
        if (row + 1 < m && (board[row + 1][col] == 1 || board[row + 1][col] == 2)) {
            result += 1;
        }
        
        // Left
        if (col - 1 >= 0 && (board[row][col - 1] == 1 || board[row][col - 1] == 2)) {
            result += 1;
        }
        
        // Right
        if (col + 1 < n && (board[row][col + 1] == 1 || board[row][col + 1] == 2)) {
            result += 1;
        }
        
        // NW
        if (row - 1 >= 0 && col - 1 >= 0 && (board[row - 1][col - 1] == 1 || board[row - 1][col - 1] == 2)) {
            result += 1;
        }
        
        // NE
        if (row - 1 >= 0 && col + 1 < n && (board[row - 1][col + 1] == 1 || board[row - 1][col + 1] == 2)) {
            result += 1;
        }
        
        // SW
        if (row + 1 < m && col - 1 >= 0 && (board[row + 1][col - 1] == 1 || board[row + 1][col - 1] == 2)) {
            result += 1;
        }
        
        // SE
        if (row + 1 < m && col + 1 < n && (board[row + 1][col + 1] == 1 || board[row + 1][col + 1] == 2)) {
            result += 1;
        }
        
        return result;
    }
}