代码随想录算法训练营第51期第28天 | 122. 买卖股票的最佳时机 II、55. 跳跃游戏、45. 跳跃游戏 II、1005.K次取反后最大化的数组和

122. 买卖股票的最佳时机 II

122. 买卖股票的最佳时机 IIhttps://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/1.我刚刚看了一下之前用C++写题的时候，自己说了句【我好像记得这道题是怎么写的，也不知道是福是祸】会心一笑，好像不是坏事，过了这么久了，我还是记得，说明我会呀

2.很简单哈，就是搜集区间为正数的每日收入，加起来就行了，有一说一，这个是不是画个坐标系，然后统计每个上升区间的差值就可以了

int maxProfit(int* prices, int pricesSize) {
    int res = 0;
    for (int i = 1; i < pricesSize; i++) {
        // int money = *(prices + i) - *(prices + i - 1);
        int money = prices[i] - prices[i-1];
        if (money > 0) {
            res += money;
        }
    }
    return res;
}

55. 跳跃游戏

55. 跳跃游戏https://leetcode.cn/problems/jump-game/1.有点尴尬，看之前的blog的时候，不小心看到范围两个字，好吧，我知道怎么写了

2.这题的关键在于覆盖范围，当覆盖范围达到数组长度的时候，就是返回true的时候了，一旦没有达到覆盖范围，则return false

3.我把卡哥的代码也放进来，我觉得更简洁一些

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

bool canJump(int* nums, int numsSize) {
    int range = *nums;
    int tmp = 0;
    for (int i = 1; i < numsSize; i++) {
        if (i <= range) {
            tmp = nums[i] + i;
            if (tmp > range) {
                range = tmp;
                if (range > numsSize -1){
                    return true;
                }
            }
        }else{
            return false;
        }
    }
    return true;
}

#define max(a, b) (((a) > (b)) ? (a) : (b))

bool canJump(int* nums, int numsSize){
    int cover = 0;

    int i;
    // 只可能获取cover范围中的步数，所以i<=cover
    for(i = 0; i <= cover; ++i) {
        // 更新cover为从i出发能到达的最大值/cover的值中较大值
        cover = max(i + nums[i], cover);

        // 若更新后cover可以到达最后的元素，返回true
        if(cover >= numsSize - 1)
            return true;
    }

    return false;
}

45. 跳跃游戏 II

1.打眼一看，这道题应该用动态规划会更好做一点，但是tm的我现在记不得动态规划的写法了；

2.参考文心一言的写法，懂的很舒服

3.看了一言的写法，dp也可以，无非是没有贪心高效罢了

int jump(int* nums, int numsSize) {
    int jumps = 0;  // 跳跃次数
    int currentEnd = 0;  // 当前跳跃范围的结束位置
    int farthest = 0;  // 在当前跳跃范围内能够到达的最远点

    for (int i = 0; i < numsSize - 1; i++) {  // 遍历到倒数第二个元素
        farthest = (farthest > i + nums[i]) ? farthest : i + nums[i];  // 更新最远点
        if (i == currentEnd) {  // 到达当前跳跃范围的边界
            jumps++;  // 进行一次新的跳跃
            currentEnd = farthest;  // 更新跳跃范围的结束位置为当前能够到达的最远点
            if (currentEnd >= numsSize - 1) {  // 如果已经能够跳到最后一个元素或更远
                break;  // 提前终止循环
            }
        }
    }

    return jumps;
}

int cmp(const void* a, const void* b) {
    int inta = *(int *)a;
    int intb = *(int *)b;
    return inta - intb;
}
int largestSumAfterKNegations(int* nums, int numsSize, int k) {
    qsort(nums, numsSize, sizeof(int), cmp);
    int res = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] < 0 && k > 0){
            nums[i] = -nums[i];
            k--;
        }
        res += nums[i];
    }
    qsort(nums, numsSize, sizeof(int), cmp);
    if (k % 2 == 1) {
        res = res - nums[0] * 2;
    }
    return res;
}