代码随想录训练营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;}
};