Add Binary

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".
Solution:

两个字符串从最后一位开始加，如果遇见长度不一的情况，就把短的字符串高位补0.

每轮计算要加上进位，最后跳出循环后要检查进位是否为1，如果为1，别忘了加在结果的最左位。

public class Solution {
    public String addBinary(String a, String b) {
        int aLen = a.length();
        int bLen = b.length();
        int len = Math.max(aLen, bLen);
        int carry = 0;
        StringBuilder res = new StringBuilder();
        
        for(int i = 0; i < len; i++) {
            int aDigit = 0, bDigit = 0;
            if(i < aLen) {
                aDigit = a.charAt(aLen - i - 1) - '0';
            }else {
                aDigit = 0;
            }
            if(i < bLen) {
                bDigit = b.charAt(bLen - i - 1) - '0';
            }else {
                bDigit = 0;
            }
            
            int temp = aDigit + bDigit + carry;
            carry = temp / 2;
            res.insert(0, Integer.toString(temp % 2));  //remember to insert in the front!
        }
        
        if(carry == 0) {
            return res.toString();
        }else {
            res.insert(0, Integer.toString(1));
            return res.toString();
        }
        
    }
}

Or
Main idea is 2 steps, 1. Check the length of each string and add "0" to the shorter one. 2.Add the two string, using a carry .

public class Solution {
    public String addBinary(String a, String b) {
        if(a == null || a.length() == 0)
            return b;
        else if(b == null || b.length() == 0)
            return a;
        
        int alength = a.length();
        int blength = b.length();
        int length;
        if(alength >= blength) {
            for(int i = 0; i < (alength - blength); i++) {
                b = "0" + b;
            }
            length = alength;
        }else {
            for(int i = 0; i < (blength - alength); i++) {
                a = "0" + a;
            }
            length = blength;
        }
        
        String result = "";
        boolean carry = false;
        
        for(int i = length - 1; i >= 0; i--) {
            if(a.charAt(i) == '1' && b.charAt(i) == '1') {
                if(carry) {
                    result = "1" + result;
                    carry = true;
                }else if(!carry) {
                    result = "0" + result;
                    carry = true;
                }
            }else if(a.charAt(i) == '1' && b.charAt(i) == '0') {
               if(carry) {
                   result = "0" + result;
                   carry = true;
               }else if(!carry) {
                   result = "1" + result;
                   carry = false;
               } 
            }else if(a.charAt(i) == '0' && b.charAt(i) == '1') {
                if(carry) {
                   result = "0" + result;
                   carry = true;
               }else if(!carry) {
                   result = "1" + result;
                   carry = false;
               } 
            }else if(a.charAt(i) == '0' && b.charAt(i) == '0') {
                if(carry) {
                   result = "1" + result;
                   carry = false;
               }else if(!carry) {
                   result = "0" + result;
                   carry = false;
               }  
            }
        }
        if(carry)
            result = "1" + result;
        
        return result;
    }
}

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution1: Dynamic programming

用recursion会time limit exceeded.  用DP可以避免计算重复信息，递推公式：f(n) = f(n-1)+f(n-2)

public class Solution {
    public int climbStairs(int n) {
        if(n == 0)
            return 0;
        if(n < 2) 
            return 1;

        int[] res = new int[n + 1];
        res[0] = 1;
        res[1] = 1;
        for(int i = 2; i <= n; i++) {
            res[i] = res[i - 1] + res[i - 2];
        }
        return res[n];
    }
}

Solution2: 斐波那契数列

public class Solution {
    public int climbStairs(int n) {
        int f1 = 1;
        int f2 = 2;
        if(n == 1)
            return f1;
        if(n == 2)
            return f2;
        
        for(int i = 3; i <= n; i++) {
            int f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        
        return f2;
    }
}

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Solution:

这道题跟Remove Duplicates from Sorted List比较类似，只是这里要把出现重复的元素全部删除。其实道理还是一样，只是现在要把前驱指针指向上一个不重复的元素中，如果找到不重复元素，则把前驱指针指向该元素，否则删除此元素。算法只需要一遍扫描，时间复杂度是O(n)，空间只需要几个辅助指针，是O(1)。

一般会改到链表头的题目就会需要一个辅助指针, 比如这里的newHead.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null)
            return null;
        
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        ListNode pre = newHead;
        ListNode cur = head;
        
        while(cur != null) {
            while(cur.next != null && pre.next.val == cur.next.val) {
                cur = cur.next;
            }
            
            if(pre.next == cur) {
                pre = pre.next;
            }else {
                pre.next = cur.next;
            }
            cur = cur.next;
        }
        return newHead.next;
    }
}

Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and respectively.

Solution:
从后往前填空。

public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        int k = m + n - 1;
        int i = m - 1;
        int j = n - 1;
        for(; i >= 0 && j >= 0; k--) {
            if(A[i] >= B[j]) {
                A[k] = A[i];
                i--;
            }else {
                A[k] = B[j];
                j--;
            }
        }
        while(j >= 0) {
            A[k] = B[j];
            k--;
            j--;
        }
    }
}

Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Solution: recursion
用一个整数来做返回值，0或者正数表示树的深度，-1表示此树已经不平衡了。
如果已经不平衡，则递归一直返回-1即可。
否则就利用返回的深度信息看看左右子树是不是违反平衡条件，如果违反返回-1。
否则返回左右子树深度大的加一作为自己的深度即可。
Run time complexity is O(n), space complexity is stack space O(logn).

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        return helper(root) >= 0;
    }
    
    public int helper(TreeNode root) {
        if(root == null)
            return 0;
            
        int left = helper(root.left);
        int right = helper(root.right);
        
        //如果不balance，会返回-1，所以只要left或者right小于0，就说明不balance了。
        //balance的话会返回深度，一定是一个正数。
        if(left < 0 || right < 0) {   
            return -1;
        }
        
        if(Math.abs(left - right) > 1) {
            return -1;
        }
        
        return Math.max(left, right) + 1;
    }
}

Reference：http://blog.csdn.net/linhuanmars/article/details/23731355
Or

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null)
            return true;
        
        int depthL = getDepth(root.left);
        int depthR = getDepth(root.right);
        if(Math.abs(depthL - depthR) > 1) {
            return false;
        }else {
            boolean balancedL = isBalanced(root.left);
            boolean balancedR = isBalanced(root.right);
            return balancedL && balancedR;
        }
    }
    
    public int getDepth(TreeNode root) {
        if(root == null)
            return 0;
        return Math.max(getDepth(root.left), getDepth(root.right)) + 1;
    }
}

Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Solution1: recursion
Run time complexity is O(n), stack space.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null)
            return 0;
        else
            return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

Solution2: iterative
BFS。一直走到最后再返回深度。

Run time complexity is O(n), space complexity is O(n).

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null)
            return 0;
        
        LinkedList queue = new LinkedList();
        int lastNum = 1;
        int curNum = 0;
        int level = 0;
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            lastNum--;
            if(cur.left != null) {
                queue.offer(cur.left);
                curNum++;
            }
            if(cur.right != null) {
                queue.offer(cur.right);
                curNum++;
            }
            if(lastNum == 0) {
                lastNum = curNum;
                curNum = 0;
                level++;
            }
        }
        return level;
    }
}

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Solution1: recursion
如果一个节点只有左子树或者右子树，不能取它左右子树中小的作为深度，因为那样会是0。只有在叶子节点才能判断深度。
Run time complexity is O(n), stack space since it's recursion.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) 
            return 0;
        
        if(root.left == null) {
            return minDepth(root.right) + 1;
        }
        
        if(root.right == null) {
            return minDepth(root.left) + 1;
        }
        
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }
}

Solution2: iterative
相当于BFS。找到第一个叶子节点就返回。
Run time complexity is O(n), space complexity is O(n).

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) 
            return 0;
        
        LinkedList queue = new LinkedList();
        int curNum = 0;
        int lastNum = 1;
        int level = 1;
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur.left == null && cur.right == null) {  //找到第一个叶子节点就返回
                return level;
            }
            lastNum--;
            if(cur.left != null) {
                queue.offer(cur.left);
                curNum++;
            }
            if(cur.right != null) {
                queue.offer(cur.right);
                curNum++;
            }
            if(lastNum == 0) {
                lastNum = curNum;
                curNum = 0;
                level++;
            }
        }
        return level;
    }
}

Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Try to do this in one pass.

Solution:
两个指针fast和slow，fast先走n步，然后两个再一起走，当fast走到最后一个的时候，slow指的就是倒数第n个节点。

Run time complexity is O(n), constant space.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null || head.next == null) {  //if only has one node, after removed, it will be null
            return null;
        }
        
        ListNode fast = head;
        ListNode slow = head;
        while(n != 0) {
            fast = fast.next;
            n--;
        }
        
        if(fast == null) {  //fast==null means the node which need to be removed is the head
            head = head.next;
            return head;
        }
        
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        
        slow.next = slow.next.next;

        return head;
    }
}

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.
Solution:
就是brute force的想法，以第一个字符串为标准，对于每个字符串从第一个字符开始，看看是不是和标准一致，如果不同，则跳出循环返回当前结果，否则继续下一个字符。
时间复杂度应该是O(m*n)，m表示字符串的最大长度，n表示字符串的个数，空间复杂度应该是O(m),即字符串的长度.

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0 || hasEmpty(strs))  //if strs has empty string, return ""
            return "";
        if(strs.length == 1) 
            return strs[0];
        
        String str1 = strs[0];
        for (int i = 0; i < str1.length(); i++) {
            char temp = str1.charAt(i); 
            
            for (int j = 1; j < strs.length; j++) {
                if (i > strs[j].length() - 1 || strs[j].charAt(i) != temp) {
                    return str1.substring(0, i);
                }
            }
        }
        return str1;
    }
    
    public boolean hasEmpty(String[] strs){
        for(int i = 0; i < strs.length; i++){
            if(strs[i].length() == 0)
                return true;
        }
        return false;
    }
}

Or

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        StringBuilder res = new StringBuilder();
        if(strs == null || strs.length == 0)
            return res.toString();
        
        int index = 0;
        boolean isSame = true;
        while(isSame) {
            for(int i = 0; i < strs.length; i++) {
                if(strs[i].length() <= index || strs[i].charAt(index) != strs[0].charAt(index)) {
                    isSame = false;
                    break;
                }
            }
            if(isSame) {
                res.append(strs[0].charAt(index));
                index++;
            }
        }
        return res.toString();
    }
}

Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

click to show spoilers.

Some hints:

Could negative integers be palindromes? (ie, -1)

If you are thinking of converting the integer to string, note the restriction of using extra space.

You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?

There is a more generic way of solving this problem.

Solution:

对比第一位和最后一位，如果不同则返回false；相同，则去除第一位和最后一位，继续对比，直到0为止。

Run time complexity is O(n), constant space.

public class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0)
            return false;
        if(x < 10 && x >= 0)
            return true;
        
        int div = 1;
        while(div <= x / 10) {
            div *= 10;
        }
        
        while(x != 0) {
            if(x / div != x % 10) {  //if first digit != last digit, return false
                return false;
            }
            x = (x % div) / 10;  //get rid of first digit and last digit
            div /= 100;
        }
        
        return true;
    }
}

String to Integer (atoi)

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front. 

spoilers alert... click to show requirements for atoi.

Requirements for atoi:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

Solution1:

1. null or empty string
2. white spaces
3. +/- sign
4. handle min and max
5. calculate real value

Run time complexity is O(n).

public class Solution {
    public int atoi(String str) {
        if(str == null || str.length() == 0)
            return 0;
        
        //deal with string only contains space
        str = str.trim(); 
        if(str.length() == 0)
            return 0;
        
        //deal with sign
        boolean isNeg = false;
        int i = 0;
        if(str.charAt(0) == '-' || str.charAt(0) == '+') {
            i++;
            if(str.charAt(0) == '-') {
                isNeg = true;
            }
        }
        
        double res = 0;
        while(i < str.length()) {
            if(str.charAt(i) < '0' || str.charAt(i) > '9') {  //deal with special characters
                break;
            }
            
            double digit = str.charAt(i) - '0';
            if(isNeg && res > (-(Integer.MIN_VALUE + digit) / 10))  //deal with MIN_VALUE
                return Integer.MIN_VALUE;
            if(!isNeg && res > ((Integer.MAX_VALUE - digit) / 10))  //deal with MAX_VALUE
                return Integer.MAX_VALUE;
            
            res = res * 10 + digit;  //calculate value
            i++;
        }
        
        if(isNeg)
            return (int)-res;
        
        return (int)res;
    }
}

Solution2:

In each step we are appending a digit to the number by doing a multiplication and addition. If the current number is greater than 214748364, we know it is going to overflow. On the other hand, if the current number is equal to 214748364, we know that it will overflow only when the current digit is greater than or equal to 8. Remember to also consider edge case for the smallest number, –2147483648 (–231).

public class Solution {
    private static final int maxDiv10 = Integer.MAX_VALUE / 10;
    
    public int atoi(String str) {
        int i = 0, n = str.length();
        while(i < n && Character.isWhitespace(str.charAt(i))) {
            i++;
        }
        
        int sign = 1;
        if(i < n && str.charAt(i) == '-') {
            sign = -1;
            i++;
        }else if(i < n && str.charAt(i) == '+') {
            i++;
        }
        
        int result = 0;
        while(i < n && Character.isDigit(str.charAt(i))) {
            int digit = Character.getNumericValue(str.charAt(i));
            if(result > maxDiv10 || result == maxDiv10 && digit >= 8) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            result = result * 10 + digit;
            i++;
        }
        return result * sign;
    }
}

Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Have you thought about this?

Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Update (2014-11-10):
Test cases had been added to test the overflow behavior.

Solution:

Reverse的公式: y = x % 10

                          result = result * 10 + y

注意Integer.MIN_VALUE的绝对值是比Integer.MAX_VALUE大1的。

Run time complexity is O(n), constant space.

public class Solution {
    public int reverse(int x) {
        if(x == Integer.MIN_VALUE)
            return 0;

        int num = Math.abs(x);
        int res = 0;
        while(num != 0) {
            if(res > (Integer.MAX_VALUE - num % 10) / 10) {
                return 0;
            }
            res = res * 10 + num % 10;
            num /= 10;
        }

        if(x < 0) {
            return -res;
        }
        return res;
    }
}

Reference: http://blog.csdn.net/linhuanmars/article/details/20024837

ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
Solution: 
所有行的重复周期都是 gap = 2 * nRows - 2

对于首行和末行之间的行，还会额外重复一次，重复的这一次距离本周期起始字符的距离是 gap - 2 * i.
Run time complexity is O(n), constant space.

public class Solution {
    public String convert(String s, int nRows) {
        if(s == null || s.length() == 0 || nRows <= 0) {
            return "";
        }
        if(nRows == 1) {
            return s;
        }
        
        StringBuilder res = new StringBuilder();
        int gap = 2 * nRows - 2;
        for(int i = 0; i < nRows; i++) {
            for(int j = i; j < s.length(); j += gap) {
                res.append(s.charAt(j));
                if(i != 0 && i != nRows - 1 && j + gap - 2*i < s.length()) {
                    res.append(s.charAt(j + gap - 2*i));
                }
            }
        }
        return res.toString();
    }
}

Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Solution1: hashmap

Use a hashmap to store element and the times it appears. Key is element, value is the times it appears. 

Store into hashmap is O(n), look for the majority element is O(n). So run time complexity is O(2n) = O(n). Space complexity is O(n).

public class Solution {
    public int majorityElement(int[] num) {
        HashMap map = new HashMap();
        for(int n : num) {
            if(map.containsKey(n)) {
                map.put(n, map.get(n) + 1);
            }else {
                map.put(n, 1);
            }
        }
        
        for(int element : map.keySet()) {
            if(map.get(element) > num.length / 2) {
                return element;
            }
        }
        
        return -1;
    }
}

Solution2: optimize the space complexity to constant space.
Sort the array first, since majority element appears more than n/2 times. So the n/2 element in the array must be the majority element. We just need to return the middle element.
Sort array takes O(nlogn), so run time complexity is O(nlogn), constant space.

public class Solution {
    public int majorityElement(int[] num) {
        Arrays.sort(num);
        return num[num.length / 2];
    }
}

Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 

Solution:

相当于10进制转26进制。对应的时候注意26进制里最小的对应10进制里的1, 而不是0， 所以在while循环中要n--。

Run time complexity is O(n), constant space.

public class Solution {
    public String convertToTitle(int n) {
        if(n <= 0) {
            throw new IllegalArgumentException("Input number is invalid!");
        }
        
        StringBuilder sb = new StringBuilder();
        while(n > 0) {
            n--;  //1->A
            char c = (char)(n % 26 + 'A');
            sb.append(c);
            n /= 26;
        }
        return sb.reverse().toString();
    }
}

Excel Sheet Column Number

Related to question Excel Sheet Column Title

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 

Solution:

可以看出规律是 number = number * 26 + s.charAt(i) - 'A' + 1

Run time complexity is O(n), constant space.

public class Solution {
    public int titleToNumber(String s) {
        if(s == null || s.length() == 0) {
            throw new IllegalArgumentException("Input string is invalid!");
        }
        
        int i = 0;
        int number = 0;
        while(i < s.length()) {
            number = number * 26 + s.charAt(i) - 65 + 1; // s.charAt(i)-'A'+1
            i++;
        }
        return number;
    }
}

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Solution:

A trailing zero is always produced by prime factors 2 and 5. If we can count the number of 5s and 2s, our task is done. However, the number of 2s is always equal to or more than the number of 5s. So we only need to count the number of 5s. 

问题转化为求阶乘过程中质因子5的个数，但是要注意25能提供2个5,125能提供3个5....count= floor(n/5) + floor(n/25) + floor(n/125) + ....

public class Solution {
    public int trailingZeroes(int n) {
        if(n == 0)
            return 0;
        
        int count = 0;
        for(long i = 5; n / i >= 1; i *= 5) {  //use long to avoid overflow
            count += n / i;
        }
        
        return count;
    }
}

Pascal's Triangle II

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

Solution1: 不限制空间
如果没有这个O(k)空间的限制，那么可以一行一行迭代生成。如果要直接生成第i行，假设生成k=3，可以这样考虑这样的一个过程：

1 0 0 0    k = 0

1 1 0 0    k = 1

1 1 1 0

1 2 1 0    k = 2

1 2 1 1

1 2 3 1

1 3 3 1    k = 3

上述过程实际上就是一个in-place的迭代过程。每当生成下一行的时候，首先数组相应位置1，然后从右向左计算每一个系数。

public class Solution {
    public ArrayList getRow(int rowIndex) {
        ArrayList current = new ArrayList();
        for(int i = 0; i <= rowIndex; i++) {
            current.add(0);
        }
        current.set(0, 1);
        
        for(int i = 1; i <= rowIndex; i++) {
            current.set(i, 1);
            for(int j = i - 1; j > 0; j--) {
                int temp = current.get(j) + current.get(j - 1);
                current.set(j, temp);
            }
        }
        return current;
    }
}

Solution2: only O(k) extra space
从后往前扫，每次需要的数据就是res[i]+res[i-1]，我们需要的数据不会被覆盖，因为需要的res[i]只在当前步用，下一步就不需要了。这个技巧在动态规划省空间时也经常使用，主要就是看我们需要的数据是原来的数据还是新的数据来决定我们遍历的方向。
时间复杂度还是O(n^2)，而空间这里是O(k)来存储结果。

public class Solution {
    public List getRow(int rowIndex) {
        ArrayList res = new ArrayList();
        if(rowIndex < 0) {
            return res;
        }
        
        res.add(1);
        for(int i = 1; i <= rowIndex; i++) {
            for(int j = res.size() - 2; j >= 0; j--) {
                res.set(j + 1, res.get(j) + res.get(j + 1));
            }
            res.add(1);
        }
        
        return res;
    }
}

Reference: http://blog.csdn.net/linhuanmars/article/details/23311629

Pascal's Triangle

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Solution:
当前行的元素是上一行相邻两个元素相加的值，每行第一个和最后一个元素是1。
时间复杂度应该是O(1+2+3+...+n)=O(n^2)，空间上只需要二维数组来存储结果，不需要额外空间。

public class Solution {
    public ArrayList> generate(int numRows) {
        ArrayList> res = new ArrayList>();
        if(numRows == 0) 
            return res;
            
        ArrayList pre = new ArrayList();
        pre.add(1);
        res.add(pre);
        for(int i = 2; i <= numRows; i++) {
            ArrayList cur = new ArrayList();
            cur.add(1);
            for(int j = 0; j < pre.size() - 1; j++) {
                cur.add(pre.get(j) + pre.get(j + 1));
            }
            cur.add(1);
            res.add(cur);
            pre = cur;
        }
        return res;
    }
}

Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
Solution:
因为在BST中，中序遍历是有序的。所以如果有元素被调换了，则中序遍历中必然出现逆序的情况。
分两种考虑，1. 如果是中序遍历相邻的两个元素被调换了，只会出现一次逆序的情况，只需要把这个两个节点记录下来最后调换值就可以；
2. 如果是不相邻的两个元素被调换，会发生两次逆序的情况，需要调换的元素应该是第一次逆序前面的元素，和第二次逆序后面的元素。比如1234567,1和5调换了，会得到5234167，逆序发生在52和41，所以是52的第一个元素，和41的第二个元素调换即可。
中序遍历寻找逆序情况，调换的第一个元素，是第一个逆序的第一个元素，调换的第二个元素如果只有一次逆序，则是那一次的后一个，如果有两次逆序则是第二次的后一个。
一次中序遍历，时间复杂度是O(n)，空间是栈大小O(logn)。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void recoverTree(TreeNode root) {
        if(root == null)
            return;
        
        ArrayList pre = new ArrayList();
        ArrayList res = new ArrayList();
        pre.add(null);
        helper(root, pre, res);
        if(res.size() != 0) {
            int temp = res.get(0).val;
            res.get(0).val = res.get(1).val;
            res.get(1).val = temp;
        }
    }
    
    public void helper(TreeNode root, ArrayList pre, ArrayList res) {
        if(root == null) {
            return;
        }
        
        helper(root.left, pre, res);
        if(pre.get(0) != null && pre.get(0).val > root.val) {
            if(res.size() == 0) {
                res.add(pre.get(0));
                res.add(root);
            }else {
                res.set(1, root);
            }
        }
        pre.set(0, root);
        helper(root.right, pre, res);
    }
}

Reference: http://blog.csdn.net/linhuanmars/article/details/24566995

Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Solution1: 2D dp

“When you see string problem that is about subsequence or matching, dynamic programming method should come to your mind naturally. ”

这道题思路是，s1取一部分s2取一部分，看最后是否能匹配s3。

定义一个boolean二维数组dp[i][j]表示： s1取前i位，s2取前j位，是否能组成s3的前i+j位。

首先，假设s2为空，将s1每一位跟s3匹配放入dp[i][0]；假设s1为空，将s2每一位跟s3匹配放入dp[0][j]。

如果不等就是False。

判断true的时候，第一个条件，新添加的字符，要等于s3里面对应的位( i + j 位)，第二个条件，之前那个格子也要等于True

举个简单的例子s1 = ab, s2 = c, s3 = bbc ，假设s1已经取了2位，c还没取，此时是False（ab!=bb），我们取s2的新的一位c，即便和s3中的c相等，但是之前是False，所以这一位也是False。

同理，如果s1 = ab, s2 = c, s3=abc ，同样的假设，s1取了2位，c还没取，此时是True（ab==ab），我们取s2的新的一位c,和s3中的c相等，且之前这一位就是True，此时我们可以放心置True （abc==abc）。
时间上因为是一个二维动态规划，所以复杂度是O(m*n)，m和n分别是s1和s2的长度。空间复杂度是O(m*n).

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1 == null || s2 == null || s3 == null)
            return false;
        if(s1.length() + s2.length() != s3.length())
            return false;
        
        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];
        dp[0][0] = true;
        
        for(int i = 1; i <= s1.length(); i++) {
            if(s1.charAt(i - 1) == s3.charAt(i - 1) && dp[i - 1][0]) {
                dp[i][0] = true; 
            }
        }
        
        for(int j = 1; j <= s2.length(); j++) {
            if(s2.charAt(j - 1) == s3.charAt(j - 1) && dp[0][j - 1]) {
                dp[0][j] = true;
            }
        }
        
        for(int i = 1; i <= s1.length(); i++) {
            for(int j = 1; j <= s2.length(); j++) {
                char c = s3.charAt(i + j - 1);
                if(c == s1.charAt(i - 1) && dp[i - 1][j]) {
                    dp[i][j] = true;
                }
                
                if(c == s2.charAt(j - 1) && dp[i][j - 1]) {
                    dp[i][j] = true;
                }
            }
        }
        
        return dp[s1.length()][s2.length()];
    }
}

Reference: http://blog.csdn.net/u011095253/article/details/9248073
Solution2: 1D dp
思路和soluton1一样，动态规划的递推式为：
res[i][j] = res[i-1][j]&&s1.charAt(i-1)==s3.charAt(i+j-1) || res[i][j-1]&&s2.charAt(j-1)==s3.charAt(i+j-1)
可以看出递推式中只需要用到上一行的信息，所以我们只需要一个一维数组就可以完成历史信息的维护，为了更加优化，把短的字符串放在内层循环，这样就可以只需要短字符串的长度即可，所以空间复杂度是O(min(m,n))。时间复杂度还是O(m*n)。

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1 == null || s2 == null || s3 == null)
            return false;
        if(s1.length() + s2.length() != s3.length())
            return false;
        
        String minStr = "";
        String maxStr = "";
        if(s1.length() > s2.length()) {
            minStr = s2;
            maxStr = s1;
        }else {
            minStr = s1;
            maxStr = s2;
        }
        
        boolean[] dp = new boolean[minStr.length() + 1];
        dp[0] = true;
        
        for(int i = 1; i <= minStr.length(); i++) {
            if(minStr.charAt(i - 1) == s3.charAt(i - 1) && dp[i - 1]) {
                dp[i] = true; 
            }
        }
        
        for(int i = 1; i <= maxStr.length(); i++) {
            dp[0] = dp[0] && maxStr.charAt(i - 1) == s3.charAt(i - 1);
            for(int j = 1; j <= minStr.length(); j++) {
                dp[j] = dp[j] && maxStr.charAt(i - 1) == s3.charAt(i + j - 1) || dp[j - 1] && minStr.charAt(j - 1) == s3.charAt(i + j - 1);
            }
        }

        return dp[minStr.length()];
    }
}

Reference: http://blog.csdn.net/linhuanmars/article/details/24683159

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

Related problem: Reverse Integer

Solution1: 

Run time complexity is O(n), n = 32, so it's constant. Constant space.

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        if(n == 0) {
            return 0;
        }
        
        int result = 0;
        int x = 0;
        for(int i = 1; i < 32; i++) {  //处理前31位
            x = n & 1;
            result = (result + x) << 1;
            n = n >>> 1;
        }
        
        //处理最后一位
        x = n & 1;
        result += x;
        
        return result;
    }
}

Solution2:

Run time complexity is O(n), n = 16, so it's constant. Constant space.

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        if(n == 0) {
            return 0;
        }
        
        for(int i = 0; i < 16; i++) {
            n = swapBits(n, i, 32 - i - 1);
        }
        
        return n;
    }
    
    public int swapBits(int n, int i, int j) {
        int a = (n >>> i) & 1;
        int b = (n >>> j) & 1;
        
        if((a ^ b) != 0) {
            n = n ^ ((1 << i) | (1 << j));
            return n;
        }
        return n;
    }
}

Solution3: 

Divide and conquer: http://articles.leetcode.com/2011/08/reverse-bits.html