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;
    }
}