当前位置: 首页 > 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的…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...