分治 & 树状数组 2016-7-21

[dayang]

4 --- median-of-two-sorted-arrays 45 --- Jump Game II 315 ---Count of Smaller Numbers After Self

[SnackMen]

参考：http://blog.csdn.net/zxzxy1988/article/details/8587244
/*
[AC] 4 --- median-of-two-sorted-arrays
*/
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
          int len1 = nums1.length;
          int len2 = nums2.length;
          if((len1+len2)%2==0){
              return (findMedia(nums1,len1,0,nums2,len2,0,(len1+len2)/2)+findMedia(nums1,len1,0,nums2,len2,0,(len1+len2)/2+1))/2;
          }else{
              return findMedia(nums1,len1,0,nums2,len2,0,(len1+len2)/2+1);
          }
    }
    public double findMedia(int nums1[],int len1,int start1,int nums2[],int len2,int start2,int media){
        if(len1>len2)
            return findMedia(nums2,len2,start2,nums1,len1,start1,media);
        if(len1==0)
            return nums2[start2+media-1];
        if(media==1)
            return Math.min(nums1[start1],nums2[start2]);
        int n1=Math.min(media/2,len1);
        int n2=media-n1;
        if(nums1[start1+n1-1]>nums2[start2+n2-1])
            return findMedia(nums1,len1,start1,nums2,len2-n2,start2+n2,media-n2);
        else if(nums2[start2+n2-1]>nums1[start1+n1-1])
            return findMedia(nums1,len1-n1,start1+n1,nums2,len2,start2,media-n1);
        else
            return nums1[n1-1];
    }
}

/*
自己尝试用库函数写，然而并没有O(log(m+n))
[AC] 4 --- median-of-two-sorted-arrays
*/
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
           int len1=nums1.length;
           int len2=nums2.length;
           int nums3[] = new int[len1+len2];
           System.arraycopy(nums1,0,nums3,0,len1);
           System.arraycopy(nums2,0,nums3,len1,len2);
           Arrays.sort(nums3);
           if((len1+len2)%2==0){
               return ((double)nums3[(len1+len2)/2]+(double)nums3[(len1+len2)/2-1])/2;
           }else{
               return nums3[(len1+len2)/2];
           }
    }
}   

[SnackMen]

/*
[AC] 45 --- Jump Game II
*/
public class Solution {
    public int jump(int[] nums) {
        int max=0;
        int count=0;
        int next=0;
        if(nums.length==1){
            count=0;
        }else{
            for(int i=0;i<nums.length-1;++i){
                next=Math.max(next,i+nums[i]);
                if(i==max){
                    max=next;
                    count++;
                }
            }
        }

        return count;
    }
}

[dayang]

/**
 * [AC] LeetCode 45 Jump Game II
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    if(nums.length === 1)
        return 0;
    var res = 1,maxPos = nums[0],nextMax = 0;
    for(var i = 1; i < nums.length; i++){
        if(maxPos >= nums.length - 1)
            break;
        for(; i<= maxPos; i++){
            if(nextMax < i + nums[i])
                nextMax = i + nums[i];
        }
        i--;
        if(nextMax > maxPos){
            res ++;
            maxPos = nextMax;
        }
    }

    return res;
};

[zhaokuohaha]

4 - C

public class Solution
{
    int[] _nums1;
    int[] _nums2;
    private double findKth(int start1,int  start2, int k)
    {
        if(start1 > _nums1.Length-1) return _nums2[start2+k-1];
        if(start2 > _nums2.Length-1) return _nums1[start1+k-1];
        if(k == 1) return Math.Min(_nums1[start1],_nums2[start2]);

        int s1 = start1+k/2;
        int s2 = start2+k/2;
        if(s2 > _nums2.Length)
            return findKth(s1, start2, k-k/2);
        if(s1 > _nums1.Length)
            return findKth(start1, s2, k-k/2);

        if(_nums1[s1-1] < _nums2[s2-1])
            return findKth(s1, start2, k-k/2);
        else
            return findKth(start1, s2, k-k/2);
    }
    public double FindMedianSortedArrays(int[] nums1, int[] nums2)
    {
        _nums1 = nums1;
        _nums2 = nums2;
        int total = nums1.Length + nums2.Length;
        if(total%2==0)
            return (findKth(0,0,(total+1)/2) + findKth(0,0,total/2+1)) / 2.0;
        return findKth(0,0,total/2+1);
    }
}

[zhaokuohaha]

45 - C# - 根据王舒的思路来做

每决定走一格则记录在这个格所能走的范围内(max)的下一步所能达到的最大距离(next), 等走完这个范围之后重新更新max, 步数count++

public class Solution {
    public int Jump(int[] nums) {
        if(nums.Length <= 1) return 0;
        int count=0;
        int max = 0;
        int next = 0;
        for(int i=0; i<nums.Length-1; i++){
            next = Math.Max(next,i+nums[i]);
            if(max == i){
                max  = next;
                count ++;
            }
        }
        return count;
    }
}

[zhaokuohaha]

315 - 谁能告诉我这份神奇的代码是什么意思

public class Solution
{
    public IList<int> CountSmaller(int[] nums)
    {
        int[] lintResult = new int[nums.Length];
        List<int> llistSorted = new List<int>();

        for (int i = nums.Length - 1; i >= 0; --i)
        {
            int lintPos = llistSorted.BinarySearch(nums[i]);
            if (lintPos >= 0)
            {
                while (lintPos > 0 && llistSorted[lintPos] == llistSorted[lintPos - 1])
                {
                    lintPos--;
                }
                lintResult[i] = lintPos;
            }
            else
            {
                lintPos = ~lintPos;
                lintResult[i] = lintPos;
            }
            llistSorted.Insert(lintPos, nums[i]);
        }
        return lintResult.ToList<int>();
    }
}