H-Index II

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

Hint:

1. Expected runtime complexity is in O(log n) and the input is sorted.

Solution: run time complexity is in O(log n)
取中间值mid，比较citations[mid]和length-mid做比较，如果前者大，则right移到mid之前，反之right移到mid之后，终止条件是left>right，最后返回length-left.

public class Solution {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) {
            return 0;
        }
        
        int l = 0;
        int r = citations.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (citations[mid] == citations.length - mid) {
                return citations.length - mid;
            }
            
            if (citations[mid] > citations.length - mid) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        
        return citations.length - l;
    }
}

H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Hint:

1. An easy approach is to sort the array first.
2. What are the possible values of h-index?
3. A faster approach is to use extra space.

Solution: run time complexity is O(n), constant space
定义为一个人的学术文章有n篇分别被引用了n次，那么H指数就是n。
按照如下方法确定某人的H指数：1、将其发表的所有SCI论文按被引次数从高到低排序；2、从前往后查找排序后的列表，直到某篇论文的序号大于该论文被引次数。所得序号减一即为H指数。

public class Solution {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) {
            return 0;
        }
        
        Arrays.sort(citations);
        int l = 0;
        int r = citations.length - 1;
        // reverse array
        while (l < r) {
            int temp = citations[l];
            citations[l] = citations[r];
            citations[r] = temp;
            l++;
            r--;
        }
        
        for (int i = 0; i < citations.length; i++) {
            // 从前往后查找排序后的列表，直到某篇论文的序号大于该论文被引次数。所得序号减一即为H指数。
            if (i >= citations[i]) {
                return i;
            }
        }
        return citations.length;
    }
}

Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Solution:

这道题跟Merge Intervals很类似，都是关于数据结构interval的操作。事实上，Merge Intervals是这道题的子操作，就是插入一个interval，如果出现冲突了，就进行merge。跟Merge Intervals不一样的是，这道题不需要排序，因为插入之前已经默认这些intervals排好序了。简单一些的是这里最多只有一个连续串出现冲突，因为就插入那么一个。

基本思路就是先扫描走到新的interval应该插入的位置，接下来就是插入新的interval并检查后面是否冲突，一直到新的interval的end小于下一个interval的start，然后取新interval和当前interval中end大的即可。因为要进行一次线性扫描，所以时间复杂度是O(n)。而空间上如果我们重新创建一个ArrayList返回，那么就是O(n)。有朋友可能会说为什么不in-place的进行操作，这样就不需要额外空间，但是如果使用ArrayList这个数据结构，那么删除操作是线性的，如此时间就不是O(n)的。如果这道题是用LinkedList那么是可以做到in-place的，并且时间是线性的。

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList insert(ArrayList intervals, Interval newInterval) {
        ArrayList res = new ArrayList();
        if(intervals == null || intervals.size() == 0) {
            res.add(newInterval);
            return res;
        }
        
        int i = 0;
        
        //check新的start是否大于第i个的end，
        //是 则不需要merge，直接把第i个加进result
        while(i < intervals.size() && intervals.get(i).end < newInterval.start) {
            res.add(intervals.get(i));
            i++;
        }
        
        //如果新的start是小于第i个的end，新的start等于两个中小的那个
        if(i < intervals.size()) {
            newInterval.start = Math.min(newInterval.start, intervals.get(i).start);
        }
        res.add(newInterval); //add newInterval into result
        
        //如果新的end大于等于第i个的start，需要merge
        //新的end等于两个中大的那个
        while(i < intervals.size() && intervals.get(i).start <= newInterval.end) {
            newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
            i++;
        }
        
        while(i < intervals.size()) {
            res.add(intervals.get(i));
            i++;
        }
        
        return res;
    }
}

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

Solution:

假设这些interval是有序的（也就是说先按起始点排序，然后如果起始点相同就按结束点排序），那么要把它们合并就只需要按顺序读过来，如果当前一个和结果集中最后一个有重叠，那么就把结果集中最后一个元素设为当前元素的结束点（不用改变起始点因为起始点有序，因为结果集中最后一个元素起始点已经比当前元素小了）。那么剩下的问题就是如何给interval排序，在java实现中就是要给interval自定义一个Comparator，规则是按起始点排序，然后如果起始点相同就按结束点排序。整个算法是先排序，然后再做一次线性遍历，时间复杂度是O(nlogn+n)=O(nlogn)，空间复杂度是O(1)，因为不需要额外空间，只有结果集的空间。

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public ArrayList merge(ArrayList intervals) {
        if(intervals == null || intervals.size() == 0) 
            return intervals;
        
        ArrayList res = new ArrayList();
        
        //defining a Comparator first to sort the arraylist of Intevals
        Comparator comp = new Comparator() {
            @Override
            public int compare(Interval i1, Interval i2) {
                if(i1.start == i2.start)
                    return i1.end - i2.end;
                return i1.start - i2.start; 
            }
        };

        //sort intervals by using self-defined Comparator
        Collections.sort(intervals, comp); 
        
        Interval pre = intervals.get(0);
        for(int i = 1; i < intervals.size(); i++) {
            Interval cur = intervals.get(i);
            if(pre.end >= cur.start) {  //merge some intervals
                Interval merge = new Interval(pre.start, Math.max(pre.end, cur.end));
                pre = merge;
            }else {
                res.add(pre);
                pre = cur;
            }
        }
        res.add(pre);
        return res;
    }
}

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Solution1: 

public class Solution {
    public int trap(int[] A) {
        if(A == null || A.length == 0)
            return 0;
        
        int result = 0;
        int[] left = new int[A.length];   //left数组记录到当前i为止，左边最高的bar(包含i)
        int[] right = new int[A.length];   //right数组记录到当前i为止，右边最高的bar
        
        left[0] = A[0];
        for(int i = 1; i < A.length; i++) {
            left[i] = Math.max(left[i - 1], A[i]);
        }
        
        right[A.length - 1] = A[A.length - 1];
        for(int i = A.length - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], A[i]);
        }
        
        for(int i = 0; i < A.length; i++) {  
            //第i块地方的存水量 = min(第i块左边最高的bar高度, 第i块右边最高的bar的高度) - 第i块地方bar的高度
            result += Math.min(left[i], right[i]) - A[i];
        }
        return result;
    }
}

Solution2:

这种方法是基于动态规划的，基本思路就是维护一个长度为n的数组，进行两次扫描，一次从左往右，一次从右往左。第一次扫描的时候维护对于每一个bar左边最大的高度是多少，存入数组对应元素中，第二次扫描的时候维护右边最大的高度。这个方法只需要两次扫描，所以时间复杂度是O(2*n)=O(n)。空间上需要一个长度为n的数组，空间复杂度是O(n)。

public class Solution {
    public int trap(int[] A) {
        if(A == null || A.length == 0)
            return 0;
        
        int result = 0;
        int max = 0;
        int[] container = new int[A.length];
        
        for(int i = 0; i < A.length; i++) {
            container[i] = max;
            max = Math.max(max, A[i]);
        }
        
        max = 0;
        for(int i = A.length - 1; i >= 0; i--) {
            container[i] = Math.min(container[i], max);
            max = Math.max(max, A[i]);
            if(container[i] - A[i] > 0)
                result += container[i] - A[i];
            else
                result += 0;
        }
        
        return result;
    }
}

Solution3:

只需要一次扫描就能完成。基本思路是这样的，用两个指针从两端往中间扫，在当前窗口下，如果哪一侧的高度是小的，那么从这里开始继续扫，如果比它还小的，肯定装水的瓶颈就是它了，可以把装水量加入结果，如果遇到比它大的，立即停止，重新判断左右窗口的大小情况，重复上面的步骤。这里能作为停下来判断的窗口，说明肯定比前面的大了，所以目前肯定装不了水（不然前面会直接扫过去）。这样当左右窗口相遇时，就可以结束了，因为每个元素的装水量都已经记录过了。这个算法每个元素只被访问一次，所以时间复杂度是O(n)，并且常数是1，比前面的方法更优一些。

public class Solution {
    public int trap(int[] A) {
        if(A == null || A.length == 0)
            return 0;
        
        int result = 0;
        int l = 0, r = A.length - 1;
        
        while(l < r) {
            int min = Math.min(A[l], A[r]);
            if(A[l] == min) {
                l++;
                while(l < r && A[l] < min) {
                    result += min - A[l];
                    l++;
                }
            }else {
                r--;
                while(l < r && A[r] < min) {
                    result += min - A[r];
                    r--;
                }
            }
        }
        return result;
    }
}

Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Solution: binary search, complexity is O(log n), space complexity is O(1).

假设数组是A，每次左边缘为l，右边缘为r，还有中间位置是m。在每次迭代中，分三种情况：
（1）如果target==A[m]，那么m就是我们要的结果，直接返回；
（2）如果A[m]<A[r]，那么说明从m到r一定是有序的（没有受到rotate的影响），那么我们只需要判断target是不是在m到r之间，如果是则把左边缘移到m+1，否则就target在另一半，即把右边缘移到m-1。
（3）如果A[m]>=A[r]，那么说明从l到m一定是有序的，同样只需要判断target是否在这个范围内，相应的移动边缘即可。

public class Solution {
    public int search(int[] A, int target) {
        if(A == null || A.length == 0)
            return -1;
        
        int L = 0, R = A.length - 1;
        while(L <= R) {
            int mid = (L + R) / 2;
            
            if(A[mid] == target)
                return mid;
            
            if(A[L] <= A[mid]) {
                if(target >= A[L] && target <= A[mid])
                    R = mid;
                else
                    L = mid + 1;
            }else {
                if(target <= A[R] && target >= A[mid])
                    L = mid + 1;
                else
                    R = mid;
            }
        }
        return -1;
    }
}

Add Two Numbers

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

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

Solution: run time complexity is O(n), space complexity is O(n), 储存结果用的空间。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null)
            return l2;
        else if(l2 == null)
            return l1;
        
        ListNode result = new ListNode(-1);
        ListNode c1 = l1;
        ListNode c2 = l2;
        ListNode cR = result; 
        int carry = 0;
        
        while(c1 != null || c2 != null) {
            if(c1 != null) {
                carry += c1.val;
                c1 = c1.next;
            }
            if(c2 != null) {
                carry += c2.val;
                c2 = c2.next;
            }
            if(carry >= 10) {
                cR.next = new ListNode(carry - 10);
                carry = 1;
            }else {
                cR.next = new ListNode(carry);
                carry = 0;
            }
            cR = cR.next;
        }
        if(carry == 1)
            cR.next = new ListNode(1);
        
        return result.next;
    }
}

LinkedList addition

Add 2 linkedlists without reverse in O(n) and constant space.

eg: 1->2->3 + 1->7 = 1->4->0

Solution: recursion
1. 在短的list前面补0使得两个list一样长
2. recursively add two lists
3. 处理第一位，如果第一位是0，说明第一位原本>=10, 在前面加1
相似的leetcode问题：Add Two Numbers

public class LinkedListAddition {
    // carry must defined as global variable
    public static int carry = 0;
       
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }
       
    // create new node
    ListNode newNode(int x) {
        ListNode node = new ListNode(x);
        node.val = x;
        node.next = null;
        return node;
    }
       
    public static void main(String[] args) {
        LinkedListAddition list = new LinkedListAddition();
               
        // create 1->2->3
        ListNode l1 = list.newNode(1);
        l1.next = list.newNode(2);
        l1.next.next = list.newNode(3);

        // create 1->7
        ListNode l2 = list.newNode(1);
        l2.next = list.newNode(7);
               
        // print linkedlist
        System.out.println("Two input LinkedList: ");
        printLinkedList(l1);
        printLinkedList(l2);
               
        // insert 0 to make shorter list has the same length as the longer list
        int len1 = len(l1);
        int len2 = len(l2);
        int diff = Math.abs(len1 - len2);
        ListNode newL2;
        ListNode newL1;
        if (len1 > len2) {
            ListNode node = list.newNode(0);
            newL2 = node;
            diff--;
            while (diff > 0) {
                node.next = list.newNode(0);
                node = node.next;
                diff--;
            }
            node.next = l2;
            System.out.print("newL2: ");
            printLinkedList(newL2);
                       
            // recursively add two lists
            addList(l1, newL2);
        } else if (len1 < len2) {
            ListNode node = list.newNode(0);
            newL1 = node;
            diff--;
            while (diff > 0) {
                node.next = list.newNode(0);
                newL1 = node.next;
                diff--;
            }
            node.next = l1;
            System.out.print("newL1: ");
            printLinkedList(newL1);
                       
            // recursively add two lists
            addList(newL1, l2);
        } else {
            // recursively add two lists
            addList(l1, l2);
        }
                               
        System.out.print("After adding, l1 is: ");
        printLinkedList(l1);
               
        // if first digit is 0 means it is >= 10, need to deal with this carry
        if (l1.val == 0) {
            ListNode newHead = list.newNode(1);
            newHead.next = l1;
            System.out.print("Result: ");
            printLinkedList(newHead);
        }
    }
       
    public static ListNode addList(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l1;
        }
               
        addList(l1.next, l2.next);
 
        carry = l1.val + l2.val + carry;
        if (carry >= 10) {
            l1.val = carry - 10;
            carry = 1;
        } else {
            l1.val = carry;
            carry = 0;
        }
        return l1;     
    }
       
    public static int len(ListNode head) {
        int count = 0;
        ListNode node = head;
        while (node != null) {
            node = node.next;
            count++;
        }
        return count;
    }
       
    public static void printLinkedList(ListNode head) {
        ListNode node = head;
        while (node != null) {
            if (node.next == null) {
                System.out.print(node.val);
            } else {
                System.out.print(node.val + "->");
            }                  
            node = node.next;
        }
        System.out.println();
    }
}

Largest Subsquare

a) There is a square of nxn size which is comprised of n-square 1x1 squares.

Some of these 1x1 squares are colored. Find the biggest sub square which is not colored.
b) Also asked to extend it to find the biggest area rectangle.

Solution1:
1. take the colored squares as 0 and the non-colored squares as 1. then form a n*n matrix 'a'. 
2. now we have to find the largest square matrix having all 1's. 
3. fill up the 1st row of the result (n*n) matrix as the matrix 'a'. 
4. then from the second row on wards 
4.1. if you find a[i][j] == 0 then res[i][j] = 0. 
4.2. else res[i][j] = min(res[i-1][j], res[i][j-1], res[i-1][j-1])+1. 
5. after creating the 'res' matrix the size of largest uncolored square will be the largest element in the 'res' matrix. 

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

public class LargestSubmatrix {
    public static void main(String[] args) {
        int[][] arr = {{0,1,1,0,1,0},
                       {1,1,0,0,1,0},
                       {0,1,1,1,0,1},
                       {0,1,1,0,0,1},
                       {0,1,1,1,0,1}};
        int col = arr[0].length;
        int row = arr.length;
        int [][] res = new int [row][col];
        for (int i = 0; i < col; i++) {
            res[0][i] = arr[0][i];
        }
        for (int i = 0; i < row; i++) {
            res[i][0] = arr[i][0];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (arr[i][j] == 1) {
                    res[i][j] = Math.min(Math.min(res[i][j-1], res[i-1][j]), res[i-1][j-1]) + 1;
                } else {
                    res[i][j] = 0;
                }
            }
        }
 
        System.out.println("the distance matrix is : ");
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                System.out.print(res[i][j]+" ");
            }
        System.out.println("");
        }
 
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                max = Math.max(max, res[i][j]);
            }
        }
        System.out.println("max square : "+max);
    }
}

Largest Rectangle in Histogram

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

Solution: run time complexity is O(n), space complexity is O(n).

"维护一个栈，这个栈从低向上的高度是依次递增的，如果遇到当前bar高度比栈顶元素低，那么就出栈直到满足条件，过程中检测前面满足条件的矩阵。关键问题就在于在出栈时如何确定当前出栈元素的所对应的高度的最大范围是多少。答案跟Longest Valid Parentheses中括号的范围相似，就是如果栈已经为空，说明到目前为止所有元素（当前下标元素除外）都比出栈元素高度要大（否则栈中肯定还有元素），所以矩阵面积就是高度乘以当前下标i。如果栈不为空，那么就是从当前栈顶元素的下一个到当前下标的元素之前都比出栈元素高度大（因为栈顶元素第一个比当前出栈元素小的)。"

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

public class Solution {
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        
        int max = 0;
        Stack stack = new Stack();   //存index
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
                int index = stack.pop();
                int curArea = stack.isEmpty() ? height[index] * i : height[index] * (i - stack.peek() - 1);
                max = Math.max(max, curArea);
            }
            stack.push(i);
        }
        
        while (!stack.isEmpty()) {
            int index = stack.pop();
            int curArea = stack.isEmpty() ? height[index] * height.length : height[index] * (height.length - stack.peek() - 1);
            max = Math.max(max, curArea);
        }
        
        return max;
    }
}

Or:

public class Solution {
    public int largestRectangleArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        
        int[] newArray = new int[height.length + 1];
        for (int i = 0; i < height.length; i++) {
            newArray[i] = height[i];
        }
        newArray[height.length] = 0;
        
        int max = 0;
        Stack stack = new Stack();   //存index
        for (int i = 0; i < newArray.length; i++) {
            while (!stack.isEmpty() && newArray[i] <= newArray[stack.peek()]) {
                int index = stack.pop();
                int curArea = stack.isEmpty() ? newArray[index] * i : newArray[index] * (i - stack.peek() - 1);
                max = Math.max(max, curArea);
            }
            stack.push(i);
        }
        
        return max;
    }
}

Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

Solution1(leetcode上最后一个testcase没过): 如果矩阵只有一行或者一列，那么无需转圈，依次输出即可。其他情况均需转圈：从左到右，从上到下，从右到左，从下到上。如果奇数行，中心点要单独加。

public class Solution {
    public ArrayList spiralOrder(int[][] matrix) {
        ArrayList result = new ArrayList();

        if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return result;
        
        int m = matrix.length;
        int n = matrix[0].length;
        
        int top = 0, bottom = m - 1;
        int left = 0, right = n - 1;
        while(top <= bottom && left <= right) {
            if(m == 1) {
                for(int i = 0; i < n; i++) {
                    result.add(matrix[0][i]);
                }
                break;
            }else if(n == 1) {
                for(int i = 0; i < m; i++) {
                    result.add(matrix[i][0]);
                }
                break;
            }
        
            for(int i = left; i < right; i++) {
                result.add(matrix[top][i]);
            }
            for(int i = top; i < bottom; i++) {
                result.add(matrix[i][right]);
            }
            for(int i = right; i > left; i--) {
                result.add(matrix[bottom][i]);
            }
            for(int i = bottom; i > top; i--) {
                result.add(matrix[i][left]);
            }
            top++;
            bottom--;
            left++;
            right--;
        }
        
        if(n % 2 != 0 && m == n && m > 1)
            result.add(matrix[n/2][n/2]);

        return result;
    }
}

Solution2: 
类似于rotate image的做法。Run time complexity is O(m * n), space complexity is O(n), 储存结果占用的空间.

public class Solution {
    public List spiralOrder(int[][] matrix) {
        List res = new ArrayList();
        if (matrix == null || matrix.length == 0) {
            return res;
        }
        
        int min = Math.min(matrix.length, matrix[0].length);
        int level = min / 2;
        for (int i = 0; i < level; i++) {
            for (int j = i; j < matrix[0].length - i - 1; j++) {
                res.add(matrix[i][j]);
            }
            
            for (int j = i; j < matrix.length - i - 1; j++) {
                res.add(matrix[j][matrix[0].length - i - 1]);
            }
            
            for (int j = matrix[0].length - i - 1; j > i; j--) {
                res.add(matrix[matrix.length - i - 1][j]);
            }
            
            for (int j = matrix.length - i - 1; j > i; j--) {
                res.add(matrix[j][i]);
            }
        }
        
        if (min % 2 != 0) {
            if (matrix.length < matrix[0].length) {
                for (int i = level; i < matrix[0].length - level; i++) {
                    res.add(matrix[level][i]);
                }
            } else {
                for (int i = level; i < matrix.length - level; i++) {
                    res.add(matrix[i][level]);
                }
            }
        }
        
        return res;
    }
}

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

Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Solution1:

中位数定义：把所有的同类数据按照大小的顺序排列。如果数据的个数是奇数，则中间那个数据就是这群数据的中位数；如果数据的个数是偶数，则中间那2个数据的算术平均值就是这群数据的中位数。

因此，在计算中位数Median时候，需要根据奇偶分类讨论。

解决此题的方法可以依照：寻找一个unioned sorted array中的第k大（从1开始数）的数。因而等价于寻找并判断两个sorted array中第k/2（从1开始数）大的数。

特殊化到求median，那么对于奇数来说，就是求第(m+n)/2 +1（从1开始数）大的数。

而对于偶数来说，就是求第(m+n)/2大（从1开始数）和第(m+n)/2+ 1大（从1开始数）的数的算术平均值。

所以，我们需要判断A[k/2-1]和B[k/2-1]的大小。

如果A[k/2-1]==B[k/2-1]，那么这个数就是两个数组中第k大的数。

如果A[k/2-1]<B[k/2-1], 那么说明A[0]到A[k/2-1]都不可能是第k大的数，所以需要舍弃这一半，继续从A[k/2]到A[A.length-1]继续找。当然，因为这里舍弃了A[0]到A[k/2-1]这k/2个数，那么第k大也就变成了，第k-k/2个大的数了。

如果 A[k/2-1]>B[k/2-1]，就做之前对称的操作就好

eg.

array a:   |       m1      |
array b:   |                          m2            |
M1和M2分别代表两个array的median.
假如M1比M2大， 那么总array的median肯定在 :  
|---------M1
M2 --------|     之间， 那么M1的后面，和M2的前面 都可以扔掉.
假如M1比M2小， 那么总array的median肯定在 :  
M1————|
|————M2     之间， 那么M1的前面，和M2的后面 都可以扔掉.

public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        int m = A.length;
        int n = B.length;
        
        int k = m + n;
        
        if(k % 2 != 0)
            return findK(A, 0, m, B, 0, n, k / 2);
        else
            return (findK(A, 0, m, B, 0, n, k / 2) + findK(A, 0, m, B, 0, n, k / 2 - 1)) / 2;
        
    }
    
    public double findK(int[] A, int astart, int aend, int[] B, int bstart, int bend, int k) {
        
        if(astart == aend)
            return B[bstart + k];
        else if(bstart == bend)
            return A[astart + k];
        
        if(k == 0)
            return Math.min(A[astart], B[bstart]);
        
        int akey = Integer.MAX_VALUE;
        int bkey = Integer.MAX_VALUE;
        int ak = (k + 1) / 2;
        int bk = (k + 1) / 2;
        
        if(astart + ak - 1 < A.length)
            akey = A[astart + ak - 1];
        if(bstart + bk - 1 < B.length)
            bkey = B[bstart + bk - 1];
        
        if(akey < bkey)
            return findK(A, astart + ak, aend, B, bstart, bend, k - ak);
        else
            return findK(A, astart, aend, B, bstart + bk, bend, k - bk);
        
    }
}

Next Permutation

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

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

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

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

Solution:

1. From right to left, find the first digit (PartitionNumber) which violate the increase trend.

2. From right to left, find the first digit which larger than PartitionNumber, call it ChangeNumber.

3. Swap the PartitionNumber and ChangeNumber.

4. Reverse all the digit on the right of partition index.

举例：比如排列是(2,3,6,5,4,1)，求下一个排列的基本步骤是这样：

1) 先从后往前找到第一个不是依次增长的数，记录下位置p。比如例子中的3，对应的位置是1;
2) 接下来分两种情况：
    (1) 如果上面的数字都是依次增长的，那么说明这是最后一个排列，下一个就是第一个，其实把所有数字反转过来即可(比如(6,5,4,3,2,1)下一个是(1,2,3,4,5,6));
    (2) 否则，如果p存在，从p开始往后找，找到下一个数就比p对应的数小的数字，然后两个调换位置，比如例子中的4。调换位置后得到(2,4,6,5,3,1)。最后把p之后的所有数字倒序，比如例子中得到(2,4,1,3,5,6), 这个即是要求的下一个排列。

以上方法中，最坏情况需要扫描数组三次，所以时间复杂度是O(3*n)=O(n)，空间复杂度是O(1)。

public class Solution {
    public void nextPermutation(int[] num) {
        if(num == null || num.length == 0)
            return;
        
        int i = num.length - 2;
        while(i >= 0 && num[i] >= num[i + 1]) {
            i--;
        }
        
        if(i >= 0) {
            int j = i + 1;
            while(j < num.length && num[j] > num[i]) {
                j++;
            }
            j--;
            int temp = num[i];
            num[i] = num[j];
            num[j] = temp;
        }
        reverse(num, i + 1);  //Reverse all the digit on the right of partition index
    }
    
    public void reverse(int[] num, int index) {
        int l = index;
        int r = num.length - 1;
        while(l < r) {
            int temp = num[l];
            num[l] = num[r];
            num[r] = temp;
            l++;
            r--;
        }
    }
}

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Solution: Because it requires O(n) complexity, we can not solve the problem by sorting the array first. Sorting takes at least O(nlogn) time.

We can use a HashSet to add and remove elements. HashSet is implemented by using a hash table. Elements are not ordered. The add, remove and contains methods have constant time complexity O(1).

遇到不能排序又要复杂度O(n)有序的问题，只能增加空间复杂度，用hashset或者hashtable 

public class Solution {
    public int longestConsecutive(int[] num) {
        if(num == null || num.length == 0)
            return 0;
        
        HashSet set = new HashSet();
        int max = 1;

        for(int i = 0; i < num.length; i++) {
            set.add(num[i]);
        }
        
        for(int i = 0; i < num.length; i++) {
            int left = num[i] - 1;
            int right = num[i] + 1;
            int count = 1;
            
            while(set.contains(left)) {  //找比num[i]小1的值
                count++;
                set.remove(left);
                left--;
            }
            while(set.contains(right)) {  //找比num[i]大1的值
                count++;
                set.remove(right);
                right++;
            }
            max = Math.max(max, count);
        }
        
        return max;
    }
}

Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
Solution: 
"假设把矩阵沿着某一行切下来，然后把切的行作为底面，将自底面往上的矩阵看成一个直方图。直方图的中每个项的高度就是从底面行开始往上1的数量。根据Largest Rectangle in Histogram我们就可以求出当前行作为矩阵下边缘的一个最大矩阵。接下来如果对每一行都做一次Largest Rectangle in Histogram，从其中选出最大的矩阵，那么它就是整个矩阵中面积最大的子矩阵。
然而在这里我们会发现一些动态规划的踪迹，如果我们知道上一行直方图的高度，我们只需要看新加进来的行（底面）上对应的列元素是不是0，如果是，则高度是0，否则则是上一行直方图的高度加1。"
Run time complexity is O(m * n), space complexity is O(n).
Reference: http://blog.csdn.net/linhuanmars/article/details/24444491

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        
        int[] height = new int[matrix[0].length];
        int maxArea = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                height[j] = matrix[i][j] == '0' ? 0 : height[j] + 1;
            }
            maxArea = Math.max(maxArea, largestArea(height));
        }
        
        return maxArea;
    }
    
    public int largestArea(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        
        int max = 0;
        Stack stack = new Stack();
        
        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
                int index = stack.pop();
                int curArea = stack.isEmpty() ? height[index] * i : height[index] * (i - stack.peek() - 1);
                max = Math.max(max, curArea);
            }
            stack.push(i);
        }
        
        while (!stack.isEmpty()) {
            int index = stack.pop();
            int curArea = stack.isEmpty() ? height[index] * height.length : height[index] * (height.length - stack.peek() - 1);
            max = Math.max(max, curArea);
        }
        
        return max;
    }
}

Max Points on a Line

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
Solution: HashMap
只要不同点之间的斜率(ratio)相同，说明它们在同一条直线上。Key是ratio，value存点的个数。
每一个点跟它后面的所有点比较，两层循环，maxLocal保存当前点的map中在一条线上的点的最大个数， max保存整体上一条线上点的最大个数。
Run time complexity is O(n ^ 2), space complexity is O(n).

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
        
        int max = 1;
        double ratio = 0.0;
        for (int i = 0; i < points.length - 1; i++) {
            int maxLoc = 1;
            int numOfSam = 0;
            HashMap map = new HashMap();
            
            for (int j = i + 1; j < points.length; j++) {
                if (points[j].x == points[i].x && points[j].y == points[i].y) {  // 两点重合
                    numOfSam++;
                    continue;
                } else if (points[j].x == points[i].x) {  // 两点水平
                    ratio = (double) Integer.MAX_VALUE;
                } else if (points[j].y == points[i].y) {  // 两点垂直
                    ratio = 0.0;
                } else {
                    ratio = (double) (points[j].y - points[i].y) / (double) (points[j].x - points[i].x);
                }
                
                if (map.containsKey(ratio)) {
                    map.put(ratio, map.get(ratio) + 1);
                } else {
                    map.put(ratio, 2);
                }
            }
            
            for (Integer value : map.values()) {
                maxLoc = Math.max(maxLoc, value);
            }
            maxLoc += numOfSam;  // 将重合的点加上
            max = Math.max(max, maxLoc);
        }
        
        return max;
    }
}

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

Pow(x, n)

Implement pow(x, n).
Solution: 
二分法， 用递归来解比较容易理解，把x的n次方划分成两个x的n/2次方相乘，然后递归求解子问题，结束条件是n为0返回1。因为是对n进行二分，算法复杂度是O(logn)。

public class Solution {
    public double pow(double x, int n) {
        if(n == 0)  //terminate condition
            return 1.0;
        
        double half = pow(x, n/2);
        
        if(n%2 == 0)
            return half * half;
        else if(n > 0)
            return half * half * x;
        else
            return half * half / x;
    }
}

Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

Solution: 

用一个queue来保存每一行的node， 把最右边的node.val存入到结果里。

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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List rightSideView(TreeNode root) {
        List res = new ArrayList();
        if (root == null) {
            return res;
        }
        
        LinkedList queue = new LinkedList();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            
            for (int i = 0; i < size; i++) {
                TreeNode top = queue.remove();
                
                if (i == 0) {  // the right-most node of the tree
                    res.add(top.val);
                }
                
                if (top.right != null) {
                    queue.add(top.right);
                }
                
                if (top.left != null) {
                    queue.add(top.left);
                }
            }
        }
        
        return res;
    }
}

Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

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

Solution: recursion
类似于 Combination Sum 和 Combination Sum II

public class Solution {
    public List> combinationSum3(int k, int n) {
        List> res = new ArrayList>();
        List list = new ArrayList();
        if (n == 0) {
            list.add(0);
            res.add(list);
            return res;
        }
        
        helper(res, list, k, n, 1);
        return res;
    }
    
    public void helper(List> res, List list, int k, int n, int start) {
        if (n < 0) {
            return;
        }
        
        if (n == 0 && k == 0) {
            res.add(new ArrayList(list));
            return;
        }
        
        for (int i = start; i <= 9; i++) {
            list.add(i);
            k--;
            helper(res, list, k, n - i, i + 1);
            list.remove(list.size() - 1);
            k++;
        }
    }
}

Peeking Iterator (not finished yet...)

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next().

---

Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.

You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

Hint:

1. Think of "looking ahead". You want to cache the next element.
2. Is one variable sufficient? Why or why not?
3. Test your design with call order of peek() before next() vs next() before peek().
4. For a clean implementation, check out Google's guava library source code.

Follow up: How would you extend your design to be generic and work with all types, not just integer?

Solution: 

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator {
    private Iterator myIterator;
    private Integer next;
    
 public PeekingIterator(Iterator iterator) {
     // initialize any member here.
     myIterator = iterator;
     if (myIterator.hasNext()) {
         next = myIterator.next();
     }
 }

    // Returns the next element in the iteration without advancing the iterator.
 public Integer peek() {
        return next;
 }

 // hasNext() and next() should behave the same as in the Iterator interface.
 // Override them if needed.
 @Override
 public Integer next() {
     Integer res = next;
     next = myIterator.hasNext() ? myIterator.next() : null;
     return res;
 }

 @Override
 public boolean hasNext() {
     return next != null;
 }
}

Follow Up: extend your design to be generic and work with all types, not just integer
Change Integer to generic type <T> ?

Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

Solution: binary search

解决的办法只能是对边缘移动一步，直到边缘和中间不在相等或者相遇，这就导致了会有不能切去一半的可能。所以最坏情况（比如全部都是一个元素，或者只有一个元素不同于其他元素，而他就在最后一个）就会出现每次移动一步，总共是n步，算法的时间复杂度变成O(n)。

public class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return true;
            }
            
            if (nums[mid] > nums[left]) {
                if (target < nums[mid] && target >= nums[left]) {
                    right = mid - 1;
                } else {
                    left = mid;
                } 
            } else if (nums[mid] < nums[left]) {
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            } else {
                left++;  //处理中间和边缘相等情况，移动一步
            }
        }
        
        return false;
    }
}