二刷代码随想录训练营Day 28|122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II、1005.K次取反后最大化的数组和

1.买卖股票的最佳时机2

代码随想录 (programmercarl.com)

代码：

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

 note：思路是，可以在一个表格中把这些价格和天数对应的点都连起来，我们所能获得的最大利润就是表里所有上升段数的数值累加。

2.跳跃游戏

代码随想录 (programmercarl.com)

 代码：

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

note：每次更新size的大小为当前能到达的最远的下标，看看经过遍历后能不能到达最后一个元素的下标。

这里直接在for循环的循环条件里写i <= size，因为size是最远能到达的下标，而且一旦到达nums.size（）-1就会跳出循环，不用担心数组越界的问题。而且size会随着遍历进行更新，我们的循环遍历i一定是在当前可以覆盖的范围内进行遍历的。

3.跳跃游戏2

代码随想录 (programmercarl.com)

代码：

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

 note：这里用了两个遍历curDistance和nextDistance。在for循环中，这次的循环条件是i < nums.size()。如果已经遍历到i == curDistance的时候，就将curDistance更新成nextDistance，同时进行步数的加1，并判断此时是否满足跳出循环的条件。

4.k次取反后最大化的数组和

代码随想录 (programmercarl.com)

代码：

class Solution {
static bool cmp(int a,int b){return abs(a) > abs(b);
} // 按照绝对值大小从大到小排序
public:int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(),nums.end(),cmp);for(int i = 0; i < nums.size(); i++){if(nums[i] < 0 && k > 0){nums[i] *= -1;k--;}}if(k % 2){nums[nums.size() - 1] *= -1;}int sum = 0;for(int a:nums){sum += a;}return sum;}
};

 note：按照常识来就好了。这里体现了两次贪心的思路——一次是将负数变为正数，使得总和更大；另一次是剩余的k的次数，都使用在绝对值最小的元素上，这样可以把影响降到最小。