leetcode算法刷题的第二十四天

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

题目链接

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

思路总结：这道题乍一看感觉挺难的，但其实仔细去想的话其实很简单。我们先把题目给的股票价格列出来，然后算出每一天与下一天的价格之差，因为只有当利润为正的时候才可以对我们求出最大利润有帮助，所以我们只需要将所有的利润里面的正数相加就可以了，这样我们就可以求出买卖股票的最大利润，就是局部最优推出全局最优。

2.leetcode 55.跳跃游戏

题目链接

class Solution {
public:bool canJump(vector<int>& nums) {int cover=0;if(nums.size()==1) return true;// 只有一个元素，就是能达到for(int i=0;i<=cover;i++){// 注意这里是小于等于covercover=max(i+nums[i],cover);if(cover>=nums.size()-1) return true;// 说明可以覆盖到终点了}return false;}
};

思路总结：这道题目我们需要换一个角度来看待问题，不能只局限于跳多少步，这样的话题目会变得非常的困难。

这道题目关键点在于：不用拘泥于每次究竟跳几步，而是看覆盖范围，覆盖范围内一定是可以跳过来的，不用管是怎么跳的。

大家可以看出思路想出来了，代码还是非常简单的。

一些同学可能感觉，我在讲贪心系列的时候，题目和题目之间貌似没有什么联系？

是真的就是没什么联系，因为贪心无套路！没有个整体的贪心框架解决一系列问题，只能是接触各种类型的题目锻炼自己的贪心思维！这里的cover就是我们所可以覆盖的范围，只要这个范围大于等于边界的范围，就说明可以达到最后一个下标的位置。

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

3.leetcode 45.跳跃游戏II

题目链接

class Solution {
public:int jump(vector<int>& nums) {if(nums.size()==1) return 0;int curDistance=0;// 当前覆盖最远距离下标int nextDistance=0;// 下一步覆盖最远距离下标int count=0;// 记录走的最大步数for(int i=0;i<nums.size();i++){nextDistance=max(i+nums[i],nextDistance);// 更新下一步覆盖最远距离下标if(i==curDistance){// 遇到当前覆盖最远距离下标count++;// 需要走下一步curDistance=nextDistance;// 更新当前覆盖最远距离下标（相当于加油了）// 当前覆盖最远距到达集合终点，不用做count++操作了，直接结束if(nextDistance>=nums.size()-1) break;}}return count;}
};

思路总结：思路还是跟上一道题目是相似的，还是要看最大覆盖范围。

本题要计算最少步数，那么就要想清楚什么时候步数才一定要加一呢？

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

思路虽然是这样，但在写代码的时候还不能真的能跳多远就跳多远，那样就不知道下一步最远能跳到哪里了。

所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数！

这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

理解本题的关键在于：以最小的步数增加最大的覆盖范围，直到覆盖范围覆盖了终点，这个范围内最少步数一定可以跳到，不用管具体是怎么跳的，不纠结于一步究竟跳一个单位还是两个单位。

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

题目链接

class Solution {
public:static bool cmp(int a,int b){return abs(a)>abs(b);}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==1) nums[nums.size()-1]*=-1;int sum=0;for(int i=0;i<nums.size();i++){sum+=nums[i];}return sum;}
};

思路总结：

本题思路其实比较好想了，如何可以让数组和最大呢？

贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。

局部最优可以推出全局最优。

那么如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让 数组和 达到最大。

那么又是一个贪心：局部最优：只找数值最小的正整数进行反转，当前数值和可以达到最大（例如正整数数组{5, 3, 1}，反转1 得到-1 比 反转5得到的-5 大多了），全局最优：整个 数组和 达到最大。

虽然这道题目大家做的时候，可能都不会去想什么贪心算法，一鼓作气，就AC了。

我这里其实是为了给大家展现出来 经常被大家忽略的贪心思路，这么一道简单题，就用了两次贪心！

那么本题的解题步骤为：

• 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
• 第二步：从前向后遍历，遇到负数将其变为正数，同时K--
• 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
• 第四步：求和

  贪心的题目如果简单起来，会让人简单到开始怀疑：本来不就应该这么做么？这也算是算法？我认为这不是贪心？

  本题其实很简单，不会贪心算法的同学都可以做出来，但是我还是全程用贪心的思路来讲解。

  因为贪心的思考方式一定要有！

  如果没有贪心的思考方式（局部最优，全局最优），很容易陷入贪心简单题凭感觉做，贪心难题直接不会做，其实这样就锻炼不了贪心的思考方式了。

  所以明知道是贪心简单题，也要靠贪心的思考方式来解题，这样对培养解题感觉很有帮助。