[LeetCode] Climbing Stairs

Thought:
   Nothing easier than this....

Code:
public class Solution {
    public int climbStairs(int n) {
        int[] result = new int[n + 2];
        result[1] = 1;
        for(int i = 2; i < n + 2; i++) {
            result[i] = result[i - 1] + result[i - 2];
        }
        return result[n + 1];
    }
}

[LeetCode] Binary Tree Maximum Path Sum

Thought:
    Use a class variable to keep track of the maximum path ever seen( either across the root of not).
    Use another method to calculate the maximum path ends with some specific node.
    Then get the result.

public class Solution {
    public static int maxAcrossRoot = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxAcrossRoot = Integer.MIN_VALUE;
        int result = maxEndsRoot(root);
        return Math.max(result, maxAcrossRoot);       
    }
    public int maxEndsRoot(TreeNode root) {
        if(root == null) return 0;
        int left = maxEndsRoot(root.left);
        int right = maxEndsRoot(root.right);
        int temp = root.val;
        if(left > 0) temp += left;
        if(right > 0) temp += right;
        maxAcrossRoot = Math.max(temp, maxAcrossRoot);
        return Math.max(root.val, Math.max(root.val + left, root.val + right));       
    }
}

[LeetCode] Binary Tree Zigzag Level Order Traversal

Thought:
    Basically the same with level order traversal. And a flag should be used for determining the order of some specific level.

Code:
public class Solution {
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        int depth = 0;
        Queue<TreeNode> q1 = new LinkedList<TreeNode>();
        Queue<Integer> q2 = new LinkedList<Integer>();
        if(root == null) return result;
        q1.offer(root);
        q2.offer(depth + 1);
        while(q1.peek() != null) {
            TreeNode element = q1.poll();
            depth = q2.poll();
            if(result.size() < depth) {
                result.add(new ArrayList<Integer>());
            }
            if(depth % 2 == 1) {
                result.get(depth - 1).add(element.val); 
            }else{
                result.get(depth - 1).add(0,element.val); 
            }                                
            if(element.left != null) {
                q1.offer(element.left);
                q2.offer(depth+1);
            }
            if(element.right != null) {
                q1.offer(element.right);
                q2.offer(depth+1);
            }
        }
        return result;
    }
}

[LeetCode] Binary Tree Level Order Traversal II

Thought:
    Basically the same with prior problem, the only change is dealing with the result.

Code:
public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        int depth = 0;
        Queue<TreeNode> q1 = new LinkedList<TreeNode>();
        Queue<Integer> q2 = new LinkedList<Integer>();
        if(root == null) return result;
        q1.offer(root);
        q2.offer(depth + 1);
        while(q1.peek() != null){
            TreeNode element = q1.poll();
            depth = q2.poll();
            if(result.size() < depth){
                result.add(0, new ArrayList<Integer>());
            }
            result.get(0).add(element.val);                      
            if(element.left != null){
                q1.offer(element.left);
                q2.offer(depth + 1);
            }
            if(element.right != null){
                q1.offer(element.right);
                q2.offer(depth + 1);
            }
        }
        return result;
    }
}

[LeetCode] Binary Tree Level Order Traversal

Thought:
    We use two Queue, one stores the TreeNode, one stores their corresponding depth.

public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        int depth = 0;
        Queue<TreeNode> q1 = new LinkedList<TreeNode>();
        Queue<Integer> q2 = new LinkedList<Integer>();
        if(root == null) return result;
        q1.offer(root);
        q2.offer(depth + 1);
        while(q1.peek() != null){
            TreeNode element = q1.poll();
            depth = q2.poll();
            if(result.size() < depth){
                result.add(new ArrayList<Integer>());
            }
            result.get(depth - 1).add(element.val);                    
            if(element.left != null){
                q1.offer(element.left);
                q2.offer(depth + 1);
            }
            if(element.right != null){
                q1.offer(element.right);
                q2.offer(depth + 1);
            }
        }
        return result;
    }
}

[LeetCode] Binary Tree Inorder Traversal

Thought:
    It is common place to use stack to simulate recursion.

Code:
public class Solution {
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        
        ArrayList<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> s = new Stack<TreeNode>();
        
        while(root != null || !s.empty()){
            while(root!=null){
                s.push(root);
                root=root.left;
            }
            if(!s.empty()){
                root = s.pop();
                result.add(root.val);
                root = root.right;
            }                        
        }
        return result;
    }
}

[LeetCode] Best Time to Buy and Sell Stock II

Thought:
We just bought on the first  day, and every time we can earn some money we sell it.

Code:
public class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        if(prices.length == 0) return profit;
        int bought = prices[0];
       
        for(int i = 1; i < prices.length; i++) {
            if( prices[i] > bought){
                profit += prices[i] - bought;
            }
            bought = prices[i];
        }
       
        return profit;
    }
}

[LeetCode] Best Time to Buy and Sell Stock III

Thought: 
Divide the array into two parts, find two profits, and add them together.

Code:
public class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        for(int i = 0; i < prices.length ; i++){
            if( forwardProfit(prices,i) + backwardProfit(prices,i) > profit ){
                profit = forwardProfit(prices,i) + backwardProfit(prices,i);
            }
        }
        return profit;     
    }
    public int forwardProfit(int[] prices, int n){
        if(prices.length==0) return 0;
        int min = prices[0] ;
        int profit = 0;
       
        for(int i = 0; i < n; i++){
            if( prices[i] < min ){
                min = prices[i];
            }else if( prices[i] - min > profit ){
                profit = prices[i] - min;
            }
        }
        return profit; 
    }
    public int backwardProfit(int[] prices, int n){
        if(prices.length==0) return 0;
        int max = prices[prices.length-1] ;
        int profit = 0;
       
        for(int i = prices.length - 1; i > n - 1; i--){
            if( prices[i] > max ){
                max = prices[i];
            }else if( max - prices[i] > profit ){
                profit = max - prices[i];
            }
        }
        return profit;
    }
}

[LeetCode] Best Time to Buy and Sell Stock I

Thought:
Just Keep track of the min price and the local max profit.

Code:
public class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        if(prices.length == 0) return profit;
        int min = prices[0];
       
        for(int i = 1; i < prices.length; i++) {
            if( prices[i] - min > profit){
                profit = prices[i] - min;
            }else if( prices[i] < min) {
                min = prices[i];
            }
        }
       
        return profit;
    }
}

[LeetCode] Balanced Binary Tree

Thought:
To prevent redundant computation, we'd better first examine the flag of the left subtree and then the right one.
-1 means unbalanced and if not -1 it means the height.

Code:
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }else{
            return flag(root) == -1? false: true; 
        }       
    }
    public int flag(TreeNode root) {
        if(root == null) {
            return 0;
        }else{           
            int lFlag = flag(root.left);
            if(lFlag == -1) return -1;
            int rFlag = flag(root.right);
            if(rFlag == -1) return -1;
            return Math.abs(lFlag - rFlag) <= 1? Math.max(lFlag, rFlag) + 1: -1;       
        }
    }
}

[LeetCode] Anagrams

Thought:
Use a HashMap to store the sorted-original pairs, if there are several original string that relates to the same sorted string, they are anagrams!

Code:
import java.util.Iterator;
public class Solution {
    public ArrayList<String> anagrams(String[] strs) {
        HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        ArrayList<String> result = new ArrayList<String>();
       
        for (int i = 0; i < strs.length; i++) {
            String key = sortWord(strs[i]);
            if (!map.containsKey(key)) {
                ArrayList<String> value = new ArrayList<String>();
                value.add(strs[i]);
                map.put(key, value);
            }
            else {
                ArrayList<String> value = map.get(key);
                value.add(strs[i]);
                map.put(key, value);
            }
        }
        
        Iterator<ArrayList<String>> it = map.values().iterator();
        while (it.hasNext()) {
            ArrayList<String> v = it.next();
            if (v.size() >= 2) {
                result.addAll(v);
            }
        }
        
        return result;
    }
    
    public String sortWord(String word){
        char[] charArr = word.toCharArray();
        Arrays.sort(charArr);
        return new String(charArr);
    }
}

[LeetCode] Add Binary

Thought:
It is easy.

Code:
public class Solution {
    public String addBinary(String a, String b) {
        StringBuilder result = new StringBuilder();
        int m = a.length();
        int n = b.length();
        int len = Math.max(m, n);
        int carry = 0;
       
        for(int i = 0; i < len; i++) {
            int x = getIndex(a, m - 1 - i);
            int y = getIndex(b, n - 1 - i);
            result.insert(0, (x + y + carry) % 2);
            carry = (x + y + carry) / 2;
        }
        if(carry == 1) {
            result.insert(0, 1);
        }
        return result.toString();       
    }
    public int getIndex(String s, int index) {
        if(index < 0 || index > s.length() - 1) {
            return 0;
        }else {
            return s.charAt(index) == '0'? 0: 1;
        }
    }
}

Second Round Code:

public class Solution {
    public String addBinary(String a, String b) {
        StringBuilder ret = new StringBuilder();        
        int carry = 0;
        int retLength = Math.max(a.length(), b.length());
        int i = a.length() - 1;
        int j = b.length() - 1;

        while (retLength-- > 0) {
            int temp = getInt(a, i--) + getInt(b, j--) + carry;
            ret.append(temp % 2);
            carry = temp / 2;            
        }
        if (carry == 1) ret.append(1);
        return ret.reverse().toString();
    }
    public int getInt (String s, int index) {
        if (index < 0 || index > s.length() - 1) return 0;
        return s.charAt(index) == '0'? 0 : 1 ;
    }
}

[LeetCode] Remove Element

Thought:
Iterate from the end of the array, if we find a match we exchange the current value and the len-1 index value, and then update the len.

Code:
public class Solution {
    public int removeElement(int[] A, int elem) {
        int len = A.length;
        for(int i = A.length - 1; i >= 0; i--){
            if(A[i] == elem){
                A[i] = A[len - 1];
                len--;
            }
        }
        return len;
    }
}

[LeetCode] Remove Duplicates from Sorted Array

Thought:
It is very easy..
Just scan the array, if the current value = index value, let the length - 1.
If the current value != index value, copy it into index's next place, and update index.

Code:
public class Solution {
    public int removeDuplicates(int[] A) {
        int index = 0;
        int len = A.length;
       
        if(A.length <= 1) return len;
       
        for(int i = 1; i < A.length; i++){
            if(A[i] == A[index]){
                len--;
            }else{
                A[++index] = A[i];
            }
        }
        return len;
    }
}

[LeetCode] Generate Parentheses

Thought:
Use Recursion, 
if right = left = n, we update the result.
if right = left < n, we add "(",
if right < left = n, we add ")",
if right < left < n, we could add "(" or ")".

Code:
public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
       
        ArrayList<String> result = new ArrayList<String>();
        char[] temp = new char[2 * n];
       
        build(result, 0, 0, n, temp);
        
        return result;
    }
    public void build(ArrayList<String> result, int left, int right, int n, char[] temp){
        if(left == right && left == n){
            result.add(new String(temp));
            return;
        }else{// some kind of DFS
            if(left < n){
                temp[left + right] = '(';
                build(result, left + 1, right, n, temp);
            }
            if(left > right){
                temp[left + right] = ')';
                build(result, left, right + 1, n, temp);               
            }
        }
    }
}

[LeetCode] Swap Nodes in Pairs

Thought:
Usually, we keep a sentinel before the head in Linked List problems.
Make sure that do not forget some links when linking nodes, which will make the whole list be divided into several parts.

Code:
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null) return head;
       
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;
        ListNode ppre = sentinel;
        ListNode pre = head;
        ListNode current = head.next;
       
        while(current != null){
           
            pre.next = current.next;
            current.next = pre;
            ppre.next = current;           
            ppre = current;           
            current = pre.next;
           
            if(current != null){
                current = current.next;
                pre = pre.next;
                ppre = ppre.next;
            }
        }
        return sentinel.next;
    }
}

[LeetCode] Valid Parentheses

Thought:
Trivial using stack.

Code:
public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for(int i = 0; i < s.length(); i++ ){
            char tmp = s.charAt(i);
            if(tmp == '(' || tmp == '[' || tmp == '{' ){
                stack.push(tmp);
            }else{
                if(stack.isEmpty()){
                    return false;
                }else if (tmp == ')'){
                    if(stack.pop() != '('){
                        return false;
                    }
                }else if (tmp == ']'){
                    if(stack.pop() != '['){
                        return false;
                    }
                }else{
                    if(stack.pop() != '{'){
                        return false;
                    }
                }
            }
        }
        return stack.isEmpty()? true: false;       
    }
}

[LeetCode] Remove Nth Node From End of List

Thought:
Use two pointers, there distance is N. When the second pointer move to the end, the first pointer will point to the Node to be deleted.
To track the Node before the deleted node, initialize a previous pointer.

Code:
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
       
        ListNode first = head;
        ListNode second = head;
        ListNode previous = head;
       
        while(n > 1){
            second = second.next;
            n--;
        }
       
        while(second.next != null){
            previous = first;
            first = first.next;
            second = second.next;
        }
               
        if(first != head){//deleting first
            previous.next = first.next;
        }else{//deleting head
            head = head.next;
        }
       
        return head;       
    }
}

[LeetCode] Letter Combinations of a Phone Number

Thought:
It is an easy DP problem, we use the previous result to obtain the current result.

Code:
public class Solution {
    public ArrayList<String> letterCombinations(String digits) {
        ArrayList<String> result = new ArrayList<String>();
        if(digits.length() == 0){
            result.add("");
        }else{
            ArrayList<String> previous = letterCombinations(digits.substring(1));
            char c = digits.charAt(0);
            for(String i: previous){
                if(c=='2'){
                    result.add("a" + i);result.add("b" + i);result.add("c" + i);
                }else if(c=='3'){
                    result.add("d" + i);result.add("e" + i);result.add("f" + i);
                }else if(c=='4'){
                    result.add("g" + i);result.add("h" + i);result.add("i" + i);
                }else if(c=='5'){
                    result.add("j" + i);result.add("k" + i);result.add("l" + i);
                }else if(c=='6'){
                    result.add("m" + i);result.add("n" + i);result.add("o" + i);
                }else if(c=='7'){
                    result.add("p" + i);result.add("q" + i);
                    result.add("r" + i);result.add("s" + i);
                }else if(c=='8'){
                    result.add("t" + i);result.add("u" + i);result.add("v" + i);
                }else if(c=='9'){
                    result.add("w" + i);result.add("x" + i);
                    result.add("y" + i);result.add("z" + i);
                }
            }
        }
        return result;
    }
}

[LeetCode] 4Sum

Thought:
Just like 3Sum, we can write an O(n^3) solution.

Code:
public class Solution {
    public ArrayList<ArrayList> fourSum(int[] num, int target) {
        Arrays.sort(num);
        HashSet<ArrayList> result = new HashSet<ArrayList>();
        for (int i = 0; i < num.length; i++) {
            for (int j = i + 1; j < num.length; j++) {
                for (int k = j + 1, l = num.length - 1; k < l;) {      
                    int sum = num[i] + num[j] + num[k] + num[l];       
                    if (sum > target) {
                        l--;
                    }
                    else if (sum < target) {
                        k++;
                    }else{
                        ArrayList tmp = new ArrayList();
                        tmp.add(num[i]);
                        tmp.add(num[j]);
                        tmp.add(num[k]);
                        tmp.add(num[l]);
                        result.add(tmp);
                        k++;
                        l--;
                    }
                }
            }
        }
        return new ArrayList<ArrayList>(result);
    }
}

Code second Round:

public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        Set<ArrayList<Integer>> result = new HashSet<ArrayList<Integer>>();
        Arrays.sort(num);
        for (int i = 0; i < num.length - 1; i++) {
            for (int j = i + 1; j < num.length; j++) {
                 int m = j + 1, n = num.length - 1;
                 while (m < n) {
                     if (num[i] + num[j] + num[m] + num[n] < target) m++;
                     else if (num[i] + num[j] + num[m] + num[n] > target) n--;
                     else {
                         ArrayList<Integer> temp = new ArrayList<Integer>();
                         temp.add(num[i]);
                         temp.add(num[j]);
                         temp.add(num[m]);
                         temp.add(num[n]);
                         result.add(temp);
                         m++; 
                         n--;
                     }
                 }
            }
        }
        return new ArrayList<ArrayList<Integer>>(result);
    }
}

[LeetCode] 3Sum Closest

Thought:
The basic pattern is just like the 3Sum.
Use a flag to store the difference between sum and the target, when we encounter a smaller difference ,we should update the difference and also update the result at the same time. 
It is a O(n^2) solution.

Code:
public class Solution {
    public int threeSumClosest(int[] num, int target) {
        int dif = Integer.MAX_VALUE;
        int result = target;
        Arrays.sort(num);
        for(int i = 0;i < num.length; i++){
            int j = i + 1;
            int k = num.length - 1;
            while(j < k){
                int sum = num[j] + num[k] + num[i];
                if(sum == target){                   
                    return target;
                }else if(sum > target){
                    k--;
                }else{
                    j++;
                }
               
                if(dif > Math.abs(sum-target)){
                    result = sum;               
                }
                dif = Math.min(dif, Math.abs(sum-target));
            }
        }
        return result;
    }
}

Second Round Code:

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        int dif = Integer.MAX_VALUE;
        int result = target;
        Arrays.sort(num);
        for (int i = 0; i < num.length; i++) {
            int j = i + 1; 
            int k = num.length - 1;
            while (j < k) {
                int temp = num[i] + num[j] + num[k];
                
                if (temp == target) return target;
                if (temp < target) j++;
                else k--;

                if (dif > Math.abs(temp - target)) {
                    dif = Math.abs(temp - target);
                    result = temp;                
                }
            }
        }
        return result;
    }
}

[LeetCode] 3Sum

Thought:
Sort and iterate the array, for every element, we find the other two elements whose sum is -num[i], it is a O(n^2) solution.

Code:
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        HashSet<ArrayList<Integer>> result = new HashSet<ArrayList<Integer>>();
        Arrays.sort(num);
        for(int i = 0;i < num.length; i++){
            int j = i + 1;
            int k = num.length - 1;
            while(j < k){
                if(num[j] + num[k] + num[i] < 0){
                    j++;
                }else if(num[j] + num[k] + num[i] > 0){
                    k--;
                }else{
                    ArrayList<Integer> tmp = new ArrayList<Integer>();                  
                    tmp.add(num[i]);
                    tmp.add(num[j]);
                    tmp.add(num[k]);
                    result.add(tmp);
                    j++;
                    k--;
                }               
            }
        }
        return new ArrayList<ArrayList<Integer>>(result);
    }
}

Code when I met this problem the second time:

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        Set<ArrayList<Integer>> result = new HashSet<ArrayList<Integer>>();
        Arrays.sort(num);
        for (int i = 0; i < num.length; i++) {
            twoSum(Arrays.copyOfRange(num, i + 1, num.length), -num[i], result);
        }
        return new ArrayList<ArrayList<Integer>>(result);
    }
    public void twoSum(int[] array, int sum, Set<ArrayList<Integer>> result) {
        if (array.length < 2) return;
        int i = 0, j = array.length - 1;
        while (i < j) {
            if (array[i] + array[j] < sum) i++;
            else if (array[i] + array[j] > sum) j--;
            else {
                ArrayList<Integer> temp = new ArrayList<Integer>();
                temp.add(-sum);
                temp.add(array[i]);
                temp.add(array[j]);
                result.add(temp);
                i++;       // I forgot this two lines at first...............
                j--;
            }
        }
    }
}

[LeetCode] Longest Common Prefix

Thought:
For every string in the array, test their first character, and then second and then... until we found mismatch.

Code:
public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length==0) return "";
        
        int len = 0;
        boolean flag = true;
        while(flag){
            for(int i = 0; i < strs.length; i++){
                if( len >= strs[i].length() ){
                    flag = false;
                    break;
                }else if( strs[i].charAt(len) != strs[0].charAt(len) ){
                    flag = false;
                    break;
                }
            }
            if(flag) len++;
        }
        return strs[0].substring(0,len);        
    }
}

[LeetCode] Roman To Integer

Thought:
From the LSB to the MSB, if current bit's value is smaller than previous bit's value, we should minus this bit, otherwise add this bit.

Code:
public class Solution {
    public int romanToInt(String s) {
       
        HashMap<Character, Integer> roman = new HashMap<Character, Integer>();
       
        roman.put('I', 1);
        roman.put('V', 5);
        roman.put('X', 10);
        roman.put('L', 50);
        roman.put('C', 100);
        roman.put('D', 500);
        roman.put('M', 1000);
       
        int i = s.length() - 1;
        int result = roman.get(s.charAt(i));
        char current = ' ', previous = ' ';
       
        while(i > 0){
            previous = s.charAt(i);
            current = s.charAt(i - 1);
            if(roman.get(current) < roman.get(previous)){
                result = result - roman.get(current);
            }else{
                result = result + roman.get(current);
            }
            i--;
        }       
        return result;       
    }
}

[LeetCode] Integer To Roman

Thought:
Using a HashMap to store the relation between integer and Roman numerical.
It is really tricky that putting 4,9,40,90,400,900 into this map will result in an easier solution.

Code:
public class Solution {
    public String intToRoman(int num) {
       
        HashMap<Integer, String> roman = new HashMap<Integer, String>();
        int[] base = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
       
        roman.put(1, "I");
        roman.put(4, "IV");
        roman.put(5, "V");
        roman.put(9, "IX");
        roman.put(10, "X");
        roman.put(40, "XL");
        roman.put(50, "L");
        roman.put(90, "XC");
        roman.put(100, "C");
        roman.put(400, "CD");
        roman.put(500, "D");
        roman.put(900, "CM");
        roman.put(1000, "M");
       
        String result = new String();
        for( int temp : base ){
            while( num >= temp ){
                result = result + roman.get(temp);
                num = num - temp;
            }
        }
        return result;       
    }
}

2nd Round:
public class Solution {
    public String intToRoman(int num) {
        Map<Integer, String> dict = new HashMap<Integer, String>();
        dict.put(1, "I");
        dict.put(4, "IV");
        dict.put(5, "V");
        dict.put(9, "IX");
        dict.put(10, "X");
        dict.put(40, "XL");
        dict.put(50, "L");
        dict.put(90, "XC");
        dict.put(100, "C");
        dict.put(400, "CD");
        dict.put(500, "D");
        dict.put(900, "CM");
        dict.put(1000, "M");
        int[] key = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000};
        StringBuilder sb = new StringBuilder();
        int index = key.length - 1;
        while (num > 0) {
            while (num >= key[index]) {
                sb.append(dict.get(key[index]));
                num -= key[index];
            }
            index--;
        }
        return sb.toString();
    }

}

[LeetCode] Container with Most Water

Thought:
Calculate from both side leads to a O(n) solution.

Code:
public class Solution {
    public int maxArea(int[] height) {
        int i = 0;
        int j = height.length - 1;
        int result = 0;
        while( i < j ){
            result = Math.max( Math.min(height[i], height[j]) * (j - i), result);
            if(height[i] < height[j]){
                i++;
            }else{
                j--;
            }
        }
        return result;       
    }
}

[LeetCode] Regular Expression Matching

Thought: 
It is a 2-dimentional Dynamic Programming.

Code:
public class Solution {
    public boolean isMatch(String s, String p) {
 
        int m = s.length() + 1;
        int n = p.length() + 1;
        boolean[][] result = new boolean[n][m];
       
        result[0][0] = true;              
        for( int i = 1; i < n; i++){
            result[i][0] = p.charAt(i-1) == '*' ? result[i-2][0] : false;
        }
        for( int j = 1; j < m; j++){
            result[0][j] = s.charAt(j-1) == '*' ? result[0][j-2] : false;
        }
        for( int i = 1; i < n; i++ ){
            for( int j = 1; j < m; j++ ){
                if(p.charAt(i-1) == '*')
                    result[i][j] = match(s.charAt(j-1),p.charAt(i-2)) ? (result[i][j-1]||result[i-2][j]) : result[i-2][j];
                else
                    result[i][j] = match(s.charAt(j-1),p.charAt(i-1)) ? result[i-1][j-1] : false;
            }
        }
        return result[n-1][m-1];
    }
   
    boolean match(char a, char b){
        if(a == '.' || b == '.')
            return true;
        else
            return a == b;  
    }
}

[LeetCode] Palindrome Number

Thought:
Pick a base number which is the biggest 10^n smaller than x ->
Compare the Most Significant Bit and the Least Significant Bit ->
Remove the MSB and the LSB from x ->
Update the base number ->
Result
 
Code:
public class Solution {
    public boolean isPalindrome(int x) {
        if( x < 0 ) return false;
       
        int base = 1;
        int temp = x;
       
        while( temp/10 != 0 ){
            base = base * 10;
            temp = temp / 10;
        }
       
        while( base > 1 ){
            int MSB = x / base;
            int LSB = x % 10;
            if( MSB != LSB ) return false;
            x = x % base;
            x = x / 10;
            base = base / 100;           
        }
        return true;       
    }
}

[LeetCode] String to Integer

Thought:
Skip whitespace -> Check Sign -> Check Digit -> Check Overflow -> Result
When dealing with overflow, we could write  neither 
result * 10 > Integer.MAX_VALUE - temp nor  
result * 10 + temp > Integer.MAX_VALUE 
Because both of their left side might overflows which will lead to the wrong answer.

Code:
public class Solution {
    public int atoi(String str) {
      
        int i = 0, result = 0, sign = 1;
        char c = ' ';
      
        while (i  < str.length()) {
            c = str.charAt(i);
            if (Character.isWhitespace(c)) {
                i++;
            }else if (c == '+' || c == '-' ) {
                i++;
                if( c == '-' ) sign = -1;
                break;
            }else if(Character.isDigit(c)){
                break;
            }else{
                return 0;          
            }
        }      
        while (i < str.length()) {
            c = str.charAt(i);
            if (!Character.isDigit(c)){
                break;
            }else{
                int temp = Character.digit(c, 10);
                if( result > (Integer.MAX_VALUE - temp)/10 ){
                    return sign < 0? Integer.MIN_VALUE: Integer.MAX_VALUE;
                }else{
                    result = result * 10 + temp;
                }
            }
            i++;
        }
      
        return sign * result;
    }
}

[LeetCode] Reverse Integer

Thought:
If a positive number reverse to a negative one, it means overflow in my opinion.
Zero is a special number that none of the integer's reverse is zero, so I chose it as the flag of overflow.

Code:
public class Solution {
    public int reverse(int x) {
        boolean isNegative = false;
        if( x < 0) {
            isNegative = true;
            x = -x;       
        }
       
        int result = 0;
        while( x / 10 != 0 ){
            int LSB = x % 10;
            x = x / 10;
            result = result * 10 + LSB;
        }
        result = result * 10 + x;
       
        if( result < 0 ){//overflow
            return 0;
        }
       
        if( isNegative ){
            return -result;
        }else{
            return result;
        }
    }
}

[LeetCode] ZigZag Conversion

Thought:
For the first and last row, we add one character per cycle, the cycle distance is 2*nRows -2.
While for the other rows, we add two character per cycle, the distance between two added characters is 2*nRows -2 - 2*i.

Code:
public class Solution {
    public String convert(String s, int nRows) {
        String result = "";
        int index = 0;
        if( s.length() == 0 || nRows == 1 ){
            return s;
        }
        for( int i = 0; i < nRows; i++ ){
            if( i == 0 || i == nRows - 1 ){// add one elements per cycle
                for( int j = 0; ; j++ ){
                    index = i + j * ( 2 * nRows - 2 );
                    if( index >= s.length() ){
                        break;
                    }
                    result = result.concat( s.substring( index, index + 1 ) );
                }
            }else{// add two elements per cycle
                for( int j = 0; ; j++ ){
                    index = i + j * ( 2 * nRows - 2);
                    if( index >= s.length() ){
                        break;
                    }
                    result = result.concat( s.substring( index, index + 1 ) );
                    index = index + 2 * nRows - 2 * i -2;
                    if( index >= s.length() ){
                        break;
                    }
                    result = result.concat( s.substring( index, index + 1 ) );
                }
            }          
        }
        return result;       
    }
}

[LeetCode] Longest PalinDromic Substring

Thought: 
    It is not difficult to come up with the idea to populate every character and expand along its two sides. This method will get a O(n^2) time complexity.
    There surprisingly exists a very nontrivial algorithm here whose time complexity is O(n)! Manacher’s Algorithm

Code:
public class Solution {
    public String longestPalindrome(String s) {
        String input = preProcess(s);
        int len = input.length();
        int[] P = new int[len];
        int center = 0, right = 0;
        for( int i = 1; i < len - 1; i++ ){
            int j = 2 * center - i;
            P[i] = right > i? Math.min( right - i, P[j] ): 0;
            while( input.charAt(i + P[i] + 1) == input.charAt(i - P[i] - 1) ){
                P[i]++;
            }
            if( i + P[i] > right){
                right = i + P[i];
                center = i;
            }
        }        
        int resultc = 0, resultl = 0;
        for( int i = 0 ; i < len; i++ ){
            if(P[i]>resultl){
                resultc = i;
                resultl = P[i];
            }
        }        
        return s.substring( (resultc - resultl - 1)/2, (resultc + resultl)/2 - 0 );
    }
    public String preProcess(String s){
        String temp = "!#";
        for( int i = 0; i < s.length(); i++ ){
            temp = temp + s.substring(i, i + 1);
            temp = temp + "#";
        }
        temp = temp + "@";
        return temp;
    }
}

[Cracking The Code Interview] 1-1

Description:
Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

Thoughts: 
If we could use arrays, it is trivial to implement. Without additional data structures,  we could pick up a int variable and use bit manipulation to trace whether a character has shown up in the string before.

Code:
public static boolean IsUniqueChar(String s){ //Use an extra array 
boolean[] char_set = new boolean[256];
for(int i = 0; i < s.length(); i++){
int tmp = s.charAt(i);
if(char_set[tmp]){
return false;
}
char_set[tmp] = true;
}
return true;
}
public static boolean IsUniqueChar2(String s){ // Use bit manipulation
        int flag = 0;
for(int i = 0; i <s.length(); i++){
int tmp = s.charAt(i) - 'a';
if( (flag & (1<<tmp)) > 0 ){
return false;
}
flag = flag | (1<<tmp) ;
}
return true;
}

[LeetCode] Add Two Numbers

Thoughts: 
    Use a easy tail recursion taking the carry bit into consideration.

Code:
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        return add(l1, l2, 0);
    }
    public ListNode add(ListNode l1, ListNode l2, int carry){
        ListNode result = null;
        int temp = 0;
        if( l1 != null && l2 != null){
            int val = l1.val + l2.val + carry;
            result = new ListNode(val%10);
            temp = val > 9? 1: 0;
            result.next = add(l1.next, l2.next, temp);
        }else if( l1 == null && l2 != null){           
            int val = l2.val + carry;
            result = new ListNode(val%10);
            temp = val > 9? 1: 0;
            result.next = add(null, l2.next, temp);
        }else if( l1 != null && l2 == null){
            int val = l1.val + carry;
            result = new ListNode(val%10);
            temp = val > 9? 1: 0;
            result.next = add(l1.next, null, temp);
        }else{
            if( carry == 1 ){
                result = new ListNode(carry);
            }
        }
        return result;
    }
}

[LeetCode] Longest Substring Without Repeating Characters

Thought:
    Try to implement a O(n) method using just one scan of the String.
    Use a HashMap to track which letter has occured.

Code:

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max = 0;
        int length = 0;
        HashMap<Character, Integer> index = new HashMap<Character, Integer>();
        for( int i = 0; i < s.length(); i++ ){
            char temp = s.charAt(i);
            if( !index.containsKey(temp) ){
                index.put(temp,i);
                length++;
                max = Math.max(length, max);
            }else{
                i = index.get(temp);
                index.clear();
                length = 0;
            }
        }
        return max;
    }
}

[LeetCode] Median of Two Sorted Arrays

Thought:
    The O(m+n) solution is trivial. However, we could improve it to O(lg(m+n)) by using kind of divide and conquer method.
    The key is to note that: when we remove the same amount of values from the start and end of a sorted array, its median remains the same.
    We could directly compare the median of array A and array B( respectively A[i] and B[j]) in O(1) time, and then remove some values before A[i] and after B[j](or before B[j] and after A[i]---- it depends on the size of A and B actually). By this way, we quickly decrease the problem size.
    While the most difficult part of this problem is to consider the base case and code them out. Believe in yourself and code them out!

Code(all the max and min method could be expanded to be easier to understand):
public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        double result = 0;
        int m = A.length;
        int n = B.length;
        if( m == 0 ){
            result = B[n/2] + B[(n-1)/2];
            result = result/2;
        }else if( n == 0 ){
            result = findMedianSortedArrays(B, A);
        }else if( m == 1 ){
            if( n%2 == 0 ){
                result = Math.min( B[n/2], Math.max(A[0], B[n/2-1]) );                 
            }else{
                if( n == 1 ){
                    result = A[0] + B[0];
                }else{
                    result = B[n/2] + Math.min( B[n/2+1], Math.max(A[0], B[n/2-1]) );  
                }
                result = result/2;
            }
        }else if( n == 1 ){
            result = findMedianSortedArrays(B, A);
        }else if( m == 2){
            if( n == 2 ){
                result = Math.max(A[0],B[n/2-1]) + Math.min(A[1],B[n/2]);
                result = result/2;
            }else if( n%2 == 0 ){
                result = Math.max(B[n/2-2], Math.min(A[1], B[n/2])) + Math.min(B[n/2+1], Math.max(A[0],B[n/2-1]));
                result = result/2;            
            }else{
                result = Math.max(B[n/2-1], Math.min(B[n/2+1], Math.max(A[0], Math.min(B[n/2], A[1]))));
            }
        }else if( n == 2){
            result = findMedianSortedArrays(B, A);
        }else{
            int temp = (Math.min(m, n)-1)/2;
            if(A[m/2] < B[n/2]){                
                A = Arrays.copyOfRange(A, temp, m);
                B = Arrays.copyOfRange(B, 0, n-temp); 
            }else{
                A = Arrays.copyOfRange(A, 0, m-temp);
                B = Arrays.copyOfRange(B, temp, n);
            }
            result = findMedianSortedArrays(A, B);
        }
        return result;
    }
}