[LintCode] #53 Reverse Words in a String

* reverse each word, and then reverse the entire string
sky_is_blue => yks_si_eulb => blue_is_sky

public class Solution {
    /**
     * @param s : A string
     * @return : A string
     */
    public String reverseWords(String s) {
       if (s == null || s.length() == 0) {
           return s;
       }
       
       String[] A = s.split(" ");
       if (A.length == 0 ) {
           return "";
       }
       
       StringBuilder sb = new StringBuilder();
       for (int i = A.length - 1; i >= 0; i--) {
           sb.append(A[i]);
           if (i != 0) {
               sb.append(" ");
           }
       }
       
       return new String(sb);
    }
}

* This one not working, because of it can't remove redundant spaces

public class Solution {
    public String reverseWords(String s) {
       char[] tmp = s.toCharArray();
       int start = 0;
       while(start < tmp.length) {
           while (start < tmp.length && tmp[start] == ' ') {
               start++;
           }
           if (start >= tmp.length) {
               break;
           }
           
           int end = start;
           while (end < tmp.length && tmp[end] != ' ') {
               end++;
           }
           if (start < tmp.length && end <= tmp.length) {
               reverse(start, end - 1, tmp);
           }
           
           start = end;
       }
       reverse(0, tmp.length - 1, tmp);
       return new String(tmp);
    }
    
    private void reverse(int start, int end, char[] A) {
        while (start < end) {
            char tmp = A[start];
            A[start] = A[end];
            A[end] = tmp;
            
            start++;
            end--;
        }
    }
}

[LintCode] #8 Rotate String

1) when offset > str.length!!!!!

public class Solution {
    /**
     * @param str: an array of char
     * @param offset: an integer
     * @return: nothing
     */
    public void rotateString(char[] str, int offset) {
        // write your code here
        if (str == null || str.length == 0 || offset < 0) {
            return;
        }
        offset = offset % str.length; //T_T!!!!!!!
        reverse(str, 0, str.length - offset - 1);
        reverse(str, str.length - offset, str.length - 1);
        reverse(str, 0, str.length - 1);
    }
    
    private void reverse(char[] str, int start, int end) {
        while (start < end) {
            char tmp = str[start];
            str[start] = str[end];
            str[end] = tmp;
            
            start++;
            end--;
        }
    }
}

[LintCode] #159 Find Minimum in Rotated Sorted Array

1) [mid] > [start] move right, else move left
2) edge case: the array is sorted

public class Solution {
    /**
     * @param num: a rotated sorted array
     * @return: the minimum number in the array
     */
    public int findMin(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return -1;
        }
        if (nums[0] < nums[nums.length - 1]) { //T_T!!!!!
            return nums[0];
        }
        int start = 0;
        int end = nums.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[0] < nums[mid]) {
                start = mid;
            } else {
                end = mid;
            }
        }
        
        if (nums[start] < nums[end]) {
            return nums[start];
        } else {
            return nums[end];
        }
    }
}

[LintCode] #39 Recover Rotated Sorted Array

1) in place == re-sort O(nlogn)
2) O(n) space, O(n) time
3) 3 time reverse, O(1) space, O(n) time

public class Solution {
    /**
     * @param nums: The rotated sorted array
     * @return: The recovered sorted array
     */
    public void recoverRotatedSortedArray(ArrayList<Integer> nums) {
        // write your code
        int i;
        for (i = 1; i < nums.size(); i++) {
            if (nums.get(i) < nums.get(i - 1)) {
                break;
            }
        }
        
        reverse(nums, 0, i - 1);
        reverse(nums, i, nums.size() - 1);
        reverse(nums, 0, nums.size() - 1);
    }
    
    private void reverse(ArrayList<Integer> nums, int start, int end) {
        for (; start < end; start++, end--) {
            int tmp = nums.get(start);
            nums.set(start, nums.get(end));
            nums.set(end, tmp);
        }
    }
}

[LeetCode] #4 Median of Two Sorted Arrays

1) Merge + find median O(m + n)
2) Find kth largest element in two arrays O(logk), k = (m + n)/2, because every time throw away k/2^n

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) {
            return 0.0;
        }
        if ((nums1.length + nums2.length) % 2 != 0) {
            return findKthElem(nums1, nums2, 0, 0, (nums1.length + nums2.length) / 2 + 1);
        } else {
            return (findKthElem(nums1, nums2, 0, 0, (nums1.length + nums2.length) / 2) + findKthElem(nums1, nums2, 0, 0, (nums1.length + nums2.length) / 2 + 1)) / 2.0;
        }
    }
    
    private int findKthElem(int[] nums1, int[] nums2, int start1, int start2, int k) {
        if (start1 >= nums1.length) {
            return nums2[start2 + k - 1];
        }
        if (start2 >= nums2.length) {
            return nums1[start1 + k - 1];
        }
        
        if (k == 1) {
            return nums1[start1] > nums2[start2] ? nums2[start2] : nums1[start1];
        } 
        
        int value1 = start1 + k/2 - 1 < nums1.length ? nums1[start1 + k/2 - 1] : Integer.MAX_VALUE; // use max value here to throw away first k/2 elems in nums2 
        int value2 = start2 + k/2 - 1 < nums2.length ? nums2[start2 + k/2 - 1] : Integer.MAX_VALUE;
        if (value1 > value2) {
            return findKthElem(nums1, nums2, start1, start2 + k/2, k - k/2); // the rest elems to find
        } else {
            return findKthElem(nums1, nums2, start1 + k/2, start2, k - k/2);
        }
    }
}

[LintCode] #61 Search for a Range

public class Solution {
    /** 
     *@param A : an integer sorted array
     *@param target :  an integer to be inserted
     *return : a list of length 2, [index1, index2]
     */
    public int[] searchRange(int[] A, int target) {
        // write your code here
        int[] result = new int[2];
        result[0] = -1;
        result[1] = -1;
        if (A == null || A.length == 0) {
            return result;
        }
        
        int start = 0;
        int end = A.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] >= target) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (A[start] == target) {
            result[0] = start;
        } else if (A[end] == target){
            result[0] = end;
        } else {
            return result; //!!!!!
        }
        
        
        start = 0;
        end = A.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] <= target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (A[end] == target) {
            result[1] = end;
        } else if (A[start] == target) {
            result[1] = start;
        } else {
            result[0] = -1;
        }
        
        return result;
    }
}

[LintCode] #183 Wood Cut

public class Solution {
    /** 
     *@param L: Given n pieces of wood with length L[i]
     *@param k: An integer
     *return: The maximum length of the small pieces.
     */
    public int woodCut(int[] L, int k) {
        // write your code here
        if (L == null || L.length == 0) {
            return 0;
        }
        
        int max = 0;
        for (int i = 0; i < L.length; i++) {
            max = max < L[i] ? L[i] : max;
        }
        
        int start = 0;
        int end = max;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (numberOfPieces(L, mid) < k) {
                end = mid;
            } else {
                start = mid;
            }
        }
        
        if (numberOfPieces(L, end) >= k) {
            return end;
        } else {
            return start;
        }
    }
    
    private int numberOfPieces(int[] L, int length) {
        int pieces = 0;
        for (int i = 0; i < L.length; i++) {
            pieces += L[i] / length;
        }
        return pieces;
    }
}