代码随想录算法训练营Day32 | 122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏II

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

题目链接：LeetCode 122.买卖股票的最佳时机II

思路：
累计每天的利润

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

注意：
1.

LeetCode 55. 跳跃游戏

题目链接：LeetCode 55. 跳跃游戏

思路：
不断更新覆盖范围，只需要覆盖范围超过数组长度即可。

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

注意：
1.
2.
3.
4.

LeetCode 45.跳跃游戏II

题目链接：LeetCode 45.跳跃游戏II

思路：

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()==1) return 0;
        int cur_dist = 0;
        int next_dist = 0;
        int jump = 0;
        for(int i=0; i<nums.size(); i++){
            next_dist = max(next_dist, nums[i]+i);
            if(i == cur_dist){
                jump ++;
                cur_dist = next_dist;
                if(next_dist >= nums.size()-1) break;
            }
        }
        return jump;
    }
};