第二十八天 第八章 贪心算法 part02 122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏II 1005.K次取反后最大化的数组和

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

考虑局部最优，也就是相邻两天股票增，前一天就得买入。

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

55. 跳跃游戏  

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

class Solution {
public:
    bool canJump(vector<int>& nums) {
    int val=0;
    if (nums.size() == 1) return true;
    for(int i=0;i<=val;i++){
        //val表示能跳的最大步数
        val=max(i + nums[i],val);
        //i代表当前已走步数
        if(val>=nums.size()-1) return true;
    }
    return false;
    }
};

45.跳跃游戏II  

当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最少步数。

class Solution {
public:
    int jump(vector<int>& nums) {
    int res=0;
    int near=0;
    int far=0;
    if(nums.size()==1) return 0;
    for(int i=0;i<nums.size();i++){
    far=max(i+nums[i],far);
    if(i==near){
        res++;
        near=far;
        if (far >= nums.size() - 1) break;  
    }
    }
    return res;
    }
};

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

将绝对值从大到小排序，先处理为负数的部分。若取反后k还大于0；将最小数进行取反，也就是对数组的最后一个元素取反。

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