LeetCode第45题解析

2023-11-13

给定一个非负整数数组,你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。

说明:

假设你总是可以到达数组的最后一个位置。

解题思路:

如果我们「贪心」地进行正向查找,每次找到可到达的最远位置,就可以在线性时间内得到最少的跳跃次数。

例如,对于数组 [2,3,1,2,4,2,3],初始位置是下标 0,从下标 0 出发,最远可到达下标 2。下标 0 可到达的位置中,下标 1 的值是 3,从下标 1 出发可以达到更远的位置,因此第一步到达下标 1。

从下标 1 出发,最远可到达下标 4。下标 1 可到达的位置中,下标 4 的值是 4 ,从下标 4 出发可以达到更远的位置,因此第二步到达下标 4。

fig1

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

LeetCode第45题解析 的相关文章

  • VM 中ubuntu下----Eclipse ctrl+s 显示update conflict的问题

    VM 中ubuntu下 Eclipse ctrl s 显示update conflict的问题 VMworkstation中使用共享主机的方式 在eclipse下编辑windows下的文件 ctrl s时 显示update conflict
  • WPF 禁用TextBox的触摸后自动弹出虚拟键盘

    原文 WPF 禁用TextBox的触摸后自动弹出虚拟键盘 前言 问题 如下截图 TextBox 在触摸点击后 会自动弹出windows的虚拟键盘 如何 禁用键盘的自动弹出 调用虚拟键盘 通过调用TapTip exe或者osk exe 主动弹
  • 剖析vue常见问题(三)之vue中key的作用和原理

    背景 说到vue中key的作用 大家都知道它可以唯一的确定一个dom元素 从而执行diff算法时更加高效 但是想更加详细的知道具体原因 我们还是需要从源码入手 详见源码 src core vdom patch js中的updateChild
  • 华为od机试 Python 【计算最少步数】

    题目 小明计划在周末去爬山 他有一份包含山峰高度的地图 其中 0 代表平地 而 1 到 9 表示不同的山峰高度 小明可以向上 下 左或右移动一步 但是 由于他不想爬得太累 他决定只在高度差不超过 k 的地方移动 现在他站在地图的左上角 你能

随机推荐

  • ES安全认证机制X-pack的安装及使用

    1 给ES Kibana安装x pack bin elasticsearch plugin install x pack bin kibana plugin install x pack 2 修改密码 注意 这个只能修改一次密码 同一个集群
  • 如何在Android应用中使用百度地图api

    本篇通过一个简单的示例一步步介绍如何在Android应用中使用百度地图api 1 下载百度地图移动版API Android 开发包 要在Android应用中使用百度地图API 就需要在工程中引用百度地图API开发包 这个开发包包含两个文件
  • 互联网行业为什么能吸引越来越多的年轻人?尤其是程序员……

    上周发的关于全国程序员4月的薪资依旧稳步上涨的推文 着实让羡慕了一把 虽然互联网大厂屡次传来裁员的消息 但依然阻挡不了年轻人向互联网行业涌入的决心 那么 问题来了 互联网行业为什么能吸引越来越多的年轻人 弹性上班 很多互联网公司都会有弹性上
  • linux xargs命令使用

    linux xargs命令使用 基本的命令是 command xargs I 选项 格式 xargs I rep str comand rep srt 其中rep str 为代替传递给xargs参数 可以使 等符号 其主要作用是当xargs
  • jquery获取一组radio被选中项的值

    相关文章 EXT使用中IE下的DOCTYPE问题 DOJO的菜单老出问题 IE6 IE7和Firefox对Div处理的差异 推荐圈子 EXT 更多相关推荐
  • 在Vi里面实现字符串的批量替换

    在Vi里面实现字符串的批量替换 在Vi里面实现字符串的批量替换 a 文件内全部替换 s abc def g 用def替换文件中所有的abc 例如把一个文本文件里面的 linuxidc com 全部替换成 linuxidc net s lin
  • 训练DPT:由测试test到训练train图像的一个epochs的optimize.zero_grad() loss.backward() optimizer.step()

    不知道大家有没有这样的感受 很多研究型论文通常会给出他们的test py文件 但是其train py文件往往是空白的 这时候感觉文章的test确实很nice 就想去探究其更原始 最优参数 训练出的参数过程 那么这里就不得不开始研究如何从te
  • ssm整合无法注入dao层

    spring整合mybatis 在部署项目时 一直报错 dao无法注入ioc容器 Error creating bean with name accountController Unsatisfied dependency expresse
  • 听说CentOS 8 已经成绝版了 ?难道就没有后续了么?很烦!

    一 CentOS 8 已是绝版 CentOS Stream 才是未来 CentOS 官方发文称 CentOS Stream 才是 CentOS 项目的未来 在接下来的一年里 将逐步把开发工作的重心从 CentOS Linux 往 CentO
  • Linux设置用户的密码有效期

    使用命令chage加参数可以查看 更改用户密码的有效期 1 查看用户密码有效期 chage l username 如下是永不会过期的类型 以下是90天有效期的类型 2 修改密码到期时间 通过参数 M 设置账户密码的到期时间 语法 chage
  • Lua里实现将table转成字符串(序列化)和将字符串转换回table(反序列化)

    file name table序列化和反序列化的问题 lua author Clark 陈泽丹 created 2011 12 22 备注 支持table的递归结构 但数据类型不支持function属性 因为function只是记录地址 在
  • 《GPU的革命》文章整理

    整理几年前写的文章 或许对初学CUDA编程的朋友有帮助 CUDA 线程执行模型分析 一 招兵 GPU的革命 CUDA 线程执行模型分析 二 大军未动粮草先行 GPU的革命 CUDA硬件实现分析 一 安营扎寨 GPU的革命 CUDA硬件实现分
  • 16个自动化测试面试问题与解答

    1 什么是自动化测试 自动化测试是一种使用自动化工具编写和执行测试人员测试脚本和案例的技术 自动化测试的主要目标是减少手动运行的测试用例数量 而不是完全取消手动测试 2 什么时候自动化测试 在以下情况下首选自动化 重复性任务 烟雾和理智测试
  • vue3项目修改浏览器的项目icon小图标

    修改vue3项目的浏览器的图标 vue2修改图标
  • AD每次更新PCB元器件位置会变动

    用AD画板 在重新更新元器件标识注视后 更新PCB后会出现某些器件移到了外面 把它摆放好以后 如果又对原理图中进行了改动 在更新PCB之后 刚才摆放好的元器件就又移到外面 另外 其它一些情况也会出现更新PCB位置变动的情况 下面是解决办法
  • 【matplotlib】可视化解决方案——如何向图表中添加数据表

    概述 虽然 matplotlib 主要用途是绘图 但是他还是可以在绘图时帮助我们做一些其他事务 比如在图表旁边放置一个整齐的数据表格 我们必须明白为数据绘制可视化图形主主要是是为了解释那些不能理解的数据 将一些来自数据整体集合的总结性或者突
  • Pytest框架:测试用例setup和teardown

    背景 假如我们进入多个模块前 每个模块有一个用例 都要打开浏览器登录 执行完毕后 需要退出再关闭浏览器 即每次运行前都要执行登录打开 退出关闭两个大量重复的操作 这些我们都可以用前置后置初始化环境去实现 怎么去实现 就是下面要介绍的 用例设
  • 【上新】手工制作马赛克瓷砖,为 Gotchiverse 添色彩!

    你无需成为艺术家即可帮助一起绘制 Gotchiverse 现在 每个人都可以用马赛克瓷砖让他们的创造力得到发挥 让我们在 Gotchiverse 中涂抹色彩吧 最新和最伟大的美学 NFT 已准备好冲击 Gotchiverse 了 介绍一下马
  • 显示this application has requested the runtime to terminate it in an unusual way.问题的简单分析

    运行程序是出现了this application has requested the runtime to terminate it in an unusual way 的异常报告 有些Win7的操作系统可能会出现此类问题 一般是软件运行时
  • LeetCode第45题解析

    给定一个非负整数数组 你最初位于数组的第一个位置 数组中的每个元素代表你在该位置可以跳跃的最大长度 你的目标是使用最少的跳跃次数到达数组的最后一个位置 示例 输入 2 3 1 1 4 输出 2 解释 跳到最后一个位置的最小跳跃数是 2 从下