Cube Sum (HashMap)

Question: Please write a function that would print all positive numbers smaller than n that can be expressed as the sum of two cubes in two different ways. Bonus: calculate the complexity of that function.
For example, 1729 is one such number because 1729 = 1^3 + 12^3 = 9^3 + 10^3.

Idea: Binary search to find the ceiling(power(n,1/3)), then from 0 to the ceiling, we find calculate i^3+j^3, where j is from i+1 to the ceiling and store all the sum in a hashmap<sum, times appeared>. If any sum value shows up more than once, append to the result.
I would suggest not to use math.power(n, 1.0/3), since math.pow(64,1.0/3)=3.99999996.
"Output" is a class I wrote for printing my own tests, the function is just to print a list of integers if the input is not null. If the List<Integer> is null, print an "\n".

Time: O(n^2/3) Space: O(n^2/3)

Code:

 public class CubeSum {  
      public CubeSum()  
      {  
           int n1=1;  
           int n2=7;  
           int n3=8;  
           int n4=26;  
           int n5=27;  
           int n6=29;  
           int n7=1729;  
           int n8=30000;  
           Output.printList(getCubeNumbers(n1));  
           Output.printList(getCubeNumbers(n2));  
           Output.printList(getCubeNumbers(n3));  
           Output.printList(getCubeNumbers(n4));  
           Output.printList(getCubeNumbers(n5));  
           Output.printList(getCubeNumbers(n6));  
           Output.printList(getCubeNumbers(n7));  
           Output.printList(getCubeNumbers(n8));  
      }  
      public List<Integer> getCubeNumbers(int n)  
      {  
           List<Integer> result=new ArrayList<Integer>();  
           int start=0;  
           int end=cubeRootUp(n);  
           HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();  
           for(int i=start;i<end;i++)  
           {  
                for(int j=i+1;j<=end;j++)  
                {  
                     int cube=i*i*i+j*j*j;  
                     if(cube<=n&&map.containsKey(cube))  
                          map.put(cube, map.get(cube)+1);  
                     else  
                          map.put(cube, 1);  
                }  
           }  
           for(int key:map.keySet())  
           {  
                if(map.get(key)>1)  
                     result.add(key);  
           }  
           return result;  
      }  
      public int cubeRootUp(int x)  
      {  
           long y=(long)x;  
           long left=0;  
           long right=x/3;  
           while(left<=right)  
           {  
                long mid=(left+right)/2;  
                long cube=mid*mid*mid;  
                if(cube==y)  
                     return (int)mid;  
                if(cube<x)  
                     left=mid+1;  
                else  
                     right=mid-1;  
           }  
           return (int)left;  
      }  
 }  

Repeated DNA Sequences (LeetCode Bit Manipulation)

Question: All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
For example,
Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
Return:
["AAAAACCCCC", "CCCCCAAAAA"].

Idea: Create a HashMap<bit representation of substring, appeared times>. For each 10 letter window, calculate its bit representation as the key. Then slide the window from left to right, if the key shows up exactly twice, append the substring to the result.

Time: O(n) Space: O(n)

Code:

 public class Solution {  
   public List<String> findRepeatedDnaSequences(String s) {  
     List<String> result=new ArrayList<String>();  
     HashMap<Integer,Integer> computed=new HashMap<Integer,Integer>();  
     for(int i=0;i<=s.length()-10;i++)  
     {  
       String sub=s.substring(i,i+10);  
       int key=getKey(sub);  
       if(computed.containsKey(key))  
       {  
         computed.put(key,computed.get(key)+1);  
         if(computed.get(key)==2)  
           result.add(sub);  
       }  
       else  
         computed.put(key,1);  
     }  
     return result;  
   }  
   public int getKey(String s)  
   {  
     int result=0;  
     for(int i=s.length()-1;i>=0;i--)  
     {  
       int b=0;  
       switch(s.charAt(i))  
       {  
         case 'A':  
           b|=0;  
           break;  
         case 'T':  
           b|=1;  
           break;  
         case 'G':  
           b|=2;  
           break;  
         case 'C':  
           b|=3;  
           break;  
       }  
       result=b|result;  
       result=result<<2;  
     }  
     return result;  
   }  
 }  

Reverse Words in a String II (LeetCode String)

Question: Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.
The input string does not contain leading or trailing spaces and the words are always separated by a single space.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Could you do it in-place without allocating extra space?

Idea: Reverse twice, both in place.

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   public void reverseWords(char[] s) {  
     if(s==null||s.length==0)  
       return;  
     reverse(s,0,s.length-1);  
     for(int left=0;left<s.length;left++)  
     {  
       if(s[left]!=' ')  
       {  
         int right=left;  
         while(right<s.length&&s[right]!=' ')  
           right++;  
         reverse(s,left,right-1);  
         left=right;  
       }  
     }  
   }  
   public void reverse(char[] chars, int start,int end)  
   {  
     for(int i=start,j=end;i<j;i++,j--)  
     {  
       char tmp=chars[i];  
       chars[i]=chars[j];  
       chars[j]=tmp;  
     }  
   }  
 }  

Wildcard Matching (LeetCode Backtracking)

Question: Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

Idea: Backtracking. Use two pointers i, j to scan the two strings s, p respectively. If matches or s[i]=='?', push both pointers forward one step. If p[i]=='*', since '*' can match any number of letters, we first pretend this '*' never appears and try to match the next (as if '*' matches with 0 characters), if mismatch happens, go back to the '*' position to use the star to match the unmatched characters. If j reaches the end of p, but i has not, that means no mach. The same for the case when i reaches the end but j does not even if skip all the tailing '*'s.

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   public boolean isMatch(String s, String p) {  
     int i=0,j=0;  
     int star=-1;  
     int si=i;  
     while(i<s.length())  
     {  
       if(j<p.length())  
       {  
         if((p.charAt(j)=='?'||p.charAt(j)==s.charAt(i)))  
         {  
           i++;  
           j++;  
           continue;  
         }  
         if(p.charAt(j)=='*')  
         {  
           star=j++;  
           si=i;  
           continue;  
         }  
       }  
       if(star!=-1)  
       {  
         j=star+1;  
         i=++si;  
         continue;  
       }  
       return false;  
     }  
     while(j<p.length()&&p.charAt(j)=='*')  
       j+=1;  
     return j==p.length();  
   }  
 }  

Surrounded Regions (LeetCode Breadth-first Search)

Question: Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X

Idea: For each 'O' at boundary, do breadth-first search to mark the reachable block as '#'. Then scan the matrix and mark all non-'#' blocks as 'X' and '#' blocks as 'O'.

Time: O(n^2) Space: O(n^2)

Code:

 public class Solution {  
   public class Block{  
     int x;  
     int y;  
     public Block(int x,int y)  
     {  
       this.x=x;  
       this.y=y;  
     }  
   }  
   public void solve(char[][] board) {  
     if(board.length==0||board[0].length==0)  
       return;  
     int m=board.length;  
     int n=board[0].length;  
     for(int j=0;j<n;j++)  
     {  
       if(board[0][j]=='O')  
         bfs(board,0,j);  
       if(board[m-1][j]=='O')  
         bfs(board,m-1,j);  
     }  
     for(int i=0;i<m;i++)  
     {  
       if(board[i][0]=='O')  
         bfs(board,i,0);  
       if(board[i][n-1]=='O')  
         bfs(board,i,n-1);  
     }  
     for(int i=0;i<m;i++)  
     {  
       for(int j=0;j<n;j++)  
       {  
         if(board[i][j]=='#')  
           board[i][j]='O';  
         else  
           board[i][j]='X';  
       }  
     }  
   }  
   public void bfs(char[][] board,int startX,int startY)  
   {  
     int m=board.length;  
     int n=board[0].length;  
     Queue<Block> queue=new LinkedList<Block>();  
     queue.offer(new Block(startX,startY));  
     while(queue.isEmpty()==false)  
     {  
       int queueSize=queue.size();  
       for(int i=0;i<queueSize;i++)  
       {  
         Block cur=queue.poll();  
         if(board[cur.x][cur.y]=='O')  
         {  
           board[cur.x][cur.y]='#';  
           if(cur.x+1<m&&board[cur.x+1][cur.y]=='O')  
             queue.offer(new Block(cur.x+1,cur.y));  
           if(cur.x-1>=0&&board[cur.x-1][cur.y]=='O')  
             queue.offer(new Block(cur.x-1,cur.y));  
           if(cur.y+1<n&&board[cur.x][cur.y+1]=='O')  
             queue.offer(new Block(cur.x,cur.y+1));  
           if(cur.y-1>=0&&board[cur.x][cur.y-1]=='O')  
             queue.offer(new Block(cur.x,cur.y-1));  
         }  
       }  
     }  
   }  
 }  

Merge Intervals (LeetCode Sort)

Question: Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Idea: First sort the intervals according to their start point. Then use a variable to cache the previous interval and scan the list from left to right (ascending order). If the previous interval does not overlap with the current interval, append previous interval to the result, otherwise merge the previous interval and the current interval and store the new interval in the variable previous. When the loop is done, do not forget the last interval is not appended to result, since there is no current interval now.

Time: O(nlgn) Space: O(1)

Code:

 public class Solution {  
   public Comparator<Interval> comp=new Comparator<Interval>()  
   {  
     public int compare(Interval i1, Interval i2)  
     {  
       if(i1==null)  
         return 1;  
       else if(i2==null)  
         return -1;  
       else  
         return i1.start-i2.start;  
     }  
   };  
   public List<Interval> merge(List<Interval> intervals) {  
     if(intervals.size()<=1)  
       return intervals;  
     List<Interval> result=new ArrayList<Interval>();  
     Collections.sort(intervals,comp);  
     Interval pre=intervals.get(0);  
     for(int i=1;i<intervals.size();i++)  
     {  
       if(pre.end<intervals.get(i).start)  
       {  
         result.add(pre);  
         pre=intervals.get(i);  
       }  
       else  
       {  
         pre.start=Math.min(pre.start,intervals.get(i).start);  
         pre.end=Math.max(pre.end,intervals.get(i).end);  
       }  
     }  
     result.add(pre);  
     return result;  
   }  
 }  

Maximum Gap (LeetCode Sort)

Question: Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Try to solve it in linear time/space.
Return 0 if the array contains less than 2 elements.
You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

Idea: Bucket sort. Assume there are n elements, we construct n-1 buckets and put the n-2 elements (without the max and the min) into the bucket. For each bucket, we only keep the bucketMax and the bucketMin value. Due to pigeon hole theory, there must be at least one empty buckets. The potential max gap is on the two sides of the empty buckets.

Time: O(n) Space: O(n)

Code:

 public class Solution {  
   public int maximumGap(int[] num) {  
     if(num.length<2)  
       return 0;  
     int maxValue=num[0];  
     int minValue=num[0];  
     for(int i=0;i<num.length;i++)  
     {  
       maxValue=Math.max(maxValue,num[i]);  
       minValue=Math.min(minValue,num[i]);  
     }  
     if(maxValue==minValue)  
       return 0;  
     int numBucket=num.length-1;  
     int bucketSize=(int)Math.ceil(((double)(maxValue-minValue))/numBucket);  
     int[] bucketMax=new int[numBucket];  
     int[] bucketMin=new int[numBucket];  
     Arrays.fill(bucketMax,Integer.MIN_VALUE);  
     Arrays.fill(bucketMin,Integer.MAX_VALUE);  
     for(int i=0;i<num.length;i++)  
     {  
       if(num[i]==maxValue||num[i]==minValue)  
         continue;  
       int whichBucket=(num[i]-minValue)/bucketSize;  
       bucketMax[whichBucket]=Math.max(bucketMax[whichBucket],num[i]);  
       bucketMin[whichBucket]=Math.min(bucketMin[whichBucket],num[i]);  
     }  
     int maxGap=Integer.MIN_VALUE;  
     int pre=minValue;  
     for(int i=0;i<numBucket;i++)  
     {  
       if(bucketMax[i]==Integer.MIN_VALUE&&bucketMin[i]==Integer.MAX_VALUE)  
         continue;  
       maxGap=Math.max(maxGap,bucketMin[i]-pre);  
       pre=bucketMax[i];  
     }  
     maxGap=Math.max(maxGap,maxValue-pre);  
     return maxGap;  
   }  
 }  

Evaluate Reverse Polish Notation (LeetCode Stack)

Question: Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Idea: Use stack. Scan the input string array from left to right. If the current position is a number, push it to the stack, otherwise pop two numbers and apply the operator and push the result back to the stack. The last element in the stack is the final result.

Time: O(n) Space: O(n)

Code:

 public class Solution {  
   public int evalRPN(String[] tokens) {  
     Stack<Integer> stack=new Stack<Integer>();  
     for(int i=0;i<tokens.length;i++)  
     {  
       String s=tokens[i];  
       if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/"))  
       {  
         int second=stack.pop();  
         int first=stack.pop();  
         int result=0;  
         if(s.equals("+"))  
           result=first+second;  
         if(s.equals("-"))  
           result=first-second;  
         if(s.equals("*"))  
           result=first*second;  
         if(s.equals("/"))  
           result=first/second;  
         stack.push(result);  
       }  
       else  
         stack.push(Integer.parseInt(s));  
     }  
     return stack.pop();  
   }  
 }  

Word Ladder II (LeetCode Backtracking)

Question: Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
Return
  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Idea: Dijkstra's algorithm. Image the words as nodes and the ladder as edges, this is exactly a shortest path problem from the node start (source) to the node end (destination). Without the Boost library in C++, we need to a little bit patience to implement the Dijkstra's algorithm in Java.

First add the start and the end to the dictionary. Then use breadth-first search to flood from the start node to all the reachable nodes (even further than end nodes), and label the distance between the current node and the start node. At the same time, for each node, create single direction edges to its source.

After the flood, start from the end node to construct path to the start node, since the edges we constructed are single directional and are from destination to source. Assume the distance between the node and the start node is x, then the next hop y of this node should follow two conditions:
1) y is x's neighbor (has constructed edge)
2) distance[y=>start]==distance[x=>start]-1
So following these two rules, use depth-first search to construct the path until the start node is reached. Do not forget to reverse the paths constructed before output, since the requirement is source to destination.


Time: O(n^2) (The fastest implementation of Dijkstra's algorithm is O(e+vlgv))
Space: O(n^2)

Code:

 public class Solution {  
   public List<List<String>> findLadders(String start, String end, Set<String> dict) {  
     List<List<String>> result=new ArrayList<List<String>>();  
     if(dict==null||dict.size()==0)  
       return result;  
     HashMap<String,List<String>> graph=new HashMap<String,List<String>>();  
     HashMap<String, Integer> distance=new HashMap<String,Integer>();  
     dict.add(start);  
     dict.add(end);  
     bfs(graph,distance,start,end,dict);  
     List<String> path=new ArrayList<String>();  
     dfs(result,path,graph,distance,start,end);  
     return result;  
   }  
   public void dfs(List<List<String>> result,List<String> path, HashMap<String,List<String>> graph,HashMap<String,Integer> distance,String start,String cur)  
   {  
     path.add(cur);  
     if(path.contains(start))  
     {  
       Collections.reverse(path);  
       result.add(new ArrayList<String>(path));  
       Collections.reverse(path);  
     }  
     else  
     {  
       for(String next:graph.get(cur))  
       {  
         if(distance.containsKey(next)&&distance.get(cur)==distance.get(next)+1)  
         {  
           dfs(result,path,graph,distance,start,next);  
         }  
       }  
     }  
     path.remove(path.size()-1);  
   }  
   public void bfs(HashMap<String,List<String>> graph, HashMap<String,Integer> distance,String start, String end, Set<String> dict)  
   {  
     Queue<String> queue=new LinkedList<String>();  
     queue.offer(start);  
     distance.put(start,0);  
     for(String s:dict)  
     {  
       graph.put(s,new ArrayList<String>());  
     }  
     while(queue.isEmpty()==false)  
     {  
       String cur=queue.poll();  
       List<String> neighbors=getNeighbors(cur,dict);  
       for(String neighbor:neighbors)  
       {  
         graph.get(neighbor).add(cur);  
         if(distance.containsKey(neighbor)==false)  
         {  
           distance.put(neighbor,distance.get(cur)+1);  
           queue.offer(neighbor);  
         }  
       }  
     }  
   }  
   public List<String> getNeighbors(String cur, Set<String> dict)  
   {  
     List<String> result=new ArrayList<String>();  
     for(int i=0;i<cur.length();i++)  
     {  
       for(char c='a';c<='z';c++)  
       {  
         if(c!=cur.charAt(i))  
         {  
           String maybe=replaceCharAt(cur,i,c);  
           if(dict.contains(maybe))  
             result.add(maybe);  
         }  
       }  
     }  
     return result;  
   }  
   public String replaceCharAt(String s, int index, char c)  
   {  
     char[] chars=s.toCharArray();  
     chars[index]=c;  
     return new String(chars);  
   }  
 }  

Permutations II (LeetCode Backtracking)

Question: Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

Idea: Backtracking depth-first search. To avoid duplication, we first sort the array. Then the integers with the same value are placed at adjacent positions. For each recursive call, we only add the integer at the first unused position and is the first of the unused of the adjacent subarray with the same value.

Time: O(n!) Space: O(n)

Code:

 public class Solution {  
   public List<List<Integer>> permuteUnique(int[] num) {  
     List<List<Integer>> result=new ArrayList<List<Integer>>();  
     List<Integer> path=new ArrayList<Integer>();  
     Arrays.sort(num);  
     boolean[] used=new boolean[num.length];  
     dfs(result,path,num,used);  
     return result;  
   }  
   public void dfs(List<List<Integer>> result, List<Integer> path,int[] num,boolean[] used)  
   {  
     if(path.size()==num.length)  
     {  
       result.add(new ArrayList<Integer>(path));  
       return;  
     }  
     for(int i=0;i<num.length;i++)  
     {  
       if((i!=0&&num[i]==num[i-1]&&used[i-1]==false)||used[i]==true)  
         continue;  
       path.add(num[i]);  
       used[i]=true;  
       dfs(result,path,num,used);  
       used[i]=false;  
       path.remove(path.size()-1);  
     }  
   }  
 }  

Permutations (LeetCode Backtracking)

Question: Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Idea: Backtracking depth-first search. For each unused integer x, put it at the head of the permutation, mark x as used, then recursively construct the permutation from the rest of unused integers. When we roll back, do not forget to re-mark x to unused, since that x can be used at other positions in the future.

Time: O(n!) Space: O(n)

Code:

 public class Solution {  
   public List<List<Integer>> permute(int[] num) {  
     List<List<Integer>> result=new ArrayList<List<Integer>>();  
     List<Integer> path=new ArrayList<Integer>();  
     boolean[] used=new boolean[num.length];  
     dfs(result,path,num);  
     return result;  
   }  
   public void dfs(List<List<Integer>> result,List<Integer> path,int[] num)  
   {  
     if(path.size()==num.length)  
     {  
       result.add(new ArrayList<Integer>(path));  
       return;  
     }  
     for(int i=0;i<num.length;i++)  
     {  
       if(path.contains(num[i])==false)  
       {  
         path.add(num[i]);  
         dfs(result,path,num);  
         path.remove(path.size()-1);  
       }  
     }  
   }  
 }  

N-Queens II (LeetCode Backtracking)

Question: Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.


Idea: Backtracking depth-first search. Since we can only place one queen in each row, we place the queens row by row. For each row, we try to place the queen in each column, if the placement is safe, then place the queen and go to the next row. When we reach row==n (out of boundary), that means the rows from 0=>n-1 is valid, add 1 to the result

Time: O(n^n) Space: O(n^2)

Code:

 public class Solution {  
   int counter;  
   public int totalNQueens(int n) {  
     if(n==0)  
       return 0;  
     counter=0;  
     char[][] board=new char[n][n];  
     for(int i=0;i<n;i++)  
       Arrays.fill(board[i],'.');  
     dfs(board,0);  
     return counter;  
   }  
   public void dfs(char[][] board,int curRow)  
   {  
     int n=board.length;  
     if(curRow==n)  
     {  
       counter+=1;  
       return;  
     }  
     for(int j=0;j<n;j++)  
     {  
       board[curRow][j]='Q';  
       if(isValid(board,curRow,j))  
       {  
         dfs(board,curRow+1);  
       }  
       board[curRow][j]='.';  
     }  
   }  
   public boolean isValid(char[][] board,int x,int y)  
   {  
     int n=board.length;  
     for(int i=0;i<n;i++)  
     {  
       for(int j=0;j<n;j++)  
       {  
         if(i!=x||j!=y)  
         {  
           if(i==x&&board[i][j]=='Q')  
             return false;  
           if(j==y&&board[i][j]=='Q')  
             return false;  
           if((i+j==x+y||i-j==x-y)&&(board[i][j]=='Q'))  
             return false;  
         }  
       }  
     }  
     return true;  
   }  
 }  

N-Queens (LeetCode Backtracking)

Question: The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Idea: Brute force depth-first-search. First initial a char[][] filled with '.'s. For each row, we try to put a queen (set char[x][y]='Q') at any column. If it is valid (no conflict), place the queen then go to the next row. If we reach row==n (out of boundary), that means all the rows from 0=>n-1 are valid, append this assignment to the result.
For easier understanding, I wrote the check valid function in all the 8 directions separately: same row, same column, 2 diagonal, 2 counter- diagonal. The code presentation can be simplified by getting the distance to the boundaries first, but it will be a little bit harder to be understood. So I keep the a little bit longer but easier understood writing.

Time: O(n^n) Space: O(1)

Code:

 public class Solution {  
   public List<String[]> solveNQueens(int n) {  
     List<String[]> result=new ArrayList<String[]>();  
     if(n==0)  
       return result;  
     char[][] board=new char[n][n];  
     for(int i=0;i<n;i++)  
       Arrays.fill(board[i],'.');  
     dfs(result,board,0);  
     return result;  
   }  
   public void dfs(List<String[]> result,char[][] board,int curRow)  
   {  
     int n=board.length;  
     if(curRow==n)  
     {  
       result.add(toStringArray(board));  
       return;  
     }  
     for(int j=0;j<n;j++)  
     {  
       board[curRow][j]='Q';  
       if(isValid(board,curRow,j))  
       {  
         dfs(result,board,curRow+1);  
       }  
       board[curRow][j]='.';  
     }  
   }  
   public String[] toStringArray(char[][] board)  
   {  
     String[] result=new String[board.length];  
     for(int i=0;i<board.length;i++)  
     {  
       StringBuilder builder=new StringBuilder();  
       for(int j=0;j<board.length;j++)  
         builder.append(board[i][j]);  
       result[i]=builder.toString();  
     }  
     return result;  
   }  
   public boolean isValid(char[][] board, int x, int y)  
   {  
     int n=board.length;  
     for(int i=0;i<n;i++)  
     {  
       if(i!=x&&board[i][y]=='Q')  
         return false;  
     }  
     for(int j=0;j<n;j++)  
     {  
       if(j!=y&&board[x][j]=='Q')  
         return false;  
     }  
     for(int i=1;x+i<n&&y+i<n;i++)  
     {  
       if(board[x+i][y+i]=='Q')  
         return false;  
     }  
     for(int i=1;x-i>=0&&y-i>=0;i++)  
     {  
       if(board[x-i][y-i]=='Q')  
         return false;  
     }  
     for(int i=1;x-i>=0&&y+i<n;i++)  
     {  
       if(board[x-i][y+i]=='Q')  
         return false;  
     }  
     for(int i=1;x+i<n&&y-i>=0;i++)  
     {  
       if(board[x+i][y-i]=='Q')  
         return false;  
     }  
     return true;  
   }  
 }  

Gray Code (LeetCode Backtracking)

Question: The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2

Idea: Gray code was invented in 1947. There are many ways of generating gray code. I just listed two methods as following:
Method 1: by reflection, use n=3 as an example.
n=2 gray code:             00    01   11    10
reflect:                                                            10    11    01     00
add 0 before first half: 000  001  011  010
add 1 before 2nd half:                                   110  111  101  100
n=2 gray code:             000  001   011  010  110  111  101  100

Method 2: by bit manipulation from binary to gray.
gray code=(binary>>1)^binary

Time: O(n^n) for reflection, O(2^n) for bit manipulation.
Space: O(1)

Code by Reflection:

 public class Solution {  
   public List<Integer> grayCode(int n) {  
     List<Integer> result=new ArrayList<Integer>();  
     if(n<=1)  
     {  
       for(int i=0;i<=n;i++)  
         result.add(i);  
       return result;  
     }  
     result=grayCode(n-1);  
     List<Integer> reflected=reflect(result);  
     int x=1<<(n-1);  
     for(int i=0;i<reflected.size();i++)  
       reflected.set(i,reflected.get(i)+x);  
     result.addAll(reflected);  
     return result;  
   }  
   public List<Integer> reflect(List<Integer> old)  
   {  
     List<Integer> result=new ArrayList<Integer>();  
     for(int i=old.size()-1;i>=0;i--)  
       result.add(old.get(i));  
     return result;  
   }  
 }  

Code by Bit Manipulation:

 public class Solution {  
   public int binaryToGray(int x)  
   {  
     return (x>>1)^x;  
   }  
   public List<Integer> grayCode(int n) {  
     List<Integer> result=new ArrayList<Integer>();  
     for(int i=0;i<Math.pow(2,n);i++)  
       result.add(binaryToGray(i));  
     return result;  
   }  
 }  

Combinations (LeetCode Backtracking)

Question: Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Idea: Depth-first search. To avoid duplication, start from 1, then only add numbers bigger than all the current numbers to the set until the set size is k. Then collect all the combinations.

Time: O(n!) Space: O(n)

Code:

 public class Solution {  
   public List<List<Integer>> combine(int n, int k) {  
     List<List<Integer>> result=new ArrayList<List<Integer>>();  
     List<Integer> path=new ArrayList<Integer>();  
     dfs(result,path,1,n,k);  
     return result;  
   }  
   public void dfs(List<List<Integer>> result, List<Integer> path, int start, int end, int k)  
   {  
     if(k==path.size())  
     {  
       result.add(new ArrayList<Integer>(path));  
       return;  
     }  
     for(int i=start;i<=end;i++)  
     {  
       path.add(i);  
       dfs(result,path,i+1,end,k);  
       path.remove(path.size()-1);  
     }  
   }  
 }  

Gas Station (LeetCode Greedy)

Question: There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.

Idea: If the sum of the gas[] is larger than the sum of the cost[], the roundtrip can be fulfilled. However, the start point can not be anywhere, since partial of the trajectory may be quite "tough" (partial sum of cost> partial sum of gas). As said in Shelley's "Ode to the west wind", "If Winter comes, can Spring be far behind? ", we need to locate the end of the winter.

Start from a round point of the trip, we may face a series of continuous "tough" roads. However, since we know the round trip can be fulfilled, that means starting from the end of last "tough" roads we encountered, we can accomplish the whole trip, otherwise the whole trip can not be finished. This can be proved easily by contradiction.

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   public int canCompleteCircuit(int[] gas, int[] cost) {  
     int sum=0;  
     int total=0;  
     int breakPoint=-1;  
     for(int i=0;i<gas.length;i++)  
     {  
       sum+=gas[i]-cost[i];  
       total+=gas[i]-cost[i];  
       if(sum<0)  
       {  
         breakPoint=i;  
         sum=0;  
       }  
     }  
     if(total>=0)  
       return breakPoint+1;  
     else  
       return -1;  
   }  
 }  

Candy (LeetCode Greedy)

Question: There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Idea: Greedy. Without loss of generality, let us assume the minimum assignment to each child is 0 (we can easily add N at the end to fulfill the 1 candy restriction). Then from left to right, if the ratings are increasing monotonically, add 1 candy per index, otherwise start again from 0 candy. Now if we only look from the left to the right, the problem is solved. However, the assignment should also be valid from right to left. So we need to update the assignment from right to left to fulfill the right to left requirement. After the left-to-right assignment and the right-to-left adjustment, accumulate the number of candies and add N to the final result, since each child should have at least 1 candy.

Time: O(n) Space: O(n)

Code:

 public class Solution {  
   public int candy(int[] ratings) {  
     int n=ratings.length;  
     int[] count=new int[n];  
     for(int i=1;i<n;i++)  
     {  
       if(ratings[i]>ratings[i-1])  
         count[i]=count[i-1]+1;  
     }  
     for(int i=n-2;i>=0;i--)  
     {  
       if(ratings[i]>ratings[i+1]&&count[i]<=count[i+1])  
         count[i]=count[i+1]+1;  
     }  
     int sum=0;  
     for(int i=0;i<n;i++)  
       sum+=count[i];  
     return sum+n;  
   }  
 }  

Word Break II (LeetCode Dynamic Programming)

Question: Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].

Idea: Depth-first search with recursive dynamic programming. At each position of the input string s, break it to two halves, if the prefix is contained in the dict, recursively break the suffix to words. Use a hashmap to cache the broken strings computed before.

Time: O(n^2) Space: O(n^2)

Code:

 public class Solution {  
   public List<String> wordBreak(String s, Set<String> dict) {  
     HashMap<String,List<String>> map=new HashMap<String,List<String>>();  
     return dfs(s,dict,map);  
   }  
   public List<String> dfs(String s, Set<String> dict, HashMap<String,List<String>> map)  
   {  
     if(map.containsKey(s))  
       return map.get(s);  
     List<String> result=new ArrayList<String>();  
     int n=s.length();  
     if(n<=0)  
     {  
       map.put(s,result);  
       return result;  
     }  
     for(int i=1;i<=s.length();i++)  
     {  
       String prefix=s.substring(0,i);  
       if(dict.contains(prefix))  
       {  
         if(prefix.length()==s.length())  
           result.add(prefix);  
         else  
         {  
           String suffix=s.substring(i);  
           List<String> breakSuffix=dfs(suffix,dict,map);  
           for(String tmp:breakSuffix)  
             result.add(prefix+" "+tmp);  
         }  
       }  
     }  
     map.put(s,result);  
     return result;  
   }  
 }  

Word Break (Dynamic Programming)

Question: Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

Idea: Dynamic programming. Let dp[i] denotes from s[0]->s[i-1] can be partitioned, then dp[s.length()] is the result. For each position i, use all the words in the dict to "jump" where "jump" means if a word (assumes length x)contained in the dict matches a portion of the input string, set dp[i+x]=true. If we can finally reach the end of the input string, that means all the substrings along the way can be found in the dict.

Time: O(m*n) Space: O(m), where m is the length of the input string, n is the size of the dictionary.

Code:

 public class Solution {  
   public boolean wordBreak(String s, Set<String> dict) {  
     int n=s.length();  
     boolean[] dp=new boolean[n+1];  
     dp[0]=true;  
     for(int i=0;i<n;i++)  
     {  
       if(dp[i]==false)  
         continue;  
       for(String word:dict)  
       {  
         int len=word.length();  
         int end=i+len;  
         if(end>s.length())  
           continue;  
         if(dp[end]==true)  
           continue;  
         if(s.substring(i,end).equals(word))  
           dp[end]=true;  
       }  
     }  
     return dp[n];  
   }  
 }  

Palindrome Partitioning II (LeetCode Dynamic Programming)

Question: Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Idea: Duo-Dynamic programming. Let P[i][j] stand for whether the substring between i and j is a palindrome. Then we just need to compare the two ends of i and j to derive the recursive function. P[i][j]==true if s[i]==s[j]&&P[i+1][j-1]==true or the substring has less than 2 characters (j-i<2). Then use another array variable D[] to cache the total number of partitions. In the worst case, each character of the input string will be split as a palindrome. Then if we found s[i->j] is a palindrome through P[i][j], we can fill the data into D. This can be done at the same time as calculating P[i][j] or in another individual loop.

Time: O(n^2) Space: O(n^2)

Code:

 public class Solution {  
   public int minCut(String s) {  
     int n=s.length();  
     int[] D=new int[n+1];  
     boolean[][] P=new boolean[n][n];  
     for(int i=0;i<=n;i++)  
       D[i]=n-i;  
     for(int i=n-1;i>=0;i--)  
     {  
       for(int j=i;j<n;j++)  
       {  
         if(s.charAt(i)==s.charAt(j)&&(j-i<2||P[i+1][j-1]))  
         {  
           P[i][j]=true;  
           D[i]=Math.min(D[i],D[j+1]+1);  
         }    
       }  
     }  
     return D[0]-1;  
   }  
 }