[LeetCode] Count of Range Sum

参考：https://leetcode.com/discuss/79083/share-my-solution
照着人家的写了一个，原文解释的很详细了，稍微改了改。

public class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        if (nums == null || nums.length == 0) return 0;
        long[] prefixSum = new long[nums.length];
        prefixSum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) prefixSum[i] = prefixSum[i-1] + nums[i];
        return mergeCount(prefixSum, 0, nums.length - 1, lower, upper);
    }

    private int mergeCount(long[] prefixSum, int start, int end, int lower, int upper) {
        if (start == end) {
            if (prefixSum[start] >= lower && prefixSum[start] <= upper) return 1;
            else return 0;
        }
        int mid = (start + end) / 2;
        int count = mergeCount(prefixSum, start, mid, lower, upper);
        count += mergeCount(prefixSum, mid + 1, end, lower, upper);
        long[] left = new long[mid - start + 1];
        long[] right = new long[end - mid];
        for (int i = 0; i < mid - start + 1; i++) left[i] = prefixSum[start + i];
        for (int i = 0; i < end - mid; i++) right[i] = prefixSum[mid + 1 + i];
        for (int leftIndex = 0, lowerBound = 0, upperBound = 0, rightIndex = 0, index = start; leftIndex < mid - start + 1; leftIndex++) {
            while (lowerBound < end - mid && right[lowerBound] - left[leftIndex] < lower) lowerBound++;
            while (upperBound < end - mid && right[upperBound] - left[leftIndex] <= upper) upperBound++;
            count += upperBound - lowerBound;
            while (rightIndex < end - mid && right[rightIndex] < left[leftIndex]) prefixSum[index++] = right[rightIndex++];
            prefixSum[index++] = left[leftIndex];
        }
        return count;
    }
}

[LeetCode] Count of Smaller Numbers After Self

参考：https://leetcode.com/discuss/73256/mergesort-solution

就是用merge sort，写完了看了这个才发觉自己二了，不需要用HashMap来存“比某个index的数小的数”的个数，用数组够了。

public class Solution {

    public List<Integer> countSmaller(int[] nums) {

        List<Integer> countOfSmallerNumbers = new ArrayList<Integer>();

        if (nums == null || nums.length == 0) return countOfSmallerNumbers;

        int[] indexTrack = new int[nums.length];
        HashMap<Integer, Integer> smallerNumberTrack = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            indexTrack[i] = i;
            smallerNumberTrack.put(i, 0);
        }
       
        mergeSort(nums, indexTrack, 0, nums.length - 1, smallerNumberTrack);
      
        for (int i = 0; i < nums.length; i++) {
            countOfSmallerNumbers.add(smallerNumberTrack.get(i));
        }
       
        return countOfSmallerNumbers;
    }   

    private void mergeSort(int[] nums, int[] indexTrack, int start, int end, HashMap<Integer, Integer> smallerNumberTrack) {
        if (start >= end) return;
        int mid = (start + end) / 2;
        mergeSort(nums, indexTrack, start, mid, smallerNumberTrack);
        mergeSort(nums, indexTrack, mid + 1, end, smallerNumberTrack);

        int[] left = new int[mid - start + 1];
        int[] right = new int[end - mid];
        for (int i = 0; i <= mid - start; i++) left[i] = indexTrack[start + i];
        for (int i = 0; i < end - mid; i++) right[i] = indexTrack[mid + 1 + i];

        int leftIndex = 0, rightIndex = 0, current = start;
        while (current <= end) {
            if (rightIndex >= end - mid || (leftIndex <= mid - start && nums[left[leftIndex]] <= nums[right[rightIndex]])) {
                smallerNumberTrack.put(left[leftIndex], smallerNumberTrack.get(left[leftIndex]) + rightIndex);
                indexTrack[current] = left[leftIndex++];
            }
            else {
                indexTrack[current] = right[rightIndex++];
            }
            current++;
        }
    }
}

[LeetCode] Find Median from Data Stream

思路是使用一个minHeap和maxHeap。不知道有没有更好的方法。

class MedianFinder { 

    private PriorityQueue<Integer> minHeap;
    private PriorityQueue<Integer> maxHeap;

    public MedianFinder() {
        minHeap = new PriorityQueue<Integer>();
        maxHeap = new PriorityQueue<Integer>(500, Collections.reverseOrder());
    }


    // Adds a number into the data structure.
    public void addNum(int num) {
        if (maxHeap.size() == 0 || num <= maxHeap.peek()) {
            maxHeap.add(num);
        }
        else {
            minHeap.add(num);
        }
        if (maxHeap.size() - minHeap.size() >= 2) {
            minHeap.add(maxHeap.poll());
        }
        else if (minHeap.size() > maxHeap.size()) {
            maxHeap.add(minHeap.poll());
        }
    }


    // Returns the median of current data stream
    public double findMedian() {
        double median = 0;
        if (maxHeap.size() != 0) {
            if ((maxHeap.size() + minHeap.size()) % 2 != 0) {
                median = (double) maxHeap.peek();
            }
            else {
                median = (double) (maxHeap.peek() + minHeap.peek()) / 2;
            }
        }
        return median;
    }
};

[LeetCode] Longest Increasing Subsequence

参考：https://leetcode.com/discuss/71129/space-log-time-short-solution-without-additional-memory-java

思路：O(nlogn)
利用maximumLength来记录当前最大的子序列，并且在数组中从0到maximumLength-1存入这个子序列。
我们只关注这个子序列的最大值，也就是nums[maximumLength-1]，当前值和这个值的大小关系决定了目前的最大子序列能否继续扩大。如果能继续扩大，我们可以将当前值加入到这个子序列，否则需要将当前值插入到最大子序列里，为了是用未来可能存在的更大子序列来替换当前子序列。

例如：

[11, 15, 20, 12, 13]

从11开始到20， 我们可以得到当前最大子序列[11, 15, 20], maximumLength = 3，

12的时候，其小于20，当前最大子序列[11, 15, 20]不能扩展，但12可能是未来最大子序列里中的一个元素，我们可以将其和15替换，一方面11和12可以组成一个子序列（虽然不是最大），另一方面替换15对当前最大序列的扩展没有影响，毕竟我们只需要最大长度，而不是最大序列的每一个值。

判断完13的时候0到maximumLength-1的值为[11, 12, 13]，此时[11, 15, 20]和[11, 12, 13]均为最大子序列，但我们只关注结果。

假如给这个数组加一个值21，那么此时其跟13比较而不是20，但无论使用[11, 15, 20]还是[11, 12 ,13]对结果没有影响。假如给这个数组加一个值19，可以看到13使得其扩展。所以最大子序列的末尾越小越好，这也是为什么我们希望将小于当前最大子序列末尾的值插入替换到子序列里。

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int maximumLength = 1;
        for (int i = 1; i < nums.length; i++) {
            int previousIndex = 0;
            if (nums[i] > nums[maximumLength-1]) {
                nums[maximumLength++] = nums[i];
            }
            else if ((previousIndex = Arrays.binarySearch(nums, 0, maximumLength, nums[i])) < 0) {
                nums[-(previousIndex+1)] = nums[i];
            }
        }
        return maximumLength;
    }
}

[LeetCode] Wiggle Sort II

参考：https://leetcode.com/discuss/77133/o-n-o-1-after-median-virtual-indexing

思路：
1）QucikSort 的方法找出中间值，时间O(n)，空间O(1)
2）参见参考链接，类似于给三种颜色排序，将高中低三种值各自规划成一组，由于其中涉及到数组索引的变换，使得实际得到的结果是高低穿插。例如：

数组值：高    高    高    中    中    低
原索引： 0      1      2      3      4      5
变换后： 3      0      4      1      5      2


依据变换索引给高中低值进行规划（顺序为高中低）：

变换后索引值： 0      1      2      3      4      5
数     组     值：高    高     高    中     中    低
原     索     引： 1      3      5      0      2      4

也就是

原     索     引： 0     1      2     3     4      5
数     组     值：中    高    中    高    低    中

这个方法的另一个好处是变换后中间值是相邻的，使得变换前中间值是岔开的，解决了[4, 5 , 5, 6]这种情况

时间O(n)，空间O(1)

代码：

public class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length <= 1) return;
        int median = getMedian(nums);

        int higher = 0, lower = nums.length - 1, current = 0;
        while (current <= lower) {
            if (nums[reIndex(current, nums.length)] == median) {
                current++;
            }

            else if (nums[reIndex(current, nums.length)] < median) {
                swap(nums, reIndex(current, nums.length), reIndex(lower--, nums.length));
            }
            else swap(nums, reIndex(current++, nums.length), reIndex(higher++, nums.length));
        }
    }
   
    private int reIndex(int index, int n) {
        return (2*index + 1) % (n | 1);
    }

    private int getMedian(int[] nums) {
        int start = 0, end = nums.length - 1, target = nums.length / 2;
        while (true) {
            swap(nums, start, (start + end) / 2);
            int swapIndex = start, current = start + 1;
            while (current <= end) {
                if (nums[current] >= nums[start]) swap(nums, ++swapIndex, current);
                current++;
            }
            swap(nums, start, swapIndex);
            if (swapIndex - start == target) return nums[swapIndex];
            else if (swapIndex - start > target) end = swapIndex - 1;
            else {
                target -= (swapIndex - start + 1);
                start = swapIndex + 1;
            }
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}