【代码随想录_Day23】122. 买卖股票的最佳时机 II 55. 跳跃游戏 45.跳跃游戏II 1005.K次取反后最大化的数组和

Day23 OK，今日份的打卡！第二十三天

以下是今日份的总结
- 买卖股票的最佳时机 II
- 跳跃游戏
- 跳跃游戏II
- K次取反后最大化的数组和

以下是今日份的总结

122 买卖股票的最佳时机 II
55 跳跃游戏
45 跳跃游戏II
1005 K次取反后最大化的数组和

今天的题目难度不低，尽量还是写一些简洁代码 ^ _ ^

买卖股票的最佳时机 II

思路：

算出每一天的差值，然后计算所有正值的和，不计算亏损

值得注意的是

局部最优：收集每天的正利润
全局最优：求得最大利润。

    int maxProfit(vector<int>& prices) {
        int res = 0;
        for (int i = 1; i < prices.size(); i++) {
            res += max(prices[i] - prices[i - 1],0);
        }
        return res;
    }

跳跃游戏

思路：

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

值得注意的是

因为元素值是最大跳跃步数，所以可以在范围内跳任意步数

       bool canJump(vector<int>& nums) {
        int cover = 0;
        if (nums.size() == 1)
            return true; // 只有一个元素，就是能达到
        for (int i = 0; i <= cover; i++) { // 注意这里是小于等于cover
            cover = max(i + nums[i], cover);
            if (cover >= nums.size() - 1)
                return true; // 说明可以覆盖到终点了
        }
        return false;
    }

跳跃游戏II

思路：

从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数

值得注意的是

需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖

    int jump(vector<int>& nums) {
        int curDistance = 0;  // 当前覆盖的最远距离下标
        int ans = 0;          // 记录走的最大步数
        int nextDistance = 0; // 下一步覆盖的最远距离下标
        for (int i = 0; i < nums.size() - 1;
             i++) { // 注意这里是小于nums.size() - 1，这是关键所在
            nextDistance =
                max(nums[i] + i, nextDistance); // 更新下一步覆盖的最远距离下标
            if (i == curDistance) { // 遇到当前覆盖的最远距离下标
                curDistance = nextDistance; // 更新当前覆盖的最远距离下标
                ans++;
                if (nextDistance >= nums.size() - 1)
                    break; // 当前覆盖最远距到达集合终点，不用做ans++操作了，直接结束
            }
        }
        return ans;
    }

K次取反后最大化的数组和

思路：

第一步：将数组按照绝对值大小从小到大排序，注意要按照绝对值的大小
第二步：从前向后遍历，遇到负数将其变为正数，同时K–
第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
第四步：求和

值得注意的是

贪心第一次
局部最优：让绝对值大的负数变为正数，当前数值达到最大
整体最优：整个数组和达到最大。
再贪一次
局部最优：只找数值最小的正整数进行反转，当前数值和可以达到最大
全局最优：整个数组和达到最大。

    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int res = 0;
        //排序，假设将最小的负数放在数组最前面
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
        	//尽可能的处理数组中的负数
            if (nums[i] < 0 && k > 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        //全是正数，在此调整排序，k有余是单数，则将开头的数字负数化        
        if (k % 2 != 0) {
        	sort(nums.begin(), nums.end());
            nums[0] = -nums[0];
        }
        for (int i : nums) {
            res += i;
        }
        return res;
    }

两次排序太罗嗦了，优化一下

   static bool cmp(int a, int b) { return abs(a) < abs(b); }
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int res = 0;
        //按绝对值排序，解决两次排序的问题
        sort(nums.begin(), nums.end(), cmp);
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (nums[i] < 0 && k > 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        if (k % 2 == 1) {
            nums[0] = -nums[0];//最小值取负
        }
        for (int i : nums) {
            res += i;
        }
        return res;
    }