[LeetCode] Search in Rotated Sorted Array

Thought:
Binary Search with different condition.

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

[LeetCode] Pow(x,n)

Thought:
Divide and Conquer.

Code:
public class Solution {
    public double pow(double x, int n) {
        boolean isNeg = false;
        if (n < 0) {
            n = - n;
            isNeg = true;
        }
        return isNeg ? 1 / helper(x, n): helper(x, n);       
    }
    public double helper(double x, int n) {      
       
        if (n == 0) return 1;       
        double result = pow(x, n / 2);
       
        if (n % 2 == 0) return result * result;
        return result * result * x;
    }
   
}

[LeetCode] Merge k Sorted Lists

Thought:
Basically, we could merge every list into the first, the complexity will be nl1 + (n-1)l2 + ... + 1*ln;
To be faster, we could merge the first and the last, recursively. The complexity will be lgn*(l1 + l2 + ... + ln).
Using randomization, we could cancel out the difference between l1 - ln.
So the first method will result in the time O(n^2), while the second one is O(nlgn).

Code 1:
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists.size() == 0) return null;
        for (int i = 1; i < lists.size(); i++) {
            lists.set(0, mergeTwoLists(lists.get(0), lists.get(i)));
        }
        return lists.get(0);
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }else {           
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }    
    }
}

Code 2:
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        int len = lists.size();
        if (len == 0) return null;
        int start = 0;
        int end = len - 1;
        while (len > 1) {
            lists.set(start, mergeTwoLists(lists.get(start), lists.get(end)));
            start++;
            end--;
            if (start >= end) {
                len = (len + 1) / 2;
                start = 0;
                end = len - 1;
            }
        }
        return lists.get(start);
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }else {           
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }    
    }
}

[LeetCode] Maximum Subarray

Thought:
Divide and Conquer.

Code:
public class Solution {
    public int maxSubArray(int[] A) {
        return max(A, 0, A.length - 1);
    }
    public int max(int[] A, int start, int end) {
        if (start > end) return Integer.MIN_VALUE;
        int mid = (start + end) / 2;
        int max1 = max(A, start, mid - 1);
        int max2 = max(A, mid + 1, end);
        int tmp = 0, max31 = 0, max32 = 0;
        for (int i = mid - 1; i >= start; i--) {
            tmp = tmp + A[i];
            max31 = Math.max(max31, tmp);
        }
        tmp = 0;
        for (int j = mid + 1; j <= end; j++) {
            tmp = tmp + A[j];
            max32 = Math.max(max32, tmp);
        }
        int max3 = max31 + max32 + A[mid];
        return Math.max(max1, Math.max(max2, max3));
    }
}

[LeetCode] Median of Two Sorted Arrays

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

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