贪心算法day28|买卖股票的最佳时机、55. 跳跃游戏、1005. K 次取反后最大化的数组和

贪心算法day28|买卖股票的最佳时机、55. 跳跃游戏、1005. K 次取反后最大化的数组和

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

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

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。

提示：

• 1 <= prices.length <= 3 * 104
• 0 <= prices[i] <= 104

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sum=0;
        for(int i=0;i<prices.size()-1;i++)
        {
            if(prices[i+1]>prices[i])
            sum+=prices[i+1]-prices[i];
            else
            continue;
        }
        return sum;
    }
};

本题还是比较简单的，核心逻辑：先画出摆动图，当上坡时在峰值卖出，下坡时按兵不动。在代码上体现的比较巧妙，属于是透过现象看本质了。

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover=0;
        if(nums.size()==1)
        return true;
        for(int i=0;i<=cover;i++)
        {
            if(i+nums[i]>cover)
            cover=i+nums[i];
            if(cover>=nums.size()-1)
            return true;
        }
        return false;
    }
};

本体思路非常巧妙，也很难想到。

总体思路：将问题转化为覆盖范围，即当覆盖范围大于等于最后一个元素时，就OK了。在此期间，要cover范围内不断遍历，在遍历过程中不断地更新cover，直到到达最后一个元素。

易错点：

• 当元素个数为1时，需要另写，即：

  if(nums.size()==1)
      return true;

否则[0]就无法通过。

  if(cover>=nums.size()-1)

cover本质上还是下标的范围，所以最后比较的是nums.size()-1，而不是nums.size()。

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

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

• 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

示例 1：

输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。

示例 2：

输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。

示例 3：

输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。

提示：

• 1 <= nums.length <= 104
• -100 <= nums[i] <= 100
• 1 <= k <= 104

class Solution {
public:
    static bool cmp(int a,int b)
    {
        return abs(a)>abs(b);
    }
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end(),cmp);
        for(int i=0;i<nums.size();i++)
        {
            if(k>0&&nums[i]<0)
            {
                nums[i]=-nums[i];
                k--;
            }
        }
        if(k%2==1)
        nums[nums.size()-1]*=-1;
        int sum=0;
        for(int i=0;i<nums.size();i++)
        {
            sum+=nums[i];
        }
        return sum;
    }
};

核心逻辑：当负数全部取反之后，该取哪个正数呢？答：取最小的正数，这包括原本是负数，而现在转变成的正数。 ==>用绝对值排序

难点：

• 将元素按绝对值大小排序，需要另写cmp，格式如下：

sort(nums.begin(),nums.end(),cmp);
  static bool cmp(int a,int b)
      {
          return abs(a)>abs(b);
      }

• 当所有负数都取反之后k仍然>0时，我们要处理此时绝对值最小的数即nums[nums.size()-1]。一种非常巧妙的思维：

if(k%2==1)
  nums[nums.size()-1]*=-1;

当k为奇数时，在本质上就取反一次；k为偶数时，本质上不变。这样就省去了while循环，大大提高效率。