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

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

在这里插入图片描述

1、题目:

给定一个长度为 n0 索引整数数组 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、题目&#xff1a; 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说&#xff0c;如果你在 nums[i] 处&#xff0c;你可以跳转到任意 nums[i j] 处: 返回到达 nums[n - 1] 的最小跳跃次数。生…...

Vue 和 React 前端框架的比较

一、什么是Vue&#xff1f; Vue[1] 是一个用于构建用户界面的渐进式、可逐步采用的 JavaScript 框架。它由 Evan You[2] 于 2014 年创建&#xff0c;并由一个活跃的开发者社区负责维护。 Vue 设计得非常轻量级、灵活和强大。它建立在一个基于组件的架构上&#xff0c;以组件为…...

【Java】什么是过滤器链(FilterChain )?哪些场景可以使用过滤器链?

文章目录 前言1、创建过滤器2、修改 web.xml3、运行项目并查看结果 前言 在一个 Web 应用程序中可以注册多个 Filter 程序&#xff0c;每个 Filter 程序都可以针对某一个 URL 进行拦截。如果多个 Filter 程序都对同一个 URL 进行拦截&#xff0c;那么这些 Filter 就会组成一个…...

Vue-video-player下载失败(npm i 报错)

Vue-video-player下载失败 最近在做项目时涉及到视频的播放组件&#xff0c;看了一下选择了Vue-video-player这个工具&#xff0c;实际在操作中是遇到许多问题的。 Q1:不支持谷歌 对于 “vue-video-player” 使用时出现 Adobe Flash 不再支持的提示&#xff0c;这是因为 Ado…...

数据在内存中的存储(1)

目录 1、整数在内存中的存储 原码、反码、补码&#xff1a; 2、大小端&#xff1a; 前提须知&#xff1a; 大小端存储方式&#xff1a; 字节的顺序&#xff1a; 概念&#xff1a; 判断机器是大端还是小端&#xff1a; 代码展示&#xff1a; 代码优化1.0&#xff1a; …...

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题 汽车制造涂装-总装缓存调序区调度优化问题 原题再现&#xff1a; 背景介绍   汽车制造厂主要由焊装车间、涂装车间、总装车间构成&#xff0c;每个车间有不同的生产偏好&#xff0c;如&#xff1a;焊装车间由于车身夹具的限制偏向最…...

文本直接生成3D游戏场景、功能,用ChatGPT方式开发游戏!

3D游戏开发平台Hiber3D通过谷歌的PaLM大语言模型&#xff0c;结合自身500多个模板库&#xff0c;以及数百万个成品3D场景进行微调&#xff0c;推出了一个全新游戏开发平台。 该平台在生成式AI加持下&#xff0c;用户可以像使用ChatGPT那样&#xff0c;通过文本问答方式快速创建…...

2023年会展行业研究报告

第一章 行业概况 1.1 定义 会展行业是一个多元化和复杂的领域&#xff0c;涵盖了许多不同的活动和功能。一般来说&#xff0c;会展业是指在一定的区域空间内&#xff0c;许多人聚集在一起形成的定期或者不定期&#xff0c;制度或者非制度&#xff0c;传递和交流信息的群众性的…...

【Redis】如何保证Redis缓存与数据库的一致性?

文章目录 1、四种同步策略2、更新缓存还是删除缓存2.1 更新缓存2.2 删除缓存 3、先操作数据库还是缓存3.1 先删除缓存再更新数据库3.2 先更新数据库再删除缓存 4、延时双删4.1 采用读写分离的架构怎么办&#xff1f; 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 中&#xff0c;对表单做在前置项未填写时禁用后置项交互并提示的效果。 情景 最近有这么个需求&#xff0c;某个业务中&#xff0c;要填写一张表单&#xff0c;其中有这样两项&#xff1a;选择数据连接和选择数据表&#xff0c;数据表是数据连接下所拥有的表。…...

Linux学习之MySQL建表

MySQL查询1 MySQL查询2 表管理 #1. 建库#1&#xff09;库名命名规则仅可以使用数字、字母、下划线、不能纯数字&#xff0c;区分字母大小写&#xff0c;具有唯一性&#xff0c;不可使用MySQL命令或特殊字符#创建数据表时可以查看一下默认的字符集&#xff0c;8.0后创建数据库…...

Redis哨兵集群的介绍及搭建

Redis 是一款开源的、内存中的数据结构存储系统&#xff0c;它可以用作数据库、缓存和消息中间件。然而&#xff0c;作为一个单点服务&#xff0c;Redis 在面临硬件故障或者网络问题时可能会导致服务不可用。为了解决这个问题&#xff0c;Redis 提供了哨兵模式&#xff0c;一个…...

【zookeeper】zookeeper日常运维

本文将分享一些zookeeper在日常使用中一些维护经验。 zookeeper清理快照 脚本或者命令清理 zookeeper长时间运行&#xff0c;快照逐渐增多可能造成服务器磁盘被占满的情况&#xff0c;但我们不能贸然用rm命令删除快照文件&#xff0c;如果直接删完会导致丢失好多数据&#x…...

【工作记录】MQTT介绍、安装部署及springboot集成@20230912

背景 近期公司可能会有物联网设备相关项目内容&#xff0c;提前对用到的mqtt协议做预研和初步使用。 最初接触到mqtt协议应该是早些年的即时通讯吧&#xff0c;现在已经是物联网设备最热门的协议了。 作为记录&#xff0c;也希望能帮助到需要的朋友。 MQTT介绍 《MQTT 协议规…...

Flask 使用 JWT(一)

下面是一些 JWT 的使用场景: 1、 授权:这是 JWT 最常的使用场景。一旦用户登录,后续的每个请求都必须携带 JWT ,允许用户携带 Token 访问所有的路由、服务器和资源。单点登录时目前使用最广泛的一个场景,因为它开销小并且能够轻易的实现跨域访问。 2、信息交换:JWT Token…...

Oracle(1):Oracle简介

1 什么是 ORACLE ORACLE 数据库系统是美国 ORACLE 公司&#xff08;甲骨文&#xff09;提供的以分布式数据库为核心的一组软件产品&#xff0c;是目前最流行的客户/服务器(CLIENT/SERVER)或B/S 体系结构的数据库之一。 ORACLE 通常应用于大型系统的数据库产品。 ORACLE 数据…...

计算机网络篇之IP地址

计算机网络篇之IP地址 文章目录 计算机网络篇之IP地址概括IPv4地址IPv6地址分配总结 概括 IP地址是计算机网络中用于标识和定位设备的一组数字&#xff0c;IP地址分为IPv4和IPv6两种格式 IPv4地址 IPv4地址是32位的二进制数&#xff0c;通常表示为四个用点分隔的十进制数&am…...

webrtc-m79-测试peerconnectionserver的webclient-p2p-demo

1 背景 webrtc的代码中有peerconnectionclient和peerconnectionserver的例子&#xff0c;但是没有对应的web端的例子&#xff0c;这里简单的写了一个测试例子&#xff0c;具体如下&#xff1a; 2 具体操作 2.1 操作流程 2.2 测试效果 使用webclient与peerconnectionclient的…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...