算法训练营Day29

#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：力扣题目链接

给定一个长度为 n 的 0 索引整数数组 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！