代码随想录训练营24day-贪心算法2

一、122 买卖股票最佳时机

题目介绍限制条件，必须卖了再买，而且当前交易一只股票。一开始想法是去遍历，找到每个区间段间的差值，然后再相加。看了解答，其实每一天的利润，都是可以用差值表示出来，每一天的利润最大，那么累加起来，总利润也是最大的。再思考怎么能最大化，只要每天的是正利润，那么就是递增的。

int maxProfit(int* prices, int pricesSize) {
    //可以计算每天的利润
    int result = 0;
    for(int i = 1; i < pricesSize; i++)
    {
        int diff = prices[i] - prices[i - 1];
        //每一天的正利润相加
        if(diff >= 0)
        {
            result += diff;
        }
    }
    return  result;
}

二、55 跳跃游戏

题目意思是从下标index=0（第一个位置），跳跃数组上指定范围内的步数，能不能跳跃到最后一步。

每一步所在的数组值都是一个跳跃范围，代表了在此时，这个点能够达到的最大范围。再跳跃到最大范围的点上，找到此位置上的值，来确认范围是否覆盖。

每一次遍历数组，找到num[i] + i是不是最大值，每一次都更新最大值，判断最大值是不是到达边界。

bool canJump(int* nums, int numsSize) {
    int pos = 0;
    if(numsSize == 1)
    {
        return true;
    }
    //注意这里是<= pos
    for(int i = 0; i <= pos; i++)
    {
        pos = pos > i + nums[i] ? pos : i + nums[i];
        //printf("pos %d i%d  \n", pos, i);
        if(pos >= numsSize -1)
        {
            return true;
        }

    }

    return false;
}

三、45 跳跃游戏II

题目明确是能到达最后一个位置，求最小的步骤。

最少的步骤，就是每一步尽量选择最大的步长，且选择的位置 + 步长能够覆盖到最后一个位置。

 注意：真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数!

遍历整个数组，拿到最远覆盖范围（每一次遍历需要更新），如果i到达上一次的最远范围，把当前最远范围给pre上一次最远范围。移动次数加1，如果当前最远范围已经能覆盖最后一个位置，那么就退出；

int jump(int* nums, int numsSize) {
    int next = 0;
    int cur = 0;
    int result = 0;
    for(int i = 0; i < numsSize; i++)
    {
        next = next > nums[i] + i? next : nums[i] + i;
        if(i == cur)
        {
            result++;
            cur = next;
            if(next >= numsSize - 1)
            {
                break;
            }
        }
    }
    return result;
}