算法:经典贪心算法--跳一跳[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的…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...

docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...

毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...