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.