QuickSort

Algorithm: If the array contains only one element or zero elements then the array is sorted.

If the array contains more then one element then:

• Select an element from the array. This element is called the "pivot element". For example select the element in the middle of the array. (choose the middle one)
• All elements which are smaller then the pivot element are placed in one array and all elements which are larger are placed in another array.
• Sort both arrays by recursively applying Quicksort to them.
• Combine the arrays

Quicksort can be implemented to sort "in-place". This means that the sorting takes place in the array and that no additional array need to be created.

QuickSort can be accomplished the best in O(nlogn), the worst in O(n2).

Reference: here

 public class QuickSort {  
   public void quickSort(int[] A) {  
     if (A == null || A.length < 2)  
       return;  
     helper(A, 0, A.length-1);  
   }  
   public void helper(int[] A, int low, int high) {  
     if (A == null || A.length < 2)  
       return;  
     int pivot = (low + high) / 2;  
     int i=low, j = high;    
     while (i <= j) {  
       while (A[i] < A[pivot])  
         i++;  
       while (A[j > A[pivot]])  
         j--;    
       if (i < j) {  
         change(A, i++, j--);  
       }  
     }  
     if (low < j) helper(A, low, j); 
     if (i < high) helper(A, i, high);
   }  
   public void change(int[] A, int i, int j) {  
     int temp = A[i];  
     A[i] = A[j];  
     A[j] = temp;  
   }  
 }  

Swap Two Numbers Without Using the Third Variable

There are 2 methods that can swap 2 numbers without using the third variable.

1--"+" and "-"

public void changeNumber(int a, int b) {
    a = a + b;
    b = a - b;
    a = a - b;
}

2--"^" (XOR)

public void changeNumber(int a, int b) {
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

The second method is pretty tricky.

Longest Palindromic Substring

DP方法

 // Longest Palindromic Substring  
 // Dynamic Programming  
 // boolean table[i][j] means the substring from ith char to jth char is Palindrome or not  
 public class Solution {  
   public String longestPalindromicSubstring(String s) {  
     if (s == null || s.isEmpty())  
       return "";  
     int len = s.length();  
     boolean[][] table = new boolean[len][len];  
     for (int i=0; i<len; i++) {  
       table[i][i] = true;  
     }  
     for (int i=0; i<len-1; i++) {  
       if (s.charAt(i) == s.charAt(i+1))  
         table[i][i+1] = true;  
     }  
     for (int l=3; l<=len; l++) {  
       for (int i=0; i<=len-l; i++) {  
         int j=i+l-1;  
         if (s.charAt(i) == s.charAt(j)){  
           table[i][j] = table[i+1][j-1];  
         }  
       }  
     }  
     String ans = new String();  
     for (int i=0; i<len; i++) {  
       for (int j=i; j<len; j++) {  
         if (table[i][j]) {  
           if (ans.length() < j-i+1) {  
             ans = s.substring(i, j+1);  
           }  
         }  
       }  
     }  
     return ans;  
   }  
 }  

非DP方法

 public static String longestPalindrome(String s) {  
     if (s == null || s.length() < 2)  
       return s;  
     int len = s.length();  
     String ans = new String();  
     for (int i=0; i<len-1; i++) {  
       String a = getPalindrome(s, i, i);  
       String b = getPalindrome(s, i, i+1);  
       if (ans.length() < a.length())  
            ans = a;  
       if (ans.length() < b.length())  
            ans = b;  
     }  
     return ans;  
   }  
   public static String getPalindrome(String s, int start, int end) {  
     if (s == null || s.length() == 0)  
       return "";  
     if (start > end)  
       return "";  
     while (start >= 0 && end < s.length()) {  
       if (s.charAt(start) != s.charAt(end))  
         break;  
       else {  
         start--;  
         end++;  
       }  
     }  
     return s.substring(start+1, end);  
   }  

Problems needed to do Twice!

These problem all have some elegant method to finish it.

1. Sudoku Solver (Think about how to construct helper function and ArrayList to mark empty slots)
2. word search (2D boolean array && bugs from these array in recursive function)
3. word ladder
4. Longest Palindromic Substring (Think about 2 ways of constructing palindrome number)
5. Multiply Strings (Think about how to construct an array to store sum of multiplication)

Merge Intervals

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].

这个题目很容易出现的一个bug就是: 只merge最开始可以merge的那些, 而后面的没有merge.

先看一段代码:

 public class Solution {  
   public List<Interval> merge(List<Interval> intervals) {  
     if (intervals == null || intervals.size() < 2)  
       return intervals;  
     List<Interval> ans = new ArrayList<Interval>();  
     Collections.sort(intervals);  
     int pre = 0, curr = 1;  
     while (curr < intervals.size() && intervals.get(pre).end < intervals.get(curr).start) {  
       ans.add(intervals.get(pre));  
       pre = curr;  
       curr++;  
     }  
     int newStart = intervals.get(pre).start, newEnd = intervals.get(pre).end;  
     while (curr < intervals.size() && newEnd >= intervals.get(curr).start) {  
       newStart = Math.min(newStart, intervals.get(curr).start);  
       newEnd = Math.max(newEnd, intervals.get(curr).end);  
       curr++;  
     }      
     Interval newOne = new Interval(newStart, newEnd);  
     ans.add(newOne);  
     while (curr < intervals.size()) {  
       ans.add(intervals.get(curr));  
       curr++;  
     }  
     return ans;  
   }  
 }  

Input:	[[2,3],[2,2],[3,3],[1,3],[5,7],[2,2],[4,6]]
Output:	[[1,3],[4,6],[5,7]]
Expected:	[[1,3],[4,7]]

这个时候的问题就是: 第一组可以merge的interals全部被merge好了. 但是之后的intervals都left as their original. 问题就出在了中间斜体加粗的代码.

所以应该时刻让pre跟着curr, 从始至终都要跟着, 一旦发现了可以merge的就采取措施, 不断更新pre.
下面看正确的代码: 

 public class Solution {  
   public List<Interval> merge(List<Interval> intervals) {  
     if (intervals == null || intervals.size() < 2)  
       return intervals;  
     List<Interval> ans = new ArrayList<Interval>();  
     Collections.sort(intervals);  
     Interval pre = intervals.get(0);  
     for (int i=1; i<intervals.size(); i++) {  
       Interval curr = intervals.get(i);  
       if (pre.end < curr.start) {  
         ans.add(pre);  
         pre = curr;  
       }else {  
         pre.end = Math.max(pre.end, curr.end);  
         pre.start = Math.min(pre.start, curr.start);  
       }  
     }  
     ans.add(pre);  
     return ans;  
   }  
 }  

Note: 千万注意, get(0)要在sort之后, 因为后面的操作都是建立在已经sort好的一个Interval list上的!!!!!!!!!!!

Scrambling String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

 public boolean isScramble(String s1, String s2) {   
   int len = s1.length();   
   if (len != s2.length()) return false;   
   if (s1.equals(s2)) return true;   
   // a table of matches   
   // T[i][j][k] = true iff s2.substring(j,j+k+1) is a scambled string of s1.substring(i,i+k+1)   
   boolean[][][] scrambled = new boolean[len][len][len];   
   for (int i=0; i < len; ++i) {   
    for (int j=0; j < len; ++j) {   
     scrambled[i][j][0] = (s1.charAt(i) == s2.charAt(j));   
    }   
   }   
   // dynamically fill up the table   
   for (int k=1; k < len; ++k) { // k: length   
    for (int i=0; i < len - k; ++i) { // i: index in s1   
     for (int j=0; j < len - k; ++j) { // j: index in s2   
      scrambled[i][j][k] = false;   
      for (int p=0; p < k; ++p) { // p: split into [0..p] and [p+1..k]   
       if ((scrambled[i][j][p] && scrambled[i+p+1][j+p+1][k-p-1])   
         || (scrambled[i][j+k-p][p] && scrambled[i+p+1][j][k-p-1])) {   
        scrambled[i][j][k] = true;   
        break;   
       }   
      }   
     }   
    }   
   }   
   return scrambled[0][0][len-1];   
  }  

这个问题的解释详见:http://n00tc0d3r.blogspot.com/2013/05/scramble-string.html

Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

实现题型!

方法就是双指针. 一个解惑点: 如果当k的值大于了整个List的长度的时候, 那就是说明rotate了一圈之后在继续. 所以无论k是多少, 要rotate的个数永远是k % n. 

Recover Binary Search Tree

对于一个Binary Search Tree来说, 按照inOrder的顺序visit各个节点就会是从小到大的排列.
因为有两个节点放错了,所以会出现两次前面的点的值大于后面的点.
用三个指针, 第一个指针pre, 用来遍历整个Tree; 第二个指针first, 用来标记第一个错误的点; 第三个指针second, 用来标记第二个错误的点.

Note:在递归的时候, 何时给pre赋值, 何时给first赋值都是容易bug的地方. 说白了pre就是一个带头的, 发现一个不对的点就标记一下. (第一个点: 它的值比该层递归的root值大, 这个点不对; 第二个点, 当它作为root的时候, 位于前面的点比他大, 就是这个root有问题, 标记为second)

 public class Solution {  
   TreeNode pre;  
   TreeNode first;  
   TreeNode second;  
   public void recoverTree(TreeNode root) {  
     if (root == null)  
       return;  
     inOrder(root);  
     int tmp = first.val;  
     first.val = second.val;  
     second.val = tmp;  
   }  
   public void inOrder(TreeNode root) {  
     if (root == null)  
       return;  
     inOrder(root.left);  
     if (pre == null) {  
       pre = root;  
     }else {  
       if (pre.val > root.val) {  
         if (first == null) {  
           first = pre;  
         }
         second = root;  // 这里会发现, 如果出现了异常, second会一直跟着root走.直到不再出现异常为止,
                         // 这个时候second也就指向了第二个异常的点了.注意: second不是等于pre!!!!
       }  
       pre = root;  
     }  
     inOrder(root.right);  
   }  
 }  

上面是优解,下面这个方法虽然不是最优解, 但是容易上手. 将BST按照inorder顺序把节点和节点的数值存到两个list中, 将节点值list sort一下, 重新赋值给各个节点.

 public class Solution {  
   public void recoverTree(TreeNode root) {  
          if (root == null)  
            return;  
          ArrayList<TreeNode> visit = new ArrayList<TreeNode>();  
          ArrayList<Integer> values = new ArrayList<Integer>();  
          inOrder(visit, values, root);  
          Collections.sort(values);  
          for (int i=0; i<values.size(); i++) {  
            TreeNode curr = visit.get(i);  
            curr.val = values.get(i);  
          }  
        }  
   public void inOrder(ArrayList<TreeNode> visit, ArrayList<Integer> values, TreeNode node) {  
     if (node == null)  
       return;  
     inOrder(visit, values, node.left);  
     visit.add(node);  
     values.add(node.val);  
     inOrder(visit, values, node.right);  
   }  
 }  

Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

The key of this problem, is to calculate k-1 times each time you do "in place" operation!

The way of "in place" is very smart!!!

 public class Solution {  
   public ListNode reverseKGroup(ListNode head, int k) {  
     if (head == null || head.next == null || k < 2)  
       return head;  
     ListNode newHead = new ListNode(0);  
     newHead.next = head;  
     ListNode pre = newHead;  
     ListNode curr = head;  
     while (curr != null) {  
       // make sure the rest of the List is enough   
       int counter = k;         // calculate k-1 times
         curr = curr.next;  
         counter--;  
       }  
       if (curr != null) {  
         curr = pre.next;  
         counter = k;  
         while (counter > 1) {  // calculate k-1 times
ListNode tmp = curr.next;  
           curr.next = tmp.next;  
           tmp.next = pre.next;  
           pre.next = tmp;  
           counter--;  
         }  
         pre = curr;  
         curr = pre.next;  
       }  
     }  
     return newHead.next;  
   }  
 }  

Insertion Sort List

Sort a linked list using insertion sort.
This is insertion sort

Algorithm: 

-1-Create a new head has the same value with the value of original list.
-2-Create two pointers: pointer initialized to point to the second node in the original list, and and innerPointer used to do insertion operation in the new sorted list. InnerPointer is initialized to point to the new head;
-3-There are three parts need you to take care of: update head of the new list; effectively insert node into the new list; update tail the new list.
Note:small bug on dealing with the new head every. Consider if the value of the node waiting to insert has the same value with new head!

 public class Solution {  
   public ListNode insertionSortList(ListNode head) {  
     if (head == null || head.next == null)  
       return head;  
     ListNode newHead = new ListNode(head.val);  
     ListNode pointer = head.next;  
     while(pointer!=null){  
       ListNode innerPointer=newHead;  
       ListNode next=pointer.next;  
       if(newHead.val>=pointer.val){  // "=" is a source of bug!
         ListNode oldHead=newHead;  
         newHead=pointer;  
         newHead.next=oldHead;  
       }else{  
         while(innerPointer.next!=null){  
           if(innerPointer.val<pointer.val&&innerPointer.next.val>=pointer.val){  
             pointer.next=innerPointer.next;  
             innerPointer.next=pointer;  
             break;  
           }  
           innerPointer=innerPointer.next;  
         }  
         if(innerPointer.next==null){  
           innerPointer.next=pointer;  
           pointer.next=null;  
         }  
       }  
       pointer=next;  
     }  
     return newHead;  
   }  
 }  

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Find next larger number which consists of all the digits of current number.
You had better to remember this algorithm:

• From right to left, find the first index1 that num[index1] > num[index1-1]; if it does not exist, it means the current number is the largest one, just reverse it
• From right to left, find the first index2 that num[index2] > num[index1-1];
• Swap num[index1-1] and num[index2];
• Reverse the array from index1 to the end of this array.

 public class Solution {  
   public void nextPermutation(int[] num) {  
     if (num == null || num.length == 0)  
       return ;  
     int index1 = 0, index2 = 0;  
     for (int i=num.length-1; i>=1; i--) {  
          if (num[i]>num[i-1]) {  
               index1=i;  
               for (int j=num.length-1; j>=index1; j--){  
                    if (num[j]>num[leftPos]) {  
                         index2 = j;  
                         int t = num[index2];  
                         num[index2] = num[index1-1];  
                         num[index1-1] = t;  
                         break;  
                    }  
               }  
               reverseArray(num, index1, num.length-1);  
               return;  
          }  
     }  
     reverseArray(num, 0, num.length-1);  
   }  
   public int[] reverseArray(int[] array, int begin, int end) {  
     if (begin >= end)  
       return array;  
     for (int i=begin, j=end; i<j; i++, j--) {  
       int t = array[i];  
       array[i] = array[j];  
       array[j] = t;  
     }  
     return array;  
   }  
 }  

Unique Binary Search Tree ii

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Algorithm:
This problem is solved using recursion. We should know that every number between 1 and n can be a root value. Thus, going from 1 to n, each time get a number i as the root, the numbers smaller than i form the left child tree and the numbers larger than i form the right child tree. Recursively do this.

Code:

 public class Solution {  
   public List<TreeNode> generateTrees(int n) {  
     return helper(1, n);  
   }  
   public List<TreeNode> helper(int begin, int end) {  
     List<TreeNode> list = new ArrayList<TreeNode>();  
     if (begin > end) {  
       list.add(null);  
       return list;  
     }  
     for (int i=begin; i<=end; i++) {  
       List<TreeNode> left = helper(begin, i-1);  
       List<TreeNode> right = helper(i+1, end);  
       for (int j=0; j<left.size(); j++) {  
         for (int k=0; k<right.size(); k++) {  
           TreeNode root = new TreeNode(i);  
           root.left = left.get(j);  
           root.right = right.get(k);  
           list.add(root);  
         }  
       }  
     }  
     return list;  
   }  
 }  

NOTE: for one value, there is probably several structurally unique binary trees, like 3 as root in the example

Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

这个题目有两种思路: 第一种就是新建一个链表;第二种就是直接修改链表1或者是链表2.

可以看到, 第一种思路要相对多用一些空间. 第二种思路,比较省空间(但是实际上也可以忽略不计了).两个方法的的复杂度都是O(n).

这里只写第一种方法: 代码十分简单!

 public class Solution {  
   public ListNode addTwoNumbers(ListNode l1, ListNode l2) {  
     if (l1 == null) return l2;  
     if (l2 == null) return l1;  
     ListNode p1=l1, p2=l2;  
     ListNode newHead = new ListNode(0);  
     ListNode p3 = newHead;  
     int carry = 0;  
     while (p1 != null || p2 != null) {  
       if (p1 != null) {  
         carry += p1.val;    
         p1 = p1.next;  
       }  
       if (p2 != null) {  
         carry += p2.val;  
         p2 = p2.next;  
       }  
       ListNode next = new ListNode(carry % 10);  
       p3.next = next;  
       p3 = p3.next;  
       carry = carry / 10;  
     }  
     if (carry != 0) {  
       p3.next = new ListNode(carry);  
     }  
     return newHead.next;  
   }  
 }  

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

 public class Solution {  
   public int lengthOfLongestSubstring(String s) {  
     if (s == null || s.isEmpty())  
       return 0;  
     int len = s.length();  
     boolean[] table = new boolean[256];  
     int start = 0;  
     int maxLength = 1;  
     int i = 0;  
     while (i < s.length()) {  
       char curr = s.charAt(i);  
       if (!table[curr])  
         table[curr] = true;  
       else {  
         int currLen = i - start;  
         maxLength = Math.max(maxLength, currLen);  
         for (int j=start; j<i; j++) {  
           if (s.charAt(j) == s.charAt(i)) {  
             start = j+1;  
             break;  
           }  
           else  
             table[s.charAt(j)] = false;  
         }  
       }  
       i++;  
     }  
     maxLength = Math.max(maxLength, len-start);  
     return maxLength;  
   }  
 }  

Note:这里关键是看到如何处理else中update完maxLength之后的部分

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

[
    ["aa","b"],
    ["a","a","b"]
  ]

 public class Solution {  
   public ArrayList<ArrayList<String>> partition(String s) {  
     ArrayList<ArrayList<String>> list = new ArrayList<ArrayList<String>>();  
     if (s == null || s.length() == 0) {  
       list.add(new ArrayList<String>());  
       return list;  
     }  
     helper(s, list, new ArrayList<String>(), 0, s.length());  
     return list;  
   }  
   public void helper(String s, ArrayList<ArrayList<String>> r, ArrayList<String> temp, int pos, int n) {  
     if (pos == n) {  
       ArrayList<String> newTemp = new ArrayList<String>(temp);  
       r.add(newTemp);  
       return;  
     }  
     // here we need an end pointer to extract each substrings  
     for (int end=pos+1; end<=n; end++) {  
       String sub = s.substring(pos, end);  
       if (isPalindrome(sub)) {  
         temp.add(sub);  
         helper(s, r, temp, end, n);  
         temp.remove(temp.size()-1);  
       }  
       // here you do not need to deal with the case that sub is not palindorme  
     }  
   }  
   public boolean isPalindrome(String string) {  
     if (string == null || string.length()==0)  
       return true;  
     boolean b = true;  
     int i=0, j=string.length()-1;  
     while (i <= j) {  
       if (string.charAt(i) != string.charAt(j))  
         b = false;  
       i++;  
       j--;  
     }  
     return b;  
   }  
 }  

Reverse Linked List II

Given positions m and n in a linked list, reverse all the nodes from mth node to nth node.

 public class Solution {  
   public ListNode reverseBetween(ListNode head, int m, int n) {  
     if (head == null || head.next == null || m == n)  
       return head;  
     ListNode newHead = new ListNode(0);  
     newHead.next = head;  
     ListNode pre = newHead;  
     ListNode first = head, second = head;  
     int further = n > m ? n:m, near = n < m?n:m;  
     for (int i=1; i<=further; i++) {  
       if (i < near)   
         pre = pre.next;  
       else if (i == near) {  
         first = pre.next;  
         second = first.next;  
       }else {  
         first.next = second.next;  
         second.next = pre.next;  
         pre.next = second;  
         second = first.next;  
       }  
     }  
     return newHead.next;  
   }  
 }  

Letter Combinations of Phone Number

There are 2 solutions the first one is wrong, the second one is right. Be careful!

 public class Solution {  
   public List<String> letterCombinations(String digits) {  
     List<String> r = new ArrayList<String>();  
     if (digits.length() == 0 || digits == null) return r;  
     String[] table = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  
     helper(digits, r, table, new StringBuilder(), 0, digits.length());  
     return r;  
   }  
   public void helper(String digits, List<String> r, String[] table, StringBuilder temp, int pos, int n) {  
     if (pos >= n) {  
       String s = temp.toString();  
       r.add(s);  
       return;  
     }  
     for (int i=pos; i<n; i++) {  
       int curr = digits.charAt(i)-'0';  
       if (curr == 0 || curr == 1 || digits.charAt(i) == '*' || digits.charAt(i) == '#')  
         helper(digits, r, table, temp, i+1, n);  
       else {  
         String choice = table[curr];  
         for (int j=0; j<choice.length(); j++) {  
           char choiceCurr = choice.charAt(j);  
           temp.append(choiceCurr);  
           helper(digits, r, table, temp, i+1, n);  
           temp = new StringBuilder(temp.substring(0, temp.length()-1));  
         }  
       }  
     }  
   }  
 }  

 public class Solution {  
   public static List<String> letterCombinations(String digits) {  
     List<String> r = new ArrayList<String>();  
     if (digits == null) return r;  
     String[] table = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  
     if (digits.isEmpty()) {  
       r.add("");  
       return r;  
     }  
     helper(digits, r, table, new StringBuilder(), 0, digits.length());  
     return r;  
   }  
   public static void helper(String digits, List<String> r, String[] table, StringBuilder temp, int pos, int n) {  
     if (pos >= n) {  
       String s = temp.toString();  
       r.add(s);  
       return;  
     }  
     int curr = digits.charAt(pos)-'0';  
     if (curr == 0 || curr == 1 || digits.charAt(pos) == '*' || digits.charAt(pos) == '#')  
       helper(digits, r, table, temp, pos+1, n);  
     else {  
       String choice = table[curr];  
       for (int j=0; j<choice.length(); j++) {  
         char choiceCurr = choice.charAt(j);  
         temp.append(choiceCurr);  
         helper(digits, r, table, temp, pos+1, n);  
         temp.deleteCharAt(pos);  
       }  
     }  
   }  
 }  

LeetCode: Binary Tree PostOrder Traversal

 /*  
 ** This is problem can be solved in a very smart way.  
 ** The key point here is if you use a stack to do DFS  
 ** (Left-to-right), the order of visiting is preorder.  
 ** But, if you do in the opposite way, it will generate  
 ** the opposite result of postorder traversal.  
 **  
 ** Preorder, stack push right first, then left  
 ** PostOrder, stack push left first, then right, after  
 ** finish the loop, reverse the result.  
 */  
 public class Solution {  
   public List<Integer> postorderTraversal(TreeNode root) {  
     List<Integer> ans = new ArrayList<Integer>();  
     if (root == null) return ans;  
     Stack<TreeNode> stack = new Stack<TreeNode>();  
     stack.push(root);  
     while (!stack.empty()) {  
       TreeNode curr = stack.pop();  
       ans.add(curr.val);  
       if (curr.left != null)   
         stack.push(curr.left);  
       if (curr.right != null)  
         stack.push(curr.right);  
     }  
     Collections.reverse(ans);  
     return ans;  
   }  
 }  

LeetCode: Partition List

Simple Question with O(n) time.

1:  /*  
2:  ** This problem is solved by making 2 new heads,  
3:  ** one lead the nodes whose value are less than the target value;  
4:  ** one lead the others  
5:  ** After making two new lists, use 2 pointers to make a new lis.  
6:  ** Here we need to see that after finish these 2 lists, you  
7:  ** need to "NULL" these 2 lists at the end, or it will be TLE  
8:  */  
9:  public class Solution {  
10:    public ListNode partition(ListNode head, int x) {  
11:      if (head == null || head.next == null)   return head;  
12:      // Construct another 2 new List  
13:      ListNode newHead1 = new ListNode(0), newHead2 = new ListNode(0);  
14:      // 2 runners  
15:      ListNode p1 = newHead1, p2 = newHead2;  
16:      ListNode curr = head;  
17:      while (curr != null) {  
18:        if (curr.val < x) {  
19:          p1.next = curr;  
20:          p1 = p1.next;  
21:        }else {  
22:          p2.next = curr;  
23:          p2 = p2.next;  
24:        }  
25:        curr = curr.next;  
26:      }  
27:      p1.next = null;  
28:      p2.next = null;  
29:      p2 = newHead2.next;  
30:      while (true) {  
31:        if (p2 == null) {  
32:          p1.next = p2;  
33:          break;  
34:        }else {  
35:          p1.next = p2;  
36:          p1 = p1.next;  
37:          p2 = p2.next;  
38:        }  
39:      }  
40:      return newHead1.next;  
41:    }  
42:  }