狂暴复习之路20160611 Greedy I

122	Best Time to Buy and Sell Stock II

参见Array I

330
Patching Array

public int minPatches(int[] nums, int n) {
    int result = 0;
    int index = 0;
    // currSum标记了当前数组nums可累加到的最大范围[1, currSum)    for (double currSum = 1; currSum <= n; )
    {
        // 数组内元素小于currSum时，可累加的sum上限增加为// currSum + nums[index]，然后数组索引值加1        if (index < nums.length && nums[index] <= currSum)
            currSum += nums[index++];
        else        {
            currSum *= 2; // 添入元素后，可累加的sum范围加倍            ++result;
        }
    }
    return result;
}

55
Jump Game

public boolean canJump(int[] nums) {
    if (nums == null || nums.length <= 1)
        return true;
int jump = nums[0];

    for (int i = 0; i < nums.length; i++)
    {
        if (jump <= i && nums[i] == 0)
            return false;

        if (i + nums[i] > jump)
        {
            jump = i + nums[i];
        }

        if (jump >= nums.length - 1)
            return true;
    }

    return false;
}
贪出一片天，当jump>=nums.length-1的时候 立即返回true。


134
Gas Station


public int canCompleteCircuit(int[] gas, int[] cost) {
    if (gas==null||gas.length==0)
        return -1;
    int sum = 0;
    int start = -1;
    int cur = 0;
    for (int i = 0; i <gas.length ; i++) {
        sum += gas[i] - cost[i];
        cur += gas[i] - cost[i];
        if (cur<0)
        {
            start = i;
            cur = 0;
        }
    }
    if (sum<0)
        return -1;
    else        return start+1;
}
如果某一个gas走不到，就从下一个开始，因为前面的路都没问题！而且这是一个circle。

45
Jump Game II


public int jump(int[] nums) {
    int result = 0;
    int last = 0;
    int cur = 0;
    for (int i = 0; i <nums.length ; i++)
    {
        if (i>cur)
            return -1;
        if (i > last)
        {
            last = cur;
            result++;
        }
        cur = Math.max(cur,i+nums[i]);
    }
    return result;
}
贪心，每次都跳当前情况下的最远距离。