DP good questions

(1) Maximal Rectangle (leetcode 85)
(2) Decode ways (leetcode 91)
(3) word break (leetcode 140) what if return one result. Similar, palindrome partition
(4) ugly number (leetcode 264)
(5) longest increasing sub-sequence (leetcode 300)
(6)Create max number(leetcode 321)
(7)Best time to buy and sell stock with cooldown(leetcode 309)
(8)Best time to buy and sell stock IV (leetcode 188)
(9)Maximum subarray III (lintcode 43)
(10) Minimum Adjust cost (lintcode 91)
(11) Backpack (lintcode 92), backpack II (lintcode 125)
(12) coins in a line II (lintcode 395)
(13) K - sum (lint code 89)
(14) Copy books (lintcode 437)
(15) Coins (cc189, 8.11, page 136)

Leetcode 298 Binary Tree Longest Consecutive Sequence

Given a binary tree, find the length of the longest consecutive sequence path.

The path refers to any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The longest consecutive path need to be from parent to child (cannot be the reverse).

For example,

   1
    \
     3
    / \
   2   4
        \
         5

Longest consecutive sequence path is 3-4-5, so return 3.

   2
    \
     3
    / 
   2    
  / 
 1

Longest consecutive sequence path is 2-3,not3-2-1, so return 2.
Solution 1: Simple DFS and keep tracking the consecutive sequence will solve it.

 public class Solution {  
   public int longestConsecutive(TreeNode root) {  
     if (root==null) return 0;  
     int[] res=new int[1];  
     dfs(root,1,res);  
     return res[0];  
   }  
   private void dfs(TreeNode x, int len, int[] res) {  
     res[0]=Math.max(res[0],len);  
     if (x.left!=null) {  
       if (x.left.val==x.val+1) dfs(x.left,len+1,res);  
       else dfs(x.left,1,res);  
     }  
     if (x.right!=null) {  
       if (x.right.val==x.val+1) dfs(x.right,len+1,res);  
       else dfs(x.right,1,res);  
     }  
   }  
 }  

Leetcode 297 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.

Solution 1: use recursive DFS, pre-order traversal.

 public class Codec {  
   // Encodes a tree to a single string.  
   public String serialize(TreeNode root) {  
     StringBuilder sb=new StringBuilder();  
     dfs(root,sb);  
     return sb.toString();  
   }  
   private void dfs(TreeNode x, StringBuilder sb) {  
     if (x==null) {  
       sb.append("null ");  
       return;  
     }  
     sb.append(String.valueOf(x.val));  
     sb.append(' ');  
     dfs(x.left,sb);  
     dfs(x.right,sb);  
   }  
   // Decodes your encoded data to tree.  
   public TreeNode deserialize(String data) {  
     String[] node=data.split(" ");  
     int[] d=new int[1];  
     return dfs(node,d);  
   }  
   private TreeNode dfs(String[] node, int[] d) {  
     if (node[d[0]].equals("null")) {  
       d[0]++;  
       return null;  
     }  
     TreeNode x=new TreeNode(Integer.valueOf(node[d[0]]));  
     d[0]++;  
     x.left=dfs(node,d);  
     x.right=dfs(node,d);  
     return x;  
   }  
 }  

Solution 2: Use iterative DFS, pre-order traversal.

 public class Codec {  
   // Encodes a tree to a single string.  
   public String serialize(TreeNode root) {  
     StringBuilder sb=new StringBuilder();  
     TreeNode x=root;  
     Deque<TreeNode> stack=new LinkedList<>();  
     while (x!=null || !stack.isEmpty()) {  
       if (x!=null) {  
         sb.append(String.valueOf(x.val));  
         sb.append(' ');  
         stack.push(x);  
         x=x.left;  
       }  
       else {  
         sb.append("null ");  
         x=stack.pop();  
         x=x.right;  
       }  
     }  
     return sb.toString();  
   }  
   // Decodes your encoded data to tree.  
   public TreeNode deserialize(String data) {  
     if (data.length()==0) return null;  
     String[] node=data.split(" ");  
     int n=node.length;  
     Deque<TreeNode> stack=new LinkedList<>();  
     TreeNode root=new TreeNode(Integer.valueOf(node[0]));  
     TreeNode x=root;  
     stack.push(x);  
     int i=1;  
     while (i<n) {  
       while (i<n && !node[i].equals("null")) {  
         x.left=new TreeNode(Integer.valueOf(node[i++]));  
         x=x.left;  
         stack.push(x);  
       }  
       while (i<n && node[i].equals("null")) {  
         x=stack.pop();  
         i++;  
       }  
       if (i<n) {  
         x.right=new TreeNode(Integer.valueOf(node[i++]));  
         x=x.right;  
         stack.push(x);  
       }  
     }  
     return root;  
   }  
 }  

Solution 3: Use BFS

 public class Codec {  
   // Encodes a tree to a single string.  
   public String serialize(TreeNode root) {  
     if (root==null) return "";  
     Queue<TreeNode> qu=new LinkedList<>();  
     StringBuilder sb=new StringBuilder();  
     qu.offer(root);  
     sb.append(String.valueOf(root.val));  
     sb.append(' ');  
     while (!qu.isEmpty()) {  
       TreeNode x=qu.poll();  
       if (x.left==null) sb.append("null ");  
       else {  
         qu.offer(x.left);  
         sb.append(String.valueOf(x.left.val));  
         sb.append(' ');  
       }  
       if (x.right==null) sb.append("null ");  
       else {  
         qu.offer(x.right);  
         sb.append(String.valueOf(x.right.val));  
         sb.append(' ');  
       }  
     }  
     return sb.toString();  
   }  
   // Decodes your encoded data to tree.  
   public TreeNode deserialize(String data) {  
     if (data.length()==0) return null;  
     String[] node=data.split(" ");  
     Queue<TreeNode> qu=new LinkedList<>();  
     TreeNode root=new TreeNode(Integer.valueOf(node[0]));  
     qu.offer(root);  
     int i=1;  
     while (!qu.isEmpty()) {  
       Queue<TreeNode> nextQu=new LinkedList<>();  
       while (!qu.isEmpty()) {  
         TreeNode x=qu.poll();  
         if (node[i].equals("null")) x.left=null;  
         else {  
           x.left=new TreeNode(Integer.valueOf(node[i]));  
           nextQu.offer(x.left);  
         }  
         i++;  
         if (node[i].equals("null")) x.right=null;  
         else {  
           x.right=new TreeNode(Integer.valueOf(node[i]));  
           nextQu.offer(x.right);  
         }  
         i++;  
       }  
       qu=nextQu;  
     }  
     return root;  
   }  
 }  

Leetcode 296 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.

Solution 1: best meeting point of one-dimension is at the middle point. for 2D is the same. find the mid-x and mid-y, it is the meeting place.

 public class Solution {  
   public int minTotalDistance(int[][] grid) {  
     int m=grid.length;  
     if (m==0) return 0;  
     int n=grid[0].length;  
     int[] row=new int[n];  
     int[] col=new int[m];  
     for (int i=0;i<m;i++) {  
       for (int j=0; j<n;j++) {  
         if (grid[i][j]==1) {  
           col[i]++;  
           row[j]++;  
         }  
       }  
     }  
     int res=0;  
     int i=0, j=n-1;  
     while (i<j) {  
       int min=Math.min(row[i],row[j]);  
       res+=min*(j-i);  
       if ((row[i]-=min)==0) i++;  
       if ((row[j]-=min)==0) j--;  
     }  
     i=0; j=m-1;  
     while (i<j) {  
       int min=Math.min(col[i],col[j]);  
       res+=min*(j-i);  
       if ((col[i]-=min)==0) i++;  
       if ((col[j]-=min)==0) j--;  
     }  
     return res;  
   }  
 }  

Leetcode 295 Find Median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples: 

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.

For example:

add(1)
add(2)
findMedian() -> 1.5
add(3) 
findMedian() -> 2

Solution 1: Use BST with size of sub-tree in the node will solve the question. add and find operation will be O(logn) complexity.

 class MedianFinder {  
   public class TreeNode {  
     private int val;  
     private int size;  
     private TreeNode left, right;  
     public TreeNode(int num) {  
       val=num;  
       size=1;  
     }  
   }  
   private TreeNode root=null;  
   // Adds a number into the data structure.  
   public void addNum(int num) {  
     root=addNum(root, num);  
   }  
   private TreeNode addNum(TreeNode x, int num) {  
     if (x==null) return new TreeNode(num);  
     x.size++;  
     if (num>x.val) x.right=addNum(x.right,num);  
     if (num<x.val) x.left=addNum(x.left,num);  
     return x;  
   }  
   // Returns the median of current data stream  
   public double findMedian() {  
     int n=root.size;  
     if (n%2==1) return find(root,n/2+1);  
     return (double)(find(root,n/2)+find(root,n/2+1))/2;  
   }  
   private int find(TreeNode x, int k) {  
     if (size(x.left)>=k) return find(x.left,k);  
     if (x.size-size(x.right)<k) return find(x.right,k-x.size+x.right.size);  
     return x.val;  
   }  
   private int size(TreeNode x) {  
     if (x==null) return 0;  
     return x.size;  
   }  
 }  

Leetcode 294 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.

Solution 1: DFS, complexity is O(n!), pay attention to the comments in below code

 public class Solution {  
   public boolean canWin(String s) {  
     char[] c=s.toCharArray();  
     return canWin(c);  
   }  
   private boolean canWin(char[] c) {  
     int n=c.length;  
     for (int i=1; i<n; i++) {  
       if (c[i-1]=='+' && c[i]=='+') {  
         c[i-1]='-'; c[i]='-';  
         boolean win=true;  
         if (canWin(c)) win=false;  
         c[i-1]='+';c[i]='+';  
         if (win) return true;//return must be after change back to '+'  
       }  
     }  
     return false;  
   }  
 }  

Leetcode 293 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 [].

Solution 1:  easy

 public class Solution {  
   public List<String> generatePossibleNextMoves(String s) {  
     char[] c=s.toCharArray();  
     int n=c.length;  
     List<String> res=new ArrayList<>();  
     for (int i=1; i<n; i++) {  
       if (c[i]=='+' && c[i-1]=='+'){  
         c[i]='-';   
         c[i-1]='-';  
         res.add(new String(c));  
         c[i]='+';  
         c[i-1]='+';  
       }  
     }  
     return res;  
   }  
 }