算法Day32

算法Day32

Day32

• • 122.买卖股票的最佳时机II
  • 55. 跳跃游戏
  • 45.跳跃游戏 II

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

题目链接：122.买卖股票的最佳时机II
我又不够“贪”。😦
prices对应一个利润数组，price[7, 1, 5, 3, 6, 4]，profit[0, -6, 4, -2, 3, -2]，局部最优解就是为利润为正相加。
如果price[1,2,3,4,5]，profit[0,1,1,1,1]，利润相加的总和与第一天买入，最后一天卖出是一样的。
因为 p r i c e 3 − p r i c e 0 = p r i c e 3 − p r i c e 2 + p r i c e 2 − p r i c e 1 + p r i c e 1 − p r i c e 0 price_3 - price_0 = price_3 - price_2 + price_2 - price_1 + price_1 - price_0 price3​−price0​=price3​−price2​+price2​−price1​+price1​−price0​

class Solution {
public:int maxProfit(vector<int>& prices) {int res = 0;for (int i = 1/*第二天才能有利润*/; i < prices.size(); ++i) {res += prices[i] - prices[i - 1] > 0 ? prices[i] - prices[i - 1] : 0;
//            res += max(prices[i] - prices[i - 1], 0);//等价于上一行}return res;}
};

55. 跳跃游戏

题目链接：55. 跳跃游戏
索引对应的数组值视为覆盖范围，最后层层覆盖，只要覆盖了终点就可以。

class Solution {
public:bool canJump(vector<int>& nums) {if (nums.size() == 1) return true;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;}
};

45.跳跃游戏 II

题目链接：45.跳跃游戏 II
也是用覆盖范围，同时需要另一个范围来记录当前范围中，能走到的最远的距离，也就是下一步覆盖的范围。
题目说一定会到回到终点，因此当覆盖到倒数第二个之后，继续遍历，res+1，就一定是答案。因此，将for循环的终止条件改为 i < nums.size() - 1;

class Solution {
public:int jump(vector<int>& nums) {if (nums.size() == 1) return 0;int cur = 0, next = 0;int res = 0;for (int i = 0; i < nums.size() - 1; ++i) {next = max(i + nums[i], next);if (i == cur/*可以执行到此处，i == cur，证明cur< nums.size() - 1*/) {res++;cur = next;}}return res;}
};