当前位置: 首页 > article >正文

LeetCode刷题日记之贪心算法(二)

目录

  • 前言
  • 买卖股票的最佳时机II
  • 跳跃游戏
  • 跳跃游戏II
  • 总结


前言

在上一篇贪心算法的学习中,我们探讨了贪心算法的基本思路和逻辑框架。在这篇文章中,我将继续分享几道经典的LeetCode贪心算法题,并探讨其背后的解题思路和技巧。希望通过这些题目的实践,能加深我对贪心算法的理解,也为同样在刷题的小伙伴提供更多思考和启发✍✍✍

买卖股票的最佳时机II

LeetCode题目链接

这道题就是给一个整数数组 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;
    }
}

代码也很简单,我们继续来学习下一道题✍✍✍

跳跃游戏

leetCode题目链接

这道题就是一个整数数组,数组每个数表示你在这个位置的最大可跳跃长度,初始在数组第一个下标,然后判断你能不能跳到数组最后一个下标处🤔🤔🤔

请添加图片描述

我们来思路梳理

  • 这道题我们用贪心算法去解决的话,它的目标是判断能否从数组的第一个位置跳跃到最后一个位置,我们的核心思路就是在遍历数组的过程中 维护一个当前能到达的最远位置并逐步更新这个最远位置,判断它是否能够覆盖到最后一个下标🤔🤔🤔

这么说可能还是不够清晰,我们展开思路

  • 每次在当前位置 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

LeetCode题目链接

这道题和上一道题相比就是这次不返回能否可达了,而是返回最小跳跃次数

请添加图片描述

我们来思路梳理

  • 这道题和上道题不同的是这道题的关键在于如何选择每一步的跳跃,使得每次都能跳到最远的地方,从而减少跳跃次数🤔🤔🤔

我们来进一步梳理贪心的四个子逻辑

  • 如何判断最优解

    • 最优解是能够到达最后一个位置的最少跳跃次数 ,每一步都尽可能跳到最远的位置,以减少总跳跃次数。每次跳跃后更新跳跃范围,直到能跳到最后一个位置为止🤔🤔🤔
  • 判断局部最优选择的可行性

    • 局部最优选择是在当前能够跳跃的范围内,找到可以跳到的最远位置。当到达当前跳跃范围的边界时,我们就进行一次跳跃,并更新下一步的跳跃范围。这样可以确保我们每次都选择最远的跳跃,从而减少跳跃次数🤔🤔🤔
  • 更新问题状态

    • 每次跳跃时,我们更新两个状态,一个是下一步的跳跃范围(也就是最远跳跃位置),另一个是跳跃的次数(每次跳跃完成则跳跃次数加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;
    }
}

总结

今天是继续学习贪心算法的第二天,大家一起加油✊✊✊


http://www.kler.cn/news/356168.html

相关文章:

  • 【汇编语言】寄存器(内存访问)(七)—— CPU提供的栈机制
  • python从0快速上手(十二)高级特性2
  • 如何接受Date范围的数据
  • Chrome DevTools 三: Performance 性能面板扩展—— 性能优化
  • Python | basemap空间绘图 | cartopy | geoviews
  • ABAP:创建/修改客户的银行信息
  • 深度学习模型训练的主要流程(不定时更新中)
  • javaScript逆向怎样做
  • 【赵渝强老师】Oracle的联机重做日志文件与数据写入过程
  • 使用正则解决SQL注入问题
  • 对于六上前二单元的一些感想
  • [Hbase]一 HBase基础
  • 【论文速看】DL最新进展20241019-人脸识别、多模态
  • 使用Radzen Blazor组件库开发的基于ABP框架炫酷UI主题
  • vue el-drawer 标签点击蒙版就关闭的问题
  • Java基于SSM框架的教学辅助微信小程序【附源码、文档】
  • DS几大常见排序讲解和实现(上)(13)
  • MySQL 安装与配置详细教程
  • C语言预处理
  • 每日一题学习笔记——移动零