LeetCode刷题日记之贪心算法（二）
前言
在上一篇贪心算法的学习中，我们探讨了贪心算法的基本思路和逻辑框架。在这篇文章中，我将继续分享几道经典的LeetCode贪心算法题，并探讨其背后的解题思路和技巧。希望通过这些题目的实践，能加深我对贪心算法的理解，也为同样在刷题的小伙伴提供更多思考和启发✍✍✍
买卖股票的最佳时机II
这道题就是给一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格，然后每天你可以选择购入或者卖出，要求最大利润🤔🤔🤔
我们来思路梳理
- 我们使用贪心算法，通过局部最优来计算全局最优，如果今天的价格高于昨天的价格，我们就在昨天买入、今天卖出，赚取当天的差价🤔 通过不断选择局部最优解（每天都尽可能买卖股票赚取差价），累加所有的利润，最终获得最大利润🤔只要今天的价格比前一天高，就可以视为一个机会进行交易，赚取当天的利润。通过这样的贪心选择，可以确保我们获得最大利润🤔
很清晰的思路，我们直接来编码
class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0; //初始化最大利润为0
//从第二天开始遍历数组
for(int i = 1; i < prices.length; i++){
//判断局部最优
if(prices[i] > prices[i - 1]) maxProfit += prices[i] - prices[i - 1];//累加今天和昨天的差值作为利润
}
return maxProfit;
}
}
代码也很简单，我们继续来学习下一道题✍✍✍
跳跃游戏
这道题就是一个整数数组，数组每个数表示你在这个位置的最大可跳跃长度，初始在数组第一个下标，然后判断你能不能跳到数组最后一个下标处🤔🤔🤔
我们来思路梳理
- 这道题我们用贪心算法去解决的话，它的目标是判断能否从数组的第一个位置跳跃到最后一个位置，我们的核心思路就是在遍历数组的过程中 维护一个当前能到达的最远位置并逐步更新这个最远位置，判断它是否能够覆盖到最后一个下标🤔🤔🤔
这么说可能还是不够清晰，我们展开思路
- 每次在当前位置
i，根据当前元素nums[i]表示的最大跳跃长度，计算从当前位置能够跳到的最远位置。如果最远位置超过或等于数组的最后一个下标，说明可以到达。通过不断更新能够跳到的最远位置，确保我们总是选择最远的跳跃路径，以尽可能覆盖更多位置。如果最远位置最终覆盖到数组末尾，则可以到达最后一个下标🤔🤔🤔
这样已经很清楚了我们来进行编码
class Solution {
public boolean canJump(int[] nums) {
int maxReach = 0;//初始化最远可达位置
for(int i = 0; i < nums.length; i++){//遍历数组元素
//判断局部最优的可行性
if(i > maxReach)return false;//已经超出最远可达位置了
//更新问题状态
maxReach = Math.max(maxReach, i + nums[i]);//更新最远可达位置
if(maxReach >= nums.length - 1)return true;//可达最后位置
}
return true;
}
}
这道题的核心就是一个最远可达位置变量的维护🤔🤔🤔
跳跃游戏II
这道题和上一道题相比就是这次不返回能否可达了，而是返回最小跳跃次数
我们来思路梳理
- 这道题和上道题不同的是这道题的关键在于如何选择每一步的跳跃，使得每次都能跳到最远的地方，从而减少跳跃次数🤔🤔🤔
我们来进一步梳理贪心的四个子逻辑
-
如何判断最优解
- 最优解是能够到达最后一个位置的最少跳跃次数 ，每一步都尽可能跳到最远的位置，以减少总跳跃次数。每次跳跃后更新跳跃范围，直到能跳到最后一个位置为止🤔🤔🤔
-
判断局部最优选择的可行性
- 局部最优选择是在当前能够跳跃的范围内，找到可以跳到的最远位置。当到达当前跳跃范围的边界时，我们就进行一次跳跃，并更新下一步的跳跃范围。这样可以确保我们每次都选择最远的跳跃，从而减少跳跃次数🤔🤔🤔
-
更新问题状态
- 每次跳跃时，我们更新两个状态，一个是下一步的跳跃范围（也就是最远跳跃位置），另一个是跳跃的次数（每次跳跃完成则跳跃次数加1）🤔🤔🤔
-
重复选择
- 遍历数组，逐步更新能够跳跃的最远位置，每次达到当前跳跃范围的边界时进行跳跃，直到能够跳到或超过最后一个位置🤔🤔🤔
-
我们在每一步的跳跃范围内，找到能够跳到的最远位置，一旦超出当前跳跃范围，就进行跳跃，并更新跳跃的范围。每次跳到最远位置时，跳跃次数加 1，直到能够到达或超过最后一个位置🤔🤔🤔
class Solution {
public int jump(int[] nums) {
int jump = 0;//初始化跳跃次数
int maxReach = 0;//记录最远可达位置
int endOfCurrentJump = 0;//记录当前跳跃范围的边界
for(int i = 0; i < nums.length - 1; i++){//不需要遍历到最后一个数，能跳过去
//判断局部最优选择的可信性
maxReach = Math.max(maxReach, i + nums[i]);//更新最远可达位置
//到达跳跃边界时进行跳跃
if(i == endOfCurrentJump){
jump++;
endOfCurrentJump = maxReach;//更新下一次跳跃范围
if(endOfCurrentJump >= nums.length - 1)break;
}
}
return jump;
}
}
总结
今天是继续学习贪心算法的第二天，大家一起加油✊✊✊
原文地址：https://blog.csdn.net/qq_48694749/article/details/143063045
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！