您现在的位置是:首页 >技术交流 >代码随想录算法训练营day32 | 贪心算法:122.买卖股票的最佳时机II ,55. 跳跃游戏,45.跳跃游戏II网站首页技术交流

代码随想录算法训练营day32 | 贪心算法:122.买卖股票的最佳时机II ,55. 跳跃游戏,45.跳跃游戏II

小鲨鱼冲冲冲 2024-06-14 17:17:26
简介代码随想录算法训练营day32 | 贪心算法:122.买卖股票的最佳时机II ,55. 跳跃游戏,45.跳跃游戏II

代码随想录算法训练营day32 | 贪心算法:122.买卖股票的最佳时机II ,55. 跳跃游戏,45.跳跃游戏II


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

教程视频:https://www.bilibili.com/video/BV1ev4y1C7na/?spm_id_from=333.788&vd_source=ddffd51aa532d23e6feac69924e20891
在这里插入图片描述在这里插入图片描述收集每天的正利润。

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int dayProfit = 0;
        for(int i=0;i<prices.length-1;i++){
            dayProfit = prices[i+1]-prices[i];
            if(dayProfit>0){
                maxProfit+=dayProfit;
            }
            //简化版本:maxProfit += Math.max(prices[i+1] - prices[i], 0);
        }
        return maxProfit;
    }
}

55. 跳跃游戏

教程视频:https://www.bilibili.com/video/BV1VG4y1X7kB/?spm_id_from=pageDriver&vd_source=ddffd51aa532d23e6feac69924e20891
在这里插入图片描述这道题目关键点在于:不用拘泥于每次究竟跳几步,而是不断寻找当前覆盖范围,覆盖范围内一定是可以跳过来的,不用管是怎么跳的。

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

例如示例1中:初始位置数字是2,最远位置更新为索引2,可以跳到值为3和1;先看3,此时更新最远位置为4等于数组长度,循环结束。

//基础版
class Solution {
    public boolean canJump(int[] nums) {
        int maxIndex = nums[0];
        for(int i=0;i<=maxIndex && i<nums.length;i++){
            if((nums[i]+i)>maxIndex){
                maxIndex=nums[i]+i;
            }
        }
        if(maxIndex>=nums.length-1){
            return true;
        }else{
            return false;
        }
    }
}
//优化版
class Solution {
    public boolean canJump(int[] nums) {
        int maxIndex = nums[0];
        for(int i=0;i<=maxIndex && i<nums.length;i++){
            maxIndex=Math.max(nums[i]+i,maxIndex);
            if(maxIndex>=nums.length-1){
                return true;
            }
        }
        return false;
    }
}

45.跳跃游戏II

教程视频:https://www.bilibili.com/video/BV1Y24y1r7XZ/?spm_id_from=pageDriver&vd_source=ddffd51aa532d23e6feac69924e20891
在这里插入图片描述用最少的步数增大覆盖范围。
记录最大覆盖范围的更新次数。

class Solution {
    public int jump(int[] nums) {
        int cur = 0;//表示当前最远覆盖位置
        int next = 0;//记录下一个最远覆盖范围
        int jump = 0;
        for(int i=0; i<nums.length; i++){
            next = Math.max(i+nums[i],next);
            if(i==cur){//到当前最远位置判断是否进行下一跳
                if(cur<nums.length-1){
                    cur=next;
                    jump++;
                }else{
                    break;
                }
            }
        }
        return jump;
    }
}

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。