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