本文主要是介绍代码随想录训练营第三十二天打卡|122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
122.买卖股票的最佳时机II
1.做的时候感觉不难，自己也AC了，但是一下子说清楚为什么这样做并不容易。思考之后，我得到了一个自己感觉还算形象的解释。股票价格走势是一个折线图，两天之间的股票价格构成一条折线。我们只要在每一条上升折线的起始点买入，结束点卖出不放过任何一个赚钱的机会就能获得最大利润。当前最优推出整体最优，典型的贪心，折线模型类似于之前的摆动序列。（注：该算法源于我们站在上帝视角知道之后几天股票的价格，现实中并不可行）
class Solution {
public://贪心：今天能赚就卖，明天能赚就买，不放弃任何一个赚钱的机会int maxProfit(vector<int>& prices) {int sum = 0;for (int i = 0; i + 1 < prices.size(); i++) {if ((prices[i + 1] - prices[i]) > 0)sum += prices[i + 1] - prices[i];}return sum;}
};2.随想录版
class Solution {
public://思想是一样的，当前赚钱就买卖int maxProfit(vector<int>& prices) {int result = 0;for (int i = 1; i < prices.size(); i++) {result += max(prices[i] - prices[i - 1], 0);}return result;}
};55. 跳跃游戏
1.贪心有时候就是朴素思想。本题我们一个朴素的思想就是如果当前位置跳不到最后位置，那我们就在当前位置能跳到的位置中选择能跳的最远的那个，这其实就是贪心！跳的最远的那个位置意味着之后有最多的选择，当前最优推出整体最优。
class Solution {
public:bool canJump(vector<int>& nums) {int sum = 0; // sum表示当前能跳跃到的最远下标//遍历当前元素能跳跃到的位置for (int i = 0; i <= sum; i++) {//如果当前位置能跳到最后直接返回trueif (nums[i] >= nums.size() - i - 1)return true;//如果不能就尝试更新能跳到的最远的位置if (nums[i] + i >= sum)sum = nums[i] + i;}return false;}
};2.随想录版，本质是一样的，cover代表能覆盖的跳跃范围。
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;}
};45.跳跃游戏II
1.其实本题的思路和之前是一样的，每次在能跳到的位置中选择能跳地最远的那个，那么最后的跳跃次数就是最小的那个。只不过本题相比于上一题的难度在于跳跃次数的统计，核心是每次跳到最远的那个位置跳跃次数+1，然后在当前位置能跳跃到的那个位置选择新的那个能跳的最远的位置。其中有些细节要注意，之前的cover是实时更新的，因为我们并不关注跳数。而现在，在遍历当前位置能跳到的位置中，遍历范围是要保持不变的。所以我们要用一个变量cover1接住cover值用于遍历，然后再在遍历过程中更新cover值，当找到新的最大cover值需要记录下次遍历的起始位置i。除此之外，当我们发现当前位置能跳到最后，跳跃次数也要+1。
class Solution {
public:int jump(vector<int>& nums) {if (nums.size() == 1)return 0;// cover表示当前跳跃下标最大值，初始值为数组初始位置int count = 0, cover = nums[0], i = 0;//遍历数组模拟跳跃过程，找跳数while (i < nums.size() - 1) {//跳跃下标能覆盖数组，跳数+1然后跳出循环if (cover >= nums.size() - 1) {count++;break;}int cover1 = cover; //复制cover值//利用复制的cover值更新cover值for (int j = i; j <= cover1; j++) {//找到跳的最远的那个位置并跳到这个位置if (nums[j] + j > cover) {cover = nums[j] + j;i = j;}}count++; //每跳一次，跳数+1}return count;}
};2.随想录版，个人觉得随想录代码虽然简洁，但其实并不是那么容易理解。代码的逻辑应该是这样的：每次确定了起跳位置跳数+1，这也是i < nums.size() - 1的原因所在。因为题目保证一定能跳到最后，所以起跳位置最多只能是nums.size() - 2。这样做的好处是下标i不用回溯，因为当前覆盖的最远距离下标是不断增大的。
class Solution {
public:int jump(vector<int>& nums) {int curDistance = 0; // 当前覆盖的最远距离下标int ans = 0; // 记录走的最大步数int nextDistance = 0; // 下一步覆盖的最远距离下标for (int i = 0; i < nums.size() - 1;i++) { // 注意这里是小于nums.size() - 1，这是关键所在nextDistance =max(nums[i] + i, nextDistance); // 更新下一步覆盖的最远距离下标if (i == curDistance) { // 遇到当前覆盖的最远距离下标curDistance = nextDistance; // 更新当前覆盖的最远距离下标ans++;}}return ans;}
};今日总结：我跳！
这篇关于代码随想录训练营第三十二天打卡|122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
