题目1:122 买卖股票的最佳时机Ⅱ
题目链接:122 买卖股票的最大时机Ⅱ
题意
整数数组prices[i]表示某股票的第i天的价格,每天可买卖股票且最多持有1股股票,返回最大利润
利润拆分,拆分为每天的利润 每天的正利润相加 得到总利润
局部最优:只收获每天的正利润 全局最优:利润最大
代码
class Solution {
public:int maxProfit(vector<int>& prices) {int result = 0;for(int i=1;i<prices.size();i++){if(prices[i]-prices[i-1]>0) result += prices[i]-prices[i-1];}return result;}
};
- 时间复杂度:O(n)
- 空间复杂度:O(1)
题目2:55 跳跃游戏
题目链接:55 跳跃游戏
题意
非负整数数组数组中的每个元素代表在该位置可以跳跃的最大长度 是否能够到达最后一个下标
当前处于数组的第一个下标处
不看每次具体跳几步,只看覆盖范围是否包含终点 在覆盖范围内的位置都可以被跳到
局部最优:每次取最大的覆盖范围 全局最优:得到最大的覆盖范围
代码
class Solution {
public:bool canJump(vector<int>& nums) {int cover = 0;for(int i=0;i<=cover;i++){//更新覆盖范围cover = max(cover,i+nums[i]);if(cover>=nums.size()-1) return true;}return false;}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1)
题目3:45 跳跃游戏Ⅱ
题目链接:45 跳跃游戏Ⅱ
题意
非负整数数组元素nums[i]表示可以跳转的最大长度,返回到达最后一个元素的最小跳跃次数,初始位置为nums[0]
每一步尽可能地往远跳,一旦跳到终止位置,最少的跳跃步数增加覆盖范围
代码
class Solution {
public:int jump(vector<int>& nums) {int cur = 0;int next = 0;int result = 0;for(int i=0;i<nums.size();i++){next = max(next, i + nums[i]);if(i==cur){if(cur!=nums.size()-1){result++;cur = next;if(cur>=nums.size()-1) break;}}}return result;}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1)