Monday, August 1, 2016

Serialize and deserialize binary tree -- Leetcode

Question:
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

Answer:
Method: Preorder and DFS!
public class Codec {
    private StringBuilder sb = new StringBuilder();
    private int index = 0;
   
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        index = 0;
        serialize(root, sb);
        return sb.toString();
    }

    public void serialize(TreeNode root, StringBuilder sb){
        //preorder and using '# ' for null node!
        if(root==null){
            sb.append("#,");
            return;
        }
       
        sb.append(root.val + ",");
       
        serialize(root.left, sb);
        serialize(root.right, sb);
        return;
    }
   
   
   
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data==null || data.length()==0){
            return null;
        }
        String[] strArr = data.split(",");
        return deserialize(strArr);
    }
   
   
    public TreeNode deserialize(String[] str){
        if(index >= str.length){
            return null;
        }
       
        String str_val = str[index];
       
        if(str_val.equals("#")){
            index++;
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(str_val));
        index++;
        root.left = deserialize(str);
        root.right = deserialize(str);
        return root;
    }
}

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

Sunday, July 31, 2016

Flatten Binary Tree to Linked List -- Leetcode

Question:
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
         1
        / \
       2   5
      / \   \
     3   4   6
The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Answer:
Method 1: Recursive 1!

public class Solution {
    public void flatten(TreeNode root) {
        if(root == null)return;
        DFS(root);
        return;
    }
 
    public TreeNode DFS(TreeNode root){
        if(root == null)return null;
        TreeNode right = root.right;
        TreeNode left = root.left;
        TreeNode ret = root;
     
        if(left != null){
            root.right = root.left;
            root.left = null;
            TreeNode leftLastNode = DFS(left);
            ret = leftLastNode;
            leftLastNode.right = right;
            leftLastNode.left = null;
        }
        if(right!=null){
            TreeNode rightLastNode = DFS(right);
            ret = rightLastNode;
        }
        return ret;
    }
}

Recursive 2!
public class Solution {
    public void flatten(TreeNode root) {
        if(root == null)return;
        DFS(root);
        return;
    }
   
    public void DFS(TreeNode root){
        if(root == null)return;
        TreeNode left = root.left;
        TreeNode right = root.right;
     
        DFS(left);
        DFS(right);
       
        if(left != null){
            root.right = left;
            root.left = null;
            TreeNode p = left;
            while(p.right != null){
                p = p.right;
            }
            p.right = right;
            p.left = null;
        }
        return;
    }
}


Method 2: Iterative O(N) time and O(1) space! 
public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            return;
        }
        while (root != null) {
            if (root.left == null) {
                root = root.right;
                continue;
            }
            TreeNode left = root.left;
            while (left.right != null) {
                left = left.right;
            }
            left.right = root.right;
            root.right = root.left;
            root.left = null;
            root = root.right;
        }
    }


Follow up: Convert to inorder double linkedlist!
//Inorder Double LL!
    public void convertToDoubleLinkedList(TreeNode root) {
        if (root == null) {
            return;
        }
        
        if (root.left != null) {
            TreeNode left = root.left;
            convertToDoubleLinkedList(left);
            //find end node of left subtree!
            while (left.right != null) {
                left = left.right;
            }
            //inorder!
            left.right = root;
            root.left = left;
        }
        
        if (root.right != null) {
            TreeNode right = root.right;
            convertToDoubleLinkedList(right);
            while (right.left != null) {
                right = right.left;
            }
            right.left = root;
            root.right = right;
        }

    }


Thursday, July 21, 2016

Decompress String / Turtle Direction

Question:
让设计一个机器人,实现前进,向右转以及输出当前位置的功能(面经题,之前是乌龟来着),一开始在原点坐标,不能去负的坐标,去的话报错。
follow1:输入指令,如 FFRRF3R,F就是前进,R就是向右转,2R就是RRR。输出这个指令之后所处的位置。
follow2:在指令里面会出现2(FFR)这种情况,就是FFRFFR。

类似:
然后是那道以前出现过的3[abc2[x]]解码变成abcxxabcxxabcxx。说明了原字符串不会有数字出现.

Answer:
public class TurtleDirection {
//3[abc2[x]] :解码变成abcxxabcxxabcxx
/* Simple version:
  public String depressStr(String str, int start){
  String res = "";
  int digit = 0;

  for(int i=start;i<str.length();i++){
  if(Character.isDigit(str.charAt(i))){
   digit = digit*10 + str.charAt(i) - '0';
  }else if(str.charAt(i) >= 'a' && str.charAt(i) <= 'z'){
res += str.charAt(i);
  }else if(str.charAt(i) == '['){
  String nextLevelStr = depressStr(str, i+1);

  for(int k=0;k<digit;k++){
  res += nextLevelStr;
  }
  //!important!
  break;
  }else if(str.charAt(i) == ']'){

  }
  }
  return res;
  }
 */

//变种: 3[abc2[x]d]ef :解码变成abcxxdabcxxdabcxxdef
//1.Recursive:
   public String depressStr(String str, int start){
  String res = "";
  int digit = 0;
  int count = 0;

  for(int i=start;i<str.length();i++){
  if(Character.isDigit(str.charAt(i))){
  if(count==0){
      digit = digit*10 + str.charAt(i) - '0';
  }
  }else if(str.charAt(i) >= 'a' && str.charAt(i) <= 'z'){
  if(count==0){
  res += str.charAt(i);
  }
  }else if(str.charAt(i) == '['){
  if(count==0){
  String nextLevelStr = depressStr(str, i+1);
  for(int k=0;k<digit;k++){
  res += nextLevelStr;
  }
  }
  count++;
  }else if(str.charAt(i) == ']'){
  //if ']' is matched the '[' level, important recursive end here!
  if(count == 0){
  return res;
  }
  count--;
  }
  }

  return res;
   }


   //2. Using Stack! No recursive!
   //3[abc2[x]] :解码变成abcxxabcxxabcxx or  3[abc2[x]d]ef :解码变成abcxxdabcxxdabcxxdef
/*
 public String depressStr(String str){
         Stack<String> strStack = new Stack<>();
 Stack<Integer> numStack = new Stack<>();

         String currLevelStr = "";
int digit = 0;

for(int i=0;i<str.length();i++){
  if(Character.isDigit(str.charAt(i))){
      digit = digit*10 + str.charAt(i) - '0';
  }else if(str.charAt(i) >= 'a' && str.charAt(i) <= 'z'){
  currLevelStr += str.charAt(i);
  }else if(str.charAt(i) == '['){
                   strStack.add(currLevelStr);
                   numStack.add(digit);

                   currLevelStr = "";
                   digit = 0;
  }else if(str.charAt(i) == ']'){
   int currLevelNum = numStack.pop();
   String tmp = strStack.pop();
 
   if(currLevelNum != 0){
    for(int k=0;k < currLevelNum;k++){
tmp += currLevelStr;
}
   }else{
    tmp += currLevelStr;
   }
   currLevelStr = tmp;
  }
  }

  return currLevelStr;
}
*/

public static void main(String[] args) {
// TODO Auto-generated method stub
        TurtleDirection obj = new TurtleDirection();
        //String str = "3[abc2[x]]";
        String str = "3[abc2[x]d]ef";
        System.out.println(obj.depressStr(str,0));
}
}

Wednesday, July 20, 2016

Two Players Fetch Number -- dp

Question:
 给一个数组,A, B轮流从头尾处选出一个数字,求当B使用:
 * 1)贪心
 * 2)最优策略时,
 * A能取到所有数字之和最大。

Answer:
1. Player B uses greedy method to fetch number:
Example: B采用的是GREEDY方法
* 也就是B一定是取头、尾里面最大的那一个。 问A能取到的最大值。比如说2 4 7 3,A可以先取3, B肯定取7,A再取4,B取2,
* 这样A取到的和是7。 另外就是A先取2, B只能在3和4里面选 B因为是GREEDY 所以肯定选4, 那么A就能取7,这样A取到的和是9。
* 9>7所以返回9. 假定unique.

public int maxPick(int[] nums) {
if (nums == null || nums.length == 0)
throw new IllegalArgumentException("Empty array is not valid.");

int n = nums.length;
int[][] dp = new int[n][n];

for (int k = 2; k <= n; k += 2) {
for (int i = 0; i <= n - k; i++) {
int j = i + k - 1;
                                //edge case
if (k == 2) {
dp[i][j] = Math.max(nums[i], nums[j]);
continue;
}
                                //DP general case
int res1 = nums[i];
int res2 = nums[j];
// for res1, A fetches left element nums[i] firstly!
if (nums[i + 1] > nums[j]) {
res1 += dp[i + 2][j];
} else {
res1 += dp[i + 1][j - 1];
}
// for res2, A fetches right element nums[j] firstly!
if (nums[i] > nums[j - 1]) {
res2 += dp[i + 1][j - 1];
} else {
res2 += dp[i][j - 2];
}
dp[i][j] = Math.max(res1, res2);
}
}
return dp[0][n - 1];
}


2. Player B uses same optimized strategy like Player A to fetch number:
// 2. DP: dp[i,j] = max(v[i] + min (dp[i+2,j], dp[i+1,j-1]), v[j] + min(dp[i,j-2], dp[i+1,j-1]));
//Example: [2 4 7 3]
//2+7 = 9, selected!
//3+4 = 7

public int maxPick(int[] nums) {
if (nums == null || nums.length == 0)
throw new IllegalArgumentException("Empty array is not valid.");

int n = nums.length;
int[][] dp = new int[n][n];

for (int k = 2; k <= n; k += 2) {
for (int i = 0; i <= n - k; i++) {
int j = i + k - 1;
//edge case!
if (k == 2) {
dp[i][j] = Math.max(nums[i], nums[j]);
continue;
}
int res1 = nums[i];
int res2 = nums[j];
// for res1, A fetches nums[i] firstly
res1 += Math.min(dp[i+2][j], dp[i+1][j-1]);
// for res2, A fetches nums[j] firstly
res2 += Math.min(dp[i][j-2], dp[i+1][j-1]);
dp[i][j] = Math.max(res1, res2);
}
}
            return dp[0][n - 1];

}


Tuesday, July 19, 2016

Game of Life -- Leetcode

Question:
According 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?
Answer:
Mehod: Using 2 bit record both old and new states of board, In-place!
public class Solution {
    //1. 01 --> 01, n<=1
    //2. 01 --> 11, n=2 or 3
    //3. 01 --> 01, n>3
    //4. 00 --> 10, n=3
    public void gameOfLife(int[][] board) {
        if(board==null || board.length==0 || board[0]==null || board[0].length==0)return;
        int m = board.length;
        int n = board[0].length;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                int num = liveNeighborsNum(board, i, j);
               
                if(board[i][j] == 0){
                    if(num == 3){
                        board[i][j] = 2;
                    }
                }else if(board[i][j] == 1){
                    if(num == 2 || num == 3){
                        board[i][j] = 3;
                    }
                }
            }
        }
       
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                //only count 2rd bit which records new board state!
                board[i][j] >>= 1;
            }
        }
        return;
    }
   
    public int liveNeighborsNum(int[][] board, int i, int j){
        int m = board.length;
        int n = board[0].length;
        int res = 0;
        for(int x = i-1;x<=i+1;x++){
            for(int y = j-1;y<=j+1;y++){
                if(x<0 || x>=m || y<0 || y>=n){
                    continue;
                }
                //only count rightmost 1st bit which records old board state!
                if(!(x==i && y==j)){
                    res += board[x][y] & 1;
                }
            }
        }
        return res;
    }
}

Word Pattern II -- Leetcode

Question:
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-emptysubstring 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.
Answer:
Method: Recursive + Backtrack!
public class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        Map<Character, String> hmap = new HashMap<Character, String>();
        Set<String> set = new HashSet<String>();
        return Util(pattern, str, 0, 0, hmap, set);
    }
    
    public boolean Util(String pattern, String str, int startP, int startS, Map<Character, String> hmap, Set<String> set){
        if(startP == pattern.length() && startS == str.length()){
            return true;
        }else if(startP == pattern.length() && startS != str.length()){
            return false;
        }else if(startP != pattern.length() && startS == str.length()){
            return false;
        }
        
        char pChar = pattern.charAt(startP);
        //case 1
        if(hmap.containsKey(pChar)){
            String tmp = hmap.get(pChar);
            if(startS + tmp.length() - 1 < str.length()){
                String curr = str.substring(startS, startS + tmp.length());
                if(curr.equals(tmp)){
                    return Util(pattern, str, startP+1, startS + tmp.length(), hmap, set);
                }else{
                    return false;
                }
            }else{
                return false;
            }
        }
        
        //case 2
        for(int i=startS; i<str.length(); i++){
            String tmp = str.substring(startS, i+1);
            if(!set.contains(tmp)){
                hmap.put(pChar, tmp);
                set.add(tmp);
                if(Util(pattern, str, startP+1, i+1, hmap, set)){
                    return true;
                }
                hmap.remove(pChar);
                set.remove(tmp);
            }
        }
        return false;
    }
}

Monday, July 18, 2016

Expression Add Operators -- Leetcode

Question:
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 -> []

Answer:
Method: DFS!
public class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<String>();
        Util(res, "", num, 0, target, 0, 0);
        return res;
    }
 
    public void Util(List<String> res, String path, String num, int start, int target, long eval, long lastNum){
        //come to string end!
        if(start == num.length()){
            if(eval == target){
                res.add(path);
            }
        }
     
        for(int i=start;i<num.length();i++){
            if(num.charAt(start)=='0' && i!=start){
                //jump out directly.As no 0xxx number!
                break;
            }
 
            long currNum = Long.parseLong(num.substring(start, i+1));
            //Process the first parsed number!
            if(start == 0){
                Util(res, path + currNum, num, i+1, target, eval + currNum, currNum);
            }else{
                Util(res, path + "+" + currNum, num, i+1, target, eval + currNum, currNum);
                Util(res, path + "-" + currNum, num, i+1, target, eval - currNum, -currNum);
                //Only * used lastNum which comes after last "+/-"!
                Util(res, path + "*" + currNum, num, i+1, target, eval - lastNum + currNum * lastNum, currNum * lastNum);
            }
        }
        return;
    }
}