【代码随想录】day32

2024-04-02 11:36

文章标签 随想录代码 day32

本文主要是介绍【代码随想录】day32，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

一、122买卖股票的最佳时机II
二、55跳跃游戏
三、45跳跃游戏II

一、122买卖股票的最佳时机II

方法1:计算斜率大于0的线段的diffY

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

方法2:套摆动序列模版

class Solution {
public:int maxProfit(vector<int>& prices) {int res = 0;if (prices.size() < 2) return res;//找拐点，记录上升段int preDiff = 0;int curDiff, buyPrice;for (int i = 1; i < prices.size(); i ++) {curDiff = prices[i] - prices[i-1];if (preDiff <= 0 && curDiff > 0) {buyPrice = prices[i-1];while (i < prices.size() && prices[i] > prices[i-1]) {i ++;}res += prices[i-1] - buyPrice;}}return res;}
};

方法3:把总收益折算成每日收益，累加正利润

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

二、55跳跃游戏

思路：找最大覆盖范围

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

三、45跳跃游戏II

class Solution {
public:int jump(vector<int>& nums) {int res = 0;int cover = 0;int maxCover = 0;for (int i = 0; i <= cover && i < nums.size(); i ++) {if (i > maxCover) {res ++;maxCover = cover;}cover = max(cover, i + nums[i]);}return res;}
};