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

算法题(76):跳跃游戏II

审题:
在确定一定可以到达数组末尾位置的前提下,查找跳跃次数最少得跳跃次数

思路:

方法一:反向查找最少次数
首先我们反向来思考,若我们要跳到pos位置(初始化为n-1位置),最后一步有多情况,但是最后一步跳出位置的索引值越小,跳跃次数越少。以此类推,我们将该跳出位置更新为pos,重复进行操作,直到pos==0结束查找(因为题目确保一定可以到达末尾,且第一步一定是从0索引出发)

方法二:正向查找最少次数

由于反向查找需要的时间复杂度是O(n^2),所以我们优化一下时间复杂度。

我们维护一个maxdistance,他负责维护选择完最优落点后的可达最远距离,在maxdiatance可以覆盖到的索引处寻找下一个最优跳跃点,最优跳跃点就是落在该位置后可以走的距离比其他位置远。维护一个end他表示当前索引可以到达的最远索引,也就是搜索最优落点的范围,当i==end时,count++,因为此时已经选择完下一个落点,跳越数++

解题:

方法一:反向查找

方法二:正向查找

45. 跳跃游戏 II - 力扣(LeetCode)


http://www.kler.cn/a/561069.html

相关文章:

  • 【Bug经验分享】Postgresql 项目链接不上,JDBC及Datasource可以连接,Navicat也可连接
  • JS宏进阶:数据分析之线性回归
  • 【Jenkins】显示 HTML 标签
  • 什么是事务?并发事务引发的问题?什么是MVCC?
  • 如何使用Spring Boot实现商品的管理系统
  • 嵌入式Modbus协议面试题及参考答案
  • Shell脚本基础:用Bash自动化任务
  • 【行业解决方案篇五】【DeepSeek智慧城市:交通流量预测系统】
  • 软考——WWW与HTTP
  • akka现有的分布式定时任务框架总结
  • leetcode 1656. 设计有序流 简单
  • Nginx解决前端跨域问题
  • LD_PRELOAD 绕过 disable_function 学习
  • JavaWeb-在idea中配置Servlet项目
  • 为什么要将PDF转换为CSV?CSV是Excel吗?
  • HTML+JS+CSS 鼠标上下移动页面(非滚动条)
  • 异步联邦学习的动态隐私保护框架:重构边缘智能的数据安全边界
  • C#中开发OCR应用时,以下是一些推荐的开源库和工具
  • Android 老项目 jcenter 库失效
  • springBoot统一响应类型2.0版本