代码随想录训练营Day32

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

前言

今天是跟着代码随想录刷题的第32天，主要是学了买卖股票的最佳时机2，跳跃游戏，跳跃游戏2和k次取反后最大化的数组和

一、买卖股票的最佳时机2

思路：这道题思路直接秒，如果下一个比这个高，如果我还没买，就赶紧入手，如果买了就跳过，如果下一个比这个低，如果我还没卖，就赶紧卖，注意这个循环得到最后一个的前一个，最后一个得判断，如果还没卖就赶紧卖，为啥最后一个不用判断高还是低，是因为最后一个既然能处于可以卖的情况，就说明他一定比倒数第二个还要大，这样倒数第二个才不会卖。

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

二、跳跃游戏

思路：从第一个开始，看范围能不能遍历到最后一个，不过需要始终更新最大的范围，如果循环完了还不能跳到最后一个就说明永远不能跳到最后一个了。

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

三、跳跃游戏2

思路：跳下一个的时候，检查这一个的范围哪一个下一个跳的最远，就选这个跳的最远的去跳就可以了，注意start要放到循环外面去改。不然会影响循环的参数。

class Solution {
public:
    int i=0;
    int path=0;
    int start=0;
    int cover=0;
    int next=0;
    int jump(vector<int>& nums) {
    if(nums.size()==1) return 0;
    cover=nums[0];
    while(nums[start]+start<nums.size()-1)
    {   
        path++;
        cover=0;
        for(i=start+1;i<=start+nums[start];i++)
        {
            
            if(i<=nums.size()-1&&nums[i]+i>cover)
            {
                cover=nums[i]+i;
                next=i;
            }
               
        }
        start=next;   
    }
    path++;
    return path;

    }
};

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

思路：就是让最小的负数先取反，如果取完了，再让小的正数取反，再求和
代码：

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
    sort(nums.begin(),nums.end());
    int fu=0,feifu=0,result=0;
    int i;
    for(i=0;i<nums.size();i++)
    {
        if(nums[i]<0) fu++;
    }
    if(k<=fu)
    {
        for(i=0;i<nums.size();i++)
        {
            if(i<k)
            {
                result=result-nums[i];
            }
            else result=result+nums[i];   
        }
    }
    if(k>fu)
    {
        for(i=0;i<nums.size();i++)
        {
            if(i<fu)
            {
                nums[i]=-nums[i];
            }
        }
        sort(nums.begin(),nums.end());
        if((k-fu)%2==1)
        {
            nums[0]=-nums[0];    
        }
        for(i=0;i<nums.size();i++)
        {
            result=result+nums[i];
        }
    }
    return result;
    }
};