Day28- 贪心算法part02-Toy模板网

这篇具有很好参考价值的文章主要介绍了Day28- 贪心算法part02。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

题目一：122. 买卖股票的最佳时机II

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

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的最大利润 。

贪心算法的核心思想是只要明天的价格比今天高，就在今天买入，明天卖出。这样，通过累积每一次的小利润，可以得到最大的总利润。

prices 数组表示股票每天的价格。函数 maxProfit 计算并返回最大利润,遍历价格数组，只要发现第二天的价格高于今天的价格，就计算这一天的利润，并累加到总利润中。最后返回总利润。

/*
 * @lc app=leetcode.cn id=122 lang=cpp
 *
 * [122] 买卖股票的最佳时机 II
 */

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

二、跳跃游戏

题目一：55. 跳跃游戏

55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

在每一步都更新能够到达的最远距离。遍历数组中的每个元素，不断更新从当前位置或之前的位置能够到达的最远距离。如果在任何时刻，这个最远距离小于当前位置的索引，这意味着无法到达当前位置，因此也就无法到达数组的最后一个位置。

/*
 * @lc app=leetcode.cn id=55 lang=cpp
 *
 * [55] 跳跃游戏
 */

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

        return false;  
    }
};
// @lc code=end

题目二：45. 跳跃游戏II

核心思想是在每一步跳跃中，都选择能够使跳得最远的选项。

在遍历数组的过程中，不断更新在当前跳跃范围内，能够达到的最远距离。一旦到达或超过当前跳跃范围的末尾，增加跳跃次数，并更新跳跃范围。文章来源地址https://www.toymoban.com/news/detail-791811.html

/*
 * @lc app=leetcode.cn id=45 lang=cpp
 *
 * [45] 跳跃游戏 II
 */

// @lc code=start
class Solution {
public:
    int jump(vector<int>& nums) {
        int jumps = 0, currentEnd = 0, farthest = 0;
    
        for (int i = 0; i < nums.size() - 1; ++i) {
            farthest = std::max(farthest, i + nums[i]);

            if (i == currentEnd) {
                jumps++;  
                currentEnd = farthest;  
                if (currentEnd >= nums.size() - 1) break;
            }
        }

        return jumps;
    }

};
// @lc code=end

到了这里，关于Day28- 贪心算法part02的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！