【代码随想录训练营】【Day32】第八章｜贪心算法｜122.买卖股票的最佳时机II ｜55. 跳跃游戏｜45.跳跃游戏II

买卖股票的最佳时机II

题目详细：LeetCode.122

买卖股票的最佳时机，怎么都能够想出来个思路，假如我们每天都能预知明天的股票是涨是降，那么贪心策略就是在涨之前买股票，在降的前一天卖掉，这就是买卖股票的最佳时机。

于是我立马一顿模拟！

Java解法（贪心，模拟）：

class Solution {public int maxProfit(int[] prices) {if(prices.length <= 2){return prices.length > 1 && prices[0] < prices[1] ? prices[1] - prices[0]: 0;}int buy = -1, sale = -1, pre = 0, cur = 1, count = 0, max = 0;while(cur < prices.length){if(buy == -1 && prices[pre] < prices[cur]){buy = prices[pre];}if(buy != -1 && sale == -1 && (prices[pre] > prices[cur] || cur + 1 == prices.length)){sale = Math.max(prices[pre], prices[cur]);count += sale - buy;buy = -1;sale = -1;}pre++;cur++;max = Math.max(max, count);}return max;}
}

这个模拟解法是完全能够AC的，但时间代码看起来就很复杂，因为是从整体去计算买卖股票的利润。

不过我们也可以把利润分解为每天为单位的维度，只需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，然后将正利润的数值都相加得到最终利润，不需要记录买卖的区间，可得贪心策略：

• 局部最优解：收集每天的正利润
• 全局最优解：累计正利润可得最大利润

Java解法（贪心）：

class Solution {public int maxProfit(int[] prices) {int ans = 0;int[] profits = new int[prices.length - 1];for(int i = 1; i < prices.length; i++){profits[i - 1] = prices[i] - prices[i - 1];if(profits[i - 1] > 0) ans += profits[i - 1];}return ans;}
}

---

跳跃游戏

题目详细：LeetCode.55

个人觉得卡哥的题解写得非常清晰易懂，所以我就不加以赘述了，详细的题解可查阅：《代码随想录》— 跳跃游戏

这题的思路需要转化一下，转化为跳跃的覆盖范围能不能覆盖到终点：

• 从数组的第一个下标开始，计算其跳跃覆盖范围内所有下标的最大跳跃长度
• 记录并得到最大的跳跃覆盖范围cover，就更新最大的跳跃覆盖范围
• 注意条件是i <= cover不是i <= nums.length，因为跳跃的覆盖范围应该是连续的

贪心策略：

• 局部最优解：每一次都计算出最大跳跃覆盖范围）
• 整体最优解：最后得到整体的最大覆盖范围，看是否能到终点（nums.length - 1）。

class Solution {public boolean canJump(int[] nums) {int cover = 0, i = 0;while(i <= cover && cover < nums.length - 1){cover = Math.max(cover, i + nums[i++]);}return cover >= nums.length - 1;}
}

---

跳跃游戏II

题目详细：LeetCode.45

这道题相较于上一题，区别在于要求计算到达终点的最少跳跃次数是多少

前一题只要求判断是否能够跳跃到终点，我们只需要求从下标为0的位置开始，其覆盖范围内每一个元素的最大跳跃覆盖距离是多少，在过程中如果能够覆盖到终点就返回true；

但是这一题要求最少跳跃次数，所以就多了一个问题，在跳跃过程中能够判断其是否能够覆盖到终点，但是什么时候应该累计跳跃次数呢？

下面我们将本题的解题思路和上一题做对比，说明在做题时需要注意的地方：

题目说明从下标为0的位置开始跳跃，所以我们可以初始化一个跳跃覆盖范围，大小为nums[0]，我们可以利用上一题的思路，计算出后续跳跃覆盖范围内每一个位置的跳跃覆盖范围，但是在这一题中，我们需要额外定义一个变量pre_cover，来记录当前这一步的跳跃覆盖范围，为什么呢？

因为我们的贪心策略需要遍历当前这一步的跳跃覆盖范围内所有的位置，并计算出它们的跳跃覆盖范围，保证下一次跳跃的位置，能够让我们尽可能的跳得更远，并记录一个最大的跳跃覆盖范围并更新到变量cover；

如果我们直接更新cover，那么由于题目保证所有的测试样本都能跳跃到达终点，且如果不修改条件i <= cover && cover < nums.length - 1的话，所以下标i将一直更新到终点，但是这样一来我们就无法确定跳跃步数更新的时机了。

具体的改动如下：

• 定义一个变量pre_cover，并且修改循环条件为i <= cur_cover && cur_cover < nums.length - 1
• 当i == cur_cover时，但是由于cur_cover < nums.length - 1，说明我们一次跳跃还不能跳跃到终点，所以需要增加跳跃次数step++，然后更新cur_cover = cover
• 更新cur_cover = cover即表示我们下一步的最大跳跃覆盖距离是多少，如果下一步就能够覆盖到终点就跳出循环，则跳出循环，返回步数step + 1（这里我初始化 step = 1，结果一样），否则继续循环累计跳跃次数

最后简单描述下本题的贪心策略：

• 局部最优解：每一步都尽可能的跳到下一步能够跳得最远的位置上，每一次跳跃到下一步后，累计一次跳跃次数
• 整体最优解：整体跳的次数最少，跳的距离最长，累计得到跳跃到达终点的总次数

Java解法（贪心）：

class Solution {public int jump(int[] nums) {if(nums.length == 1 || nums.length == 2){return nums.length - 1;}int cover = 0, cur_cover = nums[0], i = 0, step = 1;while(i <= cur_cover && cur_cover < nums.length - 1){cover = Math.max(cover, i + nums[i]);if(i++ == cur_cover){step++;cur_cover = cover;}}return step; }
}

注意：我的题解中为什么使用的特判条件是nums.length == 1 || nums.length == 2？

因为题目把测试样本的要求放宽了，保证给出的测试样本都可以到达中终点nums[n-1]，所以对于非法的输入，如[0,0]，我的题解并不能够得出正确的结果，感兴趣的可以在本题解的基础上修改编码，保证其严谨性。

---

在做贪心的题目时，我们一开始都是直接开始模拟，模拟AC后我很开心，不过还是得等到看了题解，才晓得其中的贪心策略，然后用更加简洁的编码再次解题。

这样做虽然很耗时，但是也让我对贪心策略的理解有了越来越得心应手的感觉，甚至能够像最后一题一样，再做题之后，根据自己的思路和上一题的思路做比较，写出两道题的不同的和需要注意的地方。

昨晚做到最后一题的时候，很困了，本来想着要不要直接看题解过了算了，但是我下定决心直接睡觉，盖上电脑等明天再来想一想，很开心自己没有放弃，我发现我这种笨人，做事没啥效率的，更应该在学习和做题时不要太去关心时间上的损失，有所收获才是最重要的！

如果还是跟以前一样遇到困难就退缩，看书学习都是囫囵吞枣，到头来不仅花了时间还一事无成，落笔一句诗激励一下自己：

长风破浪会有时，直挂云帆济沧海。