【代码随想录day28】【C++复健】122.买卖股票的最佳时机II ;376. 摆动序列;53. 最大子序和
122.买卖股票的最佳时机II
一周目做dp的时候也遇到过这个题,也知道这个题怎么不用递归做。这种题其实在知道怎么做了以后就会变得很简单,所以做出来也是洒洒水啦。
class Solution {
public:int maxProfit(vector<int>& prices) {int pro = 0;for(int i=1; i<prices.size(); i++){if(prices[i] > prices[i-1]){pro += prices[i] - prices[i-1];}}return pro;}
};
55. 跳跃游戏
也是一遍做出来了,不过做完之后看解析,写法和卡哥不太一样,卡哥是直接看最大下表覆盖能到哪里,我的这个写法相当于是一个汽车从nums的头开到尾,每个地方都有加油站,那每个nums[i]代表在这里加完油以后,最多能开再开几个地方。
那我这种想法我觉得还是比较形象的,必过相比卡哥的做法很显然还是麻烦了一点。(主要还是不知道一个for循环,如果我们给终止条件里面的值取一个变量,比如卡哥代码里代表最大覆盖范围的cover,那这个cover是会随着循环进行不断变化,还是固定成最开始传入的值,卡哥的代码告诉我是前者。)
除此之外,还漏掉了nums.size()==1时的情况。
class Solution {
public:bool canJump(vector<int>& nums) {int gas = nums[0];int i = 0;if(nums.size()==1){return true;}while(gas > 0){gas--;i++;if(nums[i] > gas){gas = nums[i];}if(i + gas >= nums.size()-1){return true;}}return false;}
};
45.跳跃游戏 II
一开始的想法把这题的思路想出来了八成左右,没做出来的主要原因是没做到变量的干湿分离:
第一遍写的时候我以为maxidex是固定的,但其实在不断地动态更新,导致盯着看了半天看似没啥问题,实则问题很大。
除此之外,判断条件也写成了<maxidx,实则应该是<=才对,边界处理也需要再斟酌。
class Solution {
public:int jump(vector<int>& nums) {if(nums.size()==1){return 0;}int step = 0;int maxidx = nums[0];int previdx = 0;while(maxidx < nums.size()-1){int endturn = maxidx;for(int i=previdx; i<=maxidx; i++){if(i+nums[i]>endturn){endturn = i+nums[i];}}previdx = maxidx+1;maxidx = endturn;step++;}return step+1;}
};
1005.K次取反后最大化的数组和
本题也是,思路上能想明白,但实现总是差点意思,导致做不出来。不过也是学到了不少。
关键问题1:如何找到最小的元素
我的做法是找到第一个非负数的下标i,将其与前一个下标的数的绝对值进行比较。但这样显然是麻烦了,让我们看看卡哥和GPT都是怎么做的:
卡哥:在sort的时候直接传入参数cmp,按绝对值大小排列,这样最右边的元素就是绝对值最小的
GPT:用了一个叫做min_element的函数,返回值指向nums中的最小值的位置,也就是一个迭代器。如果我们想要访问值,需要再前方加入一个*。这里*是解引用符,隐约好像听过又好像没听过的,还是学的不够扎实。
关键问题2:如何求和
使用accumulate(nums.begin(), nums.end(), 0),要传三个参数,第三个是和的初始值。要调用的库是<numeric>。其实和直接一个for循环是一样的。
关键问题3:循环终止条件
应该是i < nums.size() && k > 0,我只写了后面那个,会导致越界问题。
关键问题4:对于翻转操作的处理
因为前面我的做法是找到第一个非负数的下标i并且与前一个元素比较来决出最小,其实并不知道还剩多少次,单纯写了个i-k次for循环的nums[i] = -nums[i],这样其实是很不严谨的,因为如果最小的元素是i-1,那应该nums[i-1]翻转i-k+1次,如果是对nums[i]翻转才是i-k次。所以实际上这么搞是自找麻烦的,不如每次遇到一个负数就k--,这样才是好想的思路。
class Solution {
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(), nums.end());int i=0;for(i=0; i < nums.size() && k > 0; i++){if (nums[i] < 0) {nums[i] = -nums[i];k--;} else {break; }}int min = *std::min_element(nums.begin(), nums.end());if(k%2 == 1){return accumulate(nums.begin(), nums.end(), 0) - min*2;}else{return accumulate(nums.begin(), nums.end(), 0);}}
};