算法训练营Day29

2023-12-31 17:25:26

#Java #贪心

开源学习资料

Feeling and experiences:

买卖股票的最佳时机 II:力扣题目链接

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

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

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

该题目也很直接,买股票,就是低买高卖

思路:

那么只要第二天的价格大于第一天的,那么就可以第一天买,第二天卖,以此类推下去......

class Solution {
    public int maxProfit(int[] prices) {
    //低买高出
    //贪心:只要第二天比今天的收益高就可以买了再卖
    int profit = 0;
    for(int i = 1; i<prices.length;i++){
        if(prices[i] > prices[i-1]){
        profit+=prices[i] - prices[i-1];
        }
    }
    return profit;
    }
}

在这里就先不用动态规划做了,到动态规划专题再细解。

跳跃游戏:力扣题目链接

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

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

思路:

1. 初始化?maxposition?为?0,用于记录在遍历数组时能到达的最远位置。


2. 遍历数组?nums。对于每个位置?i:
? 如果?i?大于当前记录的?maxposition,说明无法跳到位置?i,因此返回?false。
? 更新?maxposition?为?maxposition?和?i?+?nums[i]?中的较大值,这表示从当前位置或之前的位置能跳到的最远距离。


3. 如果能遍历完整个数组,则说明可以从第一个位置跳到最后一个位置,返回?true。

核心在于贪心算法的应用,即在每一步都尽可能向前跳最远,以此判断是否能到达数组末尾

class Solution {
    public boolean canJump(int[] nums) {
    //记录每次能到达的最大位置
    int maxposition = 0;
    for(int i = 0;i<nums.length;i++){
    if(i > maxposition){
        return false;
    }
    //跟新
    maxposition = Math.max(maxposition,i+nums[i]);

    }
    return true;
    }
}

跳跃游戏 II:力扣题目链接

给定一个长度为 n0 索引整数数组 nums。初始位置为 nums[0]

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i]?
  • i + j < n

返回到达?nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]

其实就是在跳跃游戏的基础上多了一个边界需要维护:

检查是否达到了当前的右边界?(if?(i?==?end))。
如果达到了,需要进行一次新的跳跃,因此?steps?加一,并更新?end?为?maxPosition,即下一次跳跃的目标位置。
?

class Solution {
    public int jump(int[] nums) {
//定义数组长度
int len = nums.length;
//定义能跳到的最远位置
int maxPosition =0;
//定义右边界(用于维护)
int end = 0;
//定义计数器
int steps = 0;


//用for循环依次遍历
for(int i =0; i<len-1;i++){
    maxPosition = Math.max(maxPosition,i+nums[i]);
//如果i到达了右边界
    if(i == end){
end = maxPosition;
steps++;
    }
}
return steps;
    }
}

天下万般兵刃,

唯有过往伤人最深~

Fighting!

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