算法训练day32｜贪心算法part02

2023-12-15 18:35:45

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

局部最优：记录每天的利润，只需要累加利润为正的天数

// 贪心思路
class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        for (int i = 1; i < prices.length; i++) {
            result += Math.max(prices[i] - prices[i - 1], 0);
        }
        return result;
    }
}

55. 跳跃游戏

每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

45.跳跃游戏 II

贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最少步数。

如果当前范围内不够到达终点，需要多跳一步，开启下一个范围

nums.length==1为特殊情况需要单独讨论

文章来源:https://blog.csdn.net/AdrianLeon/article/details/134985084
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。