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;  
   }  
 }  

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

Solution 1: if n%4!=0, you move to 4x for your friend, no matter what your friend move, next step you move 4-step(your friend) till win.

 public class Solution {  
   public boolean canWinNim(int n) {  
     return n%4!=0;  
   }  
 }  

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

Solution 1: Use back tracking.

 public class Solution {  
   public boolean wordPatternMatch(String pattern, String str) {  
     Map<Character,String> map1=new HashMap<>();  
     Map<String,Character> map2=new HashMap<>();  
     if (str.length()<pattern.length()) return false;  
     return dfs(map1,map2,pattern,str,0,0);  
   }  
   private boolean dfs(Map<Character,String> map1, Map<String,Character> map2, String pattern, String str, int i, int j) {  
     if (i==pattern.length() && j==str.length()) return true;  
     if (i==pattern.length() || j==str.length()) return false;  
     char c=pattern.charAt(i);  
     if (map1.containsKey(c)) {  
       String s=map1.get(c);  
       int len=s.length();  
       if (j+len>str.length()) return false;  
       if (!s.equals(str.substring(j,j+len))) return false;  
       return dfs(map1,map2,pattern,str,i+1,j+len);  
     }  
     else {  
       for (int k=j+1; k<=str.length(); k++) {  
         String s=str.substring(j,k);  
         if (map2.containsKey(s)) continue;  
         map1.put(c,s);  
         map2.put(s,c);  
         if (dfs(map1,map2,pattern,str,i+1,k)) return true;  
         map1.remove(c);  
         map2.remove(s);  
       }  
       return false;  
     }  
   }  
 }  

Leetcode 290 Word Pattern

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 word in str.

Examples:

1. pattern = "abba", str = "dog cat cat dog" should return true.
2. pattern = "abba", str = "dog cat cat fish" should return false.
3. pattern = "aaaa", str = "dog cat cat dog" should return false.
4. pattern = "abba", str = "dog dog dog dog" should return false.

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Solution 1: Use two hash map, compare last appearance of c and string.

 public class Solution {  
   public boolean wordPattern(String pattern, String str) {  
     int n=pattern.length();  
     String[] words=str.split(" ");  
     if (words.length!=n) return false;  
     Map<Character,Integer> mapChar=new HashMap<>();  
     Map<String,Integer> mapStr=new HashMap<>();  
     for (int i=0; i<n; i++) {  
       char c=pattern.charAt(i);  
       String s=words[i];  
       if (mapChar.containsKey(c)) {  
         if (mapStr.containsKey(s)) {  
           if (mapChar.get(c)>mapStr.get(s)) return false;  
           if (mapChar.get(c)<mapStr.get(s)) return false;  
         }  
         else return false;  
       }  
       else {  
         if (mapStr.containsKey(s)) return false;  
         else {  
           mapStr.put(s,i);  
           mapChar.put(c,i);  
         }  
       }  
     }  
     return true;  
   }  
 }  

Leetcode 289 Game of Life

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?

Solution 1: market 1->0 to be 2 and 0->1 to be 3, then it can be solved in place. Time complexity O(mn), space O(1).

 public class Solution {  
   public void gameOfLife(int[][] board) {  
     int m=board.length;  
     if (m==0) return;  
     int n=board[0].length;  
     for (int i=0; i<m; i++) {  
       for (int j=0; j<n; j++) {  
         int num=count(board,i,j,m,n);  
         if (board[i][j]==1) {  
           if (num<2 || num>3) board[i][j]=2;  
         }  
         else if (num==3) board[i][j]=3;  
       }  
     }  
     for (int i=0; i<m; i++) {  
       for (int j=0; j<n; j++) board[i][j]%=2;  
     }  
   }  
   private int count(int[][] board, int i, int j, int m, int n) {  
     int res=0;  
     for (int l=i-1; l<=i+1; l++) {  
       for (int t=j-1; t<=j+1; t++) {  
         if (l<0 || l>=m || t<0 || t>=n) continue;  
         if ((l!=i || t!=j) && (board[l][t]==1 || board[l][t]==2)) res++;  
       }  
     }  
     return res;  
   }  
 }  

Leetcode 288 Unique Word Abbreviation

An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations:

a) it                      --> it    (no abbreviation)

     1
b) d|o|g                   --> d1g

              1    1  1
     1---5----0----5--8
c) i|nternationalizatio|n  --> i18n

              1
     1---5----0
d) l|ocalizatio|n          --> l10n

Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word's abbreviation is unique if no other word from the dictionary has the same abbreviation.

Example: 

Given dictionary = [ "deer", "door", "cake", "card" ]

isUnique("dear") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true

Solution 1: Use HashMap

 public class ValidWordAbbr {  
   Map<String,Set<String>> map=new HashMap<>();  
   public ValidWordAbbr(String[] dictionary) {  
     for (String s: dictionary) {  
       String key=genShort(s);  
       if (map.containsKey(key)) map.get(key).add(s);  
       else {  
         Set<String> one=new HashSet<>();  
         one.add(s);  
         map.put(key,one);  
       }  
     }  
   }  
   public boolean isUnique(String word) {  
     String key=genShort(word);  
     if (!map.containsKey(key)) return true;  
     if (map.get(key).size()>1) return false;  
     if (map.get(key).contains(word)) return true;  
     return false;  
   }  
   private String genShort(String s) {  
     if (s.length()<=2) return s;  
     StringBuilder sb=new StringBuilder();  
     sb.append(s.charAt(0));  
     sb.append(String.valueOf(s.length()-2));  
     sb.append(s.charAt(s.length()-1));  
     return sb.toString();  
   }  
 }  

Solution 2: Do not really need to use Set<String>, can be slightly faster.

 public class ValidWordAbbr {  
   Map<String,String> map=new HashMap<>();  
   public ValidWordAbbr(String[] dictionary) {  
     for (String s: dictionary) {  
       String key=genShort(s);  
       if (map.containsKey(key)) {  
         if (s.equals(map.get(key))) continue;  
         map.put(key,"");  
       }  
       else map.put(key,s);  
     }  
   }  
   public boolean isUnique(String word) {  
     String key=genShort(word);  
     if (!map.containsKey(key)) return true;  
     return word.equals(map.get(key));  
   }  
   private String genShort(String s) {  
     if (s.length()<=2) return s;  
     StringBuilder sb=new StringBuilder();  
     sb.append(s.charAt(0));  
     sb.append(String.valueOf(s.length()-2));  
     sb.append(s.charAt(s.length()-1));  
     return sb.toString();  
   }  
 }  

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

Solution 1: Use binary search for number count. Give a range, [lo,hi], if the duplicate number is within the range, counter>hi-lo. It is O(nlogn) complexity

 public class Solution {  
   public int findDuplicate(int[] nums) {  
     int n=nums.length-1;  
     int lo=1, hi=n;  
     while (lo<hi) {  
       int mid=lo+(hi-lo)/2;  
       if (count(nums,lo,mid)>mid-lo+1) hi=mid;  
       else lo=mid+1;  
     }  
     return lo;  
   }  
   private int count(int[] nums, int lo, int hi) {  
     int res=0;  
     for (int x: nums) {  
       if (x>=lo && x<=hi) res++;  
     }  
     return res;  
   }  
 }  

Leetcode 286 Walls and Gates

You are given a m x n 2D grid initialized with these three possible values.

1. -1 - A wall or an obstacle.
2. 0 - A gate.
3. INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

Solution 1: Use BFS, store x*n+y in the queue for the node.

 public class Solution {  
   public void wallsAndGates(int[][] rooms) {  
     int m=rooms.length;  
     if (m==0) return;  
     int n=rooms[0].length;  
     Queue<Integer> q1=new LinkedList<>();  
     Queue<Integer> q2=new LinkedList<>();  
     for (int i=0; i<m; i++) {  
       for (int j=0; j<n; j++) {  
         if (rooms[i][j]==0) q1.offer(i*n+j);  
       }  
     }  
     int d=0;  
     while (!q1.isEmpty()) {  
       while (!q1.isEmpty()) {  
         int x=q1.poll();  
         int i=x/n, j=x%n;  
         helper(rooms,i+1,j,m,n,d,q2);  
         helper(rooms,i-1,j,m,n,d,q2);  
         helper(rooms,i,j+1,m,n,d,q2);  
         helper(rooms,i,j-1,m,n,d,q2);  
       }  
       Queue<Integer> temp=q1;  
       q1=q2;  
       q2=temp;  
       d++;  
     }  
   }  
   private void helper(int[][] rooms, int i, int j, int m, int n, int d, Queue<Integer> q2) {  
     if (i<0 || j<0 || i>=m || j>=n) return;  
     if (rooms[i][j]!=Integer.MAX_VALUE) return;  
     rooms[i][j]=d+1;  
     q2.offer(i*n+j);  
   }  
 }  

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

Solution 1: binary search the value>v

 public class Solution {  
   public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {  
     TreeNode x=root;  
     TreeNode res=null;  
     while (x!=null) {  
       if (x.val>p.val) {  
         res=x;  
         x=x.left;  
       }  
       else x=x.right;  
     }  
     return res;  
   }  
 }  

Leetcode 284 Peeking Iterator

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next().

---

Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.

You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

Solution 1: Use a buffer Integer to store current value for next()

 class PeekingIterator implements Iterator<Integer> {  
   private Integer v=null;  
   private Iterator<Integer> iterator;  
   public PeekingIterator(Iterator<Integer> iterator) {   
     this.iterator=iterator;  
     if (iterator.hasNext()) v=iterator.next();  
   }  
   public Integer peek() {  
     return v;  
   }  
   @Override  
   public Integer next() {  
     Integer res=v;  
     if (iterator.hasNext()) v=iterator.next();  
     else v=null;  
     return res;  
   }  
   @Override  
   public boolean hasNext() {  
     return v!=null;  
   }  
 }  

Leetcode 283 Move Zeroes

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

Solution 1: two pointer, move ahead non-zero value from j to i, when j reach n, set 0 to all element from i to end.

 public class Solution {  
   public void moveZeroes(int[] nums) {  
     int n=nums.length;  
     int i=0, j=0;  
     while (j<n) {  
       if (nums[j]==0) j++;  
       else nums[i++]=nums[j++];  
     }  
     while (i<n) nums[i++]=0;  
   }  
 }  

Leetcode 282 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 -> []

Solution 1: Use back Tracking, need to skip continuous zeros

 public class Solution {  
   public List<String> addOperators(String num, int target) {  
     List<String> res=new ArrayList<>();  
     if (num.length()==0) return res;  
     dfs(num,0,0,1,true,"",target,res);  
     return res;  
   }  
   private void dfs(String num, int d, long pre, long curr, boolean signPlus, String path, int target, List<String> res) {  
     int n=num.length();  
     for (int i=d+1; i<n; i++) {  
       if (num.charAt(d)=='0' && i>d+1) break;//if start with 0, can only be one digit  
       String s=num.substring(d,i);  
       long t=Long.valueOf(s);  
       dfs(num,i,pre,curr*t,signPlus,path+s+"*",target,res);//'*'  
       long nextPre=signPlus?pre+curr*t:pre-curr*t;  
       dfs(num,i,nextPre,1,true,path+s+"+",target,res);//'+'  
       dfs(num,i,nextPre,1,false,path+s+"-",target,res);//'-'  
     }  
     if (num.charAt(d)=='0' && n>d+1) return;//if start with 0, can only be one digit  
     String s=num.substring(d);  
     long t=Long.valueOf(s);  
     long total=signPlus?pre+curr*t:pre-curr*t;  
     if (total==target) res.add(path+s);  
   }  
 }  

Leetcode 281 Zigzag Iterator

Given two 1d vectors, implement an iterator to return their elements alternately.

For example, given two 1d vectors:

v1 = [1, 2]
v2 = [3, 4, 5, 6]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].

Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?

Clarification for the follow up question - Update (2015-09-18):
The "Zigzag" order is not clearly defined and is ambiguous for k > 2 cases. If "Zigzag" does not look right to you, replace "Zigzag" with "Cyclic". For example, given the following input:

[1,2,3]
[4,5,6,7]
[8,9]

It should return [1,4,8,2,5,9,3,6,7].
Solution 1: a simple design question.

 public class ZigzagIterator {  
   private int i, j;  
   private int n;  
   List<Integer> v1;  
   List<Integer> v2;  
   public ZigzagIterator(List<Integer> v1, List<Integer> v2) {  
     this.v1=v1;  
     this.v2=v2;  
     i=0;  
     j=0;  
     n=Math.max(v1.size(),v2.size());  
     if (v1.size()==0) i++;  
   }  
   public int next() {  
     int res=0;  
     if (i==0) {  
       res=v1.get(j);  
       if (j>=v2.size()) j++;  
       else i++;  
     }  
     else {  
       res=v2.get(j);  
       j++;  
       if (j<v1.size()) i=0;  
     }  
     return res;  
   }  
   public boolean hasNext() {  
     return j<n;  
   }  
 }  

Leetcode 280 Wiggle Sort

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].

Solution 1: simple iterate.

 public class Solution {  
   public void wiggleSort(int[] nums) {  
     int n=nums.length;  
     for (int i=0; i<n; i+=2) {  
       if (i+1<n && nums[i]>nums[i+1]) swap(nums,i,i+1);  
       if (i+2<n && nums[i+1]<nums[i+2]) swap(nums,i+1,i+2);  
     }  
   }  
   private void swap(int[] nums, int i, int j) {  
     int temp=nums[i];  
     nums[i]=nums[j];  
     nums[j]=temp;  
   }  
 }  

Leetcode 279 Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Solution 1: Use DP, O(n^3/2) solution

 public class Solution {  
   public int numSquares(int n) {  
     if (n<=0) return 0;  
     int[] dp=new int[n+1];  
     Arrays.fill(dp,Integer.MAX_VALUE);  
     for (int i=0; i<=n; i++) {  
       if (i==0) dp[i]=0;  
       else {  
         for (int j=1; j*j<=i; j++) {  
           dp[i]=Math.min(dp[i],1+dp[i-j*j]);  
         }  
       }  
     }  
     return dp[n];  
   }  
 }  

Leetcode 278 First Bad Version

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Solution 1: binary search.

 public class Solution extends VersionControl {  
   public int firstBadVersion(int n) {  
     int lo=1, hi=n;  
     while (lo<hi) {  
       int mid=lo+(hi-lo)/2;  
       if (isBadVersion(mid)) hi=mid;  
       else lo=mid+1;  
     }  
     return lo;  
   }  
 }