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

[贪心]376. 摆动序列 53. 最大子序和 122.买卖股票的最佳时机II 55. 跳跃游戏 45. 跳跃游戏II

 376. 摆动序列

首先我就没认真读题,本题是求摆动子序列的最长长度,我以为是连续的,其实是选取元素作为摆动子序列。

本题贪心的地方在于:每次只选取前后差值变号的元素(即峰值),不用在意峰值和谷值之间的中间值

定义predif和curdif记录当前和上一对相邻元素的差值,若异号则说明出现了峰值,ans++。否则讲cur赋值给pre再进行下一次峰值的判断。最后返回ans。

53. 最大子序和

本题精髓为:当连续和为负数时立刻放弃,从下一个元素重新计算连续和。

本题一开始想到了若sum<0直接sum=0就可以,但是后来提交时出现了全是负数的测试用例难住了我,看题解发现将max值一开始定义为Integer.MIN_VALUE再与sum进行比较即可。(注意要max先与sum进行比较再令sum=0)

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

本题精髓为:题目只求最大利润,因此不用在意是哪一天买入卖出,只求正利润的和即可

因为p3-p1=p3-p2+p2-p1。因此p1买入p3卖出的利润 等于p1买p2卖p2卖p3卖,即p3与p2的利润加p2与p1的利润

55. 跳跃游戏

本题求的是是否能达到最后一个下标,不用在意从哪里跳,只需在意当前跳的覆盖范围能否达到最后一个下标即可

定义cover代表当前能覆盖的下标,每次循环与新的下标所能覆盖的最大下标进行比较,取大值。

判断若cover>len-1,则代表能到末尾,返回true。

45. 跳跃游戏II

本题求的是跳跃的最小步数,不用在意从哪开始跳,以最小的步数增加覆盖范围,每次都跳到当前能跳的覆盖范围了在进行新的跳跃,跳跃到新的嘴大覆盖范围即可。前i步所能跳最大范围记为next,若当前下标为当前下标所能跳的最大范围即cur==i,若没达到末尾,则步数加一,更新cur的值为next(新的最大覆盖范围)。否则达到末尾直接return ans。

相关文章:

  • 【SpringBoot3】SpringBoot中实现全局统一异常处理
  • 分支语句(选择结构)——“C”
  • 【寒假每日一题】洛谷 P6421 [COCI2008-2009#2] RESETO
  • aws codesuit 在codebuild和codepipeline中集成jenkins
  • DPU网络开发SDK—DPDK(八)
  • DW 2023年1月Free Excel 第五次打卡 文本函数
  • 第四层:友元与函数成员别样定义
  • SpringCloud(11):Hystrix请求合并
  • SpringBoot的自动配置
  • C语言萌新如何使用scanf函数?
  • TryHackMe-NahamStore(常见web漏洞 大杂烩)
  • 【Java入门】Java数据类型