算法:经典贪心算法--跳一跳[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的…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...

第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...

python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...