自学内容网 自学内容网

【代码随想录_Day23】122. 买卖股票的最佳时机 II 55. 跳跃游戏 45.跳跃游戏II 1005.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;
    }

写在最后

----OK,今日份的博客就写到这里,这一期的贪心算法好难想,明天继续加油!!!
—还没看下期的题,但是我的栈还有一节没写;
–追上时间进度了吗?如追,从欠两天变成欠一天!!(笑
-月亮在走,太阳在跑,时间在睡觉,机会不会等我。


原文地址:https://blog.csdn.net/qq_43671872/article/details/140151443

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!