算法:经典贪心算法--跳一跳[2]

1、题目:
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
2、分析特点:
- 这道题是典型的贪心算法,通过局部最优解得到全局最优解。
反向思维解决: 每次都找最左位置-最后一个位置,距离最远,即最大概率最小跳跃次数。- 【解题口:寻找最左位置–寻找的次数,即最小跳跃次数】
我们的目标是到达数组的最后一个位置,因此我们可以考虑最后一步跳跃前所在的位置,该位置通过跳跃能够到达最后一个位置。
如果有多个位置通过跳跃都能够到达最后一个位置,那么我们应该如何进行选择呢?直观上来看,我们可以「贪心」地选择距离最后一个位置最远的那个位置,也就是对应下标最小的那个位置。因此,我们可以从左到右遍历数组,选择第一个满足要求的位置。
找到最后一步跳跃前所在的位置之后,我们继续贪心地寻找倒数第二步跳跃前所在的位置,以此类推,直到找到数组的开始位置。
3、代码:
class Solution {public int jump(int[] nums) {int position = nums.length - 1;int steps = 0;while (position > 0) {for (int i = 0; i < position; i++) {if (i + nums[i] >= position) {position = i;steps++;break;}}}return steps;}
}
4、复杂度分析:
- 时间复杂度:O(n2),其中 nnn 是数组长度。有两层嵌套循环,在最坏的情况下,例如数组中的所有元素都是 1,position 需要遍历数组中的每个位置,对于 position 的每个值都有一次循环。
- 空间复杂度:O(1)。
5、总结:
- 这道题是典型的贪心算法,通过局部最优解得到全局最优解。
反向思维解决: 每次都找最左位置-最后一个位置,距离最远,即最大概率最小跳跃次数。- 【解题口:寻找最左位置–寻找的次数,即最小跳跃次数】
我们的目标是到达数组的最后一个位置,因此我们可以考虑最后一步跳跃前所在的位置,该位置通过跳跃能够到达最后一个位置。
如果有多个位置通过跳跃都能够到达最后一个位置,那么我们应该如何进行选择呢?直观上来看,我们可以「贪心」地选择距离最后一个位置最远的那个位置,也就是对应下标最小的那个位置。因此,我们可以从左到右遍历数组,选择第一个满足要求的位置。
找到最后一步跳跃前所在的位置之后,我们继续贪心地寻找倒数第二步跳跃前所在的位置,以此类推,直到找到数组的开始位置。
如果本文对你有帮助的话记得给一乐点个赞哦,感谢!
相关文章:
算法:经典贪心算法--跳一跳[2]
1、题目: 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i j] 处: 返回到达 nums[n - 1] 的最小跳跃次数。生…...
Vue 和 React 前端框架的比较
一、什么是Vue? Vue[1] 是一个用于构建用户界面的渐进式、可逐步采用的 JavaScript 框架。它由 Evan You[2] 于 2014 年创建,并由一个活跃的开发者社区负责维护。 Vue 设计得非常轻量级、灵活和强大。它建立在一个基于组件的架构上,以组件为…...
【Java】什么是过滤器链(FilterChain )?哪些场景可以使用过滤器链?
文章目录 前言1、创建过滤器2、修改 web.xml3、运行项目并查看结果 前言 在一个 Web 应用程序中可以注册多个 Filter 程序,每个 Filter 程序都可以针对某一个 URL 进行拦截。如果多个 Filter 程序都对同一个 URL 进行拦截,那么这些 Filter 就会组成一个…...
Vue-video-player下载失败(npm i 报错)
Vue-video-player下载失败 最近在做项目时涉及到视频的播放组件,看了一下选择了Vue-video-player这个工具,实际在操作中是遇到许多问题的。 Q1:不支持谷歌 对于 “vue-video-player” 使用时出现 Adobe Flash 不再支持的提示,这是因为 Ado…...
数据在内存中的存储(1)
目录 1、整数在内存中的存储 原码、反码、补码: 2、大小端: 前提须知: 大小端存储方式: 字节的顺序: 概念: 判断机器是大端还是小端: 代码展示: 代码优化1.0: …...
LINUX常用命令练习
显示LINUX系统当前的日期和时间。 date以 yyyy/mm/dd的格式显示系统当前的日期 date %Y/%m/%d以 yyyy-mm-dd的格式显示系统当前的日期 date %Y-%m-%d查看在线用户信息 who显示当前月份的日历 cal显示2023年整年的日历 cal 2023显示2023年9月的日历 cal 9 2023查看LINUX系统的Sh…...
2022年全国研究生数学建模竞赛华为杯C题汽车制造涂装-总装缓存调序区调度优化问题求解全过程文档及程序
2022年全国研究生数学建模竞赛华为杯 C题 汽车制造涂装-总装缓存调序区调度优化问题 原题再现: 背景介绍 汽车制造厂主要由焊装车间、涂装车间、总装车间构成,每个车间有不同的生产偏好,如:焊装车间由于车身夹具的限制偏向最…...
文本直接生成3D游戏场景、功能,用ChatGPT方式开发游戏!
3D游戏开发平台Hiber3D通过谷歌的PaLM大语言模型,结合自身500多个模板库,以及数百万个成品3D场景进行微调,推出了一个全新游戏开发平台。 该平台在生成式AI加持下,用户可以像使用ChatGPT那样,通过文本问答方式快速创建…...
2023年会展行业研究报告
第一章 行业概况 1.1 定义 会展行业是一个多元化和复杂的领域,涵盖了许多不同的活动和功能。一般来说,会展业是指在一定的区域空间内,许多人聚集在一起形成的定期或者不定期,制度或者非制度,传递和交流信息的群众性的…...
【Redis】如何保证Redis缓存与数据库的一致性?
文章目录 1、四种同步策略2、更新缓存还是删除缓存2.1 更新缓存2.2 删除缓存 3、先操作数据库还是缓存3.1 先删除缓存再更新数据库3.2 先更新数据库再删除缓存 4、延时双删4.1 采用读写分离的架构怎么办? 5、利用消息队列进行删除的补偿 1、四种同步策略 想要保证缓…...
MATLAB中ischange函数用法
目录 语法 说明 示例 均值的变化 线性区的变化 矩阵数据 ischange函数的功能是查找数据中的突然变化。 语法 TF ischange(A) TF ischange(A,method) TF ischange(___,dim) TF ischange(___,Name,Value) [TF,S1] ischange(___) [TF,S1,S2] ischange(___) 说明 …...
【React + Ant Design】表单如何在前置项未填写时禁止后置项交互并提示
在 react antd 中,对表单做在前置项未填写时禁用后置项交互并提示的效果。 情景 最近有这么个需求,某个业务中,要填写一张表单,其中有这样两项:选择数据连接和选择数据表,数据表是数据连接下所拥有的表。…...
Linux学习之MySQL建表
MySQL查询1 MySQL查询2 表管理 #1. 建库#1)库名命名规则仅可以使用数字、字母、下划线、不能纯数字,区分字母大小写,具有唯一性,不可使用MySQL命令或特殊字符#创建数据表时可以查看一下默认的字符集,8.0后创建数据库…...
Redis哨兵集群的介绍及搭建
Redis 是一款开源的、内存中的数据结构存储系统,它可以用作数据库、缓存和消息中间件。然而,作为一个单点服务,Redis 在面临硬件故障或者网络问题时可能会导致服务不可用。为了解决这个问题,Redis 提供了哨兵模式,一个…...
【zookeeper】zookeeper日常运维
本文将分享一些zookeeper在日常使用中一些维护经验。 zookeeper清理快照 脚本或者命令清理 zookeeper长时间运行,快照逐渐增多可能造成服务器磁盘被占满的情况,但我们不能贸然用rm命令删除快照文件,如果直接删完会导致丢失好多数据&#x…...
【工作记录】MQTT介绍、安装部署及springboot集成@20230912
背景 近期公司可能会有物联网设备相关项目内容,提前对用到的mqtt协议做预研和初步使用。 最初接触到mqtt协议应该是早些年的即时通讯吧,现在已经是物联网设备最热门的协议了。 作为记录,也希望能帮助到需要的朋友。 MQTT介绍 《MQTT 协议规…...
Flask 使用 JWT(一)
下面是一些 JWT 的使用场景: 1、 授权:这是 JWT 最常的使用场景。一旦用户登录,后续的每个请求都必须携带 JWT ,允许用户携带 Token 访问所有的路由、服务器和资源。单点登录时目前使用最广泛的一个场景,因为它开销小并且能够轻易的实现跨域访问。 2、信息交换:JWT Token…...
Oracle(1):Oracle简介
1 什么是 ORACLE ORACLE 数据库系统是美国 ORACLE 公司(甲骨文)提供的以分布式数据库为核心的一组软件产品,是目前最流行的客户/服务器(CLIENT/SERVER)或B/S 体系结构的数据库之一。 ORACLE 通常应用于大型系统的数据库产品。 ORACLE 数据…...
计算机网络篇之IP地址
计算机网络篇之IP地址 文章目录 计算机网络篇之IP地址概括IPv4地址IPv6地址分配总结 概括 IP地址是计算机网络中用于标识和定位设备的一组数字,IP地址分为IPv4和IPv6两种格式 IPv4地址 IPv4地址是32位的二进制数,通常表示为四个用点分隔的十进制数&am…...
webrtc-m79-测试peerconnectionserver的webclient-p2p-demo
1 背景 webrtc的代码中有peerconnectionclient和peerconnectionserver的例子,但是没有对应的web端的例子,这里简单的写了一个测试例子,具体如下: 2 具体操作 2.1 操作流程 2.2 测试效果 使用webclient与peerconnectionclient的…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...
9-Oracle 23 ai Vector Search 特性 知识准备
很多小伙伴是不是参加了 免费认证课程(限时至2025/5/15) Oracle AI Vector Search 1Z0-184-25考试,都顺利拿到certified了没。 各行各业的AI 大模型的到来,传统的数据库中的SQL还能不能打,结构化和非结构的话数据如何和…...
数据结构:递归的种类(Types of Recursion)
目录 尾递归(Tail Recursion) 什么是 Loop(循环)? 复杂度分析 头递归(Head Recursion) 树形递归(Tree Recursion) 线性递归(Linear Recursion)…...
PH热榜 | 2025-06-08
1. Thiings 标语:一套超过1900个免费AI生成的3D图标集合 介绍:Thiings是一个不断扩展的免费AI生成3D图标库,目前已有超过1900个图标。你可以按照主题浏览,生成自己的图标,或者下载整个图标集。所有图标都可以在个人或…...
