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

【LeetCode 面试经典150题】45. Jump Game II 跳跃游戏II

45. Jump Game II

题目大意

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

0 <= j <= nums[i] and
i + j < n
Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

中文释义

给定一个从0开始索引的整数数组 nums,其长度为 n。你最初位于 nums[0]

数组中的每个元素 nums[i] 表示从索引 i 开始向前跳跃的最大长度。换句话说,如果你在 nums[i],你可以跳到任何 nums[i + j],其中:

0 <= j <= nums[i] 且
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。测试用例保证你能到达 nums[n - 1]

Example

Example 1:

  • Input: nums = [2,3,1,1,4]
  • Output: 2
  • Explanation: 到达最后一个索引的最小跳跃次数是2。从索引0跳1步到索引1,然后跳3步到最后一个索引。

Example 2:

  • Input: nums = [2,3,0,1,4]
  • Output: 2

Constraints

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 1000
  • 保证你能到达 nums[n - 1]

解题思路

算法描述

此代码解决了在给定的整数数组中计算到达数组末尾所需的最小跳跃次数的问题。

将这个遍历过程分为step轮,每一轮将一些可以到达的点搜罗进来,并且记录可以到达的最远的点 next_max_reach
在每轮结束的时候更新max_reach
每走一轮相当于走一步。

算法的关键步骤如下:

  1. 初始化变量:

    • start: 表示当前步骤中考虑跳跃的起始索引。
    • max_reach: 表示当前步骤能够到达的最远索引。
    • next_max_reach: 表示下一步能够到达的最远索引。
    • step: 用于记录到达数组末尾所需的步数。
  2. 遍历数组:

    • 使用一个 while 循环,条件为 max_reach 小于数组的最后一个索引(nums.size() - 1)。
    • 在每一步中,增加 step 的计数,并更新 next_max_reach
    • 通过内部的 for 循环,遍历从 startmax_reach 之间的所有索引。
    • 在每次迭代中,计算并更新可以到达的最远索引 next_max_reach
    • 循环结束后,更新 startmax_reach 为下一轮迭代的值。
  3. 返回结果:

    • max_reach 大于或等于数组的最后一个索引时,循环结束,返回 step 作为到达数组末尾所需的最小步数。

代码示例

class Solution {
public:int jump(vector<int>& nums) {int start = 0, max_reach = 0, next_max_reach = 0, step = 0;while (max_reach < nums.size() - 1) {step++;for (int i = start; i <= max_reach; i++) {next_max_reach = max(next_max_reach, i + nums[i]);}start = max_reach + 1;max_reach = next_max_reach;}return step;}
};

相关文章:

【LeetCode 面试经典150题】45. Jump Game II 跳跃游戏II

45. Jump Game II 题目大意 You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], yo…...

RustDesk连接客户端提示key不匹配 Key Mismatch无法连接(已解决)

环境: RustDesk1.1.9 服务端docker部署 问题描述: RustDesk连接客户端提示key不匹配 Key Mismatch无法连接 解决方案: 1.docker部署RustDesk服务检查配置 networks:rustdesk-net:external: falsevolumes:hbbr:hbbs:services:hbbs:container_name: rustdesk-hbbsport…...

puppeteer入门指南

一、简介 Puppeteer 是一个 Node 库&#xff0c;它提供了一个高级 API 来通过 DevTools 协议控制 Chromium 或 Chrome。 二、使用 1、安装nodejs最新版 2、安装puppeteer-core npm install puppeteer-core 3、编写main.js const puppeteer require(puppeteer-core);(as…...

vue3按钮点击频率控制

现有一个按钮&#xff0c;如下图 点击时 再次点击 刷新窗口再次点击 刷新窗口依然可以实现点击频率控制。 代码实现&#xff1a; <template><!--<el-config-provider :locale"locale"><router-view/></el-config-provider>--><el…...

(一)Matlab数值计算基础

目录 1.2Matlab中的数据类型 1.2Matlab中的数据类型 逻辑型 逻辑型变量值为1或0字符型 MATLAB的字符型输入使用单引号括起来&#xff0c;字符串存储为字符数组&#xff0c;每个元素占一个ASCII字符数值型 数值型分为整型&#xff08;int&#xff09;、单精度浮点型&#xff0…...

《MySQL系列-InnoDB引擎02》InnoDB存储引擎介绍

文章目录 第二章 InnoDB存储引擎1 InnoDB存储引擎概述2 InnoDB存储引擎的版本3 InnoDB体系架构3.1 后台线程3.2 内存 4 Checkpoint技术5 Master Thread 工作方式5.1 InnoDB 1.0.x版本之前的Master Thread5.2 InnoDB 1.2.x版本之前的Master Thread5.3 InnoDB 1.2.x版本的Master …...

单片机大小端模式

单片机大小端模式 参考链接 单片机干货-什么是大小端_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1Ju4y1M7Tx/?spm_id_from333.337.search-card.all.click&vd_sourcee821a225c7ba4a7b85e5aa6d013ac92e 特此记录 anlog 2024年1月2日...

Codeforces Good Bye 2023 A~E

A.2023(思维) 题意&#xff1a; 有一个序列 A a 1 , a 2 , . . . , a n k A a_1, a_2, ..., a_{n k} Aa1​,a2​,...,ank​&#xff0c;且这个序列满足 ∏ i 1 n k a i 2023 \prod\limits_{i 1}^{n k}a_i 2023 i1∏nk​ai​2023&#xff0c;而这个序列中的 k k k个…...

【蓝桥杯】比赛大纲整理

枚举[1-3] 排序 &#xff08;1&#xff09;冒泡排序[2] &#xff08;2&#xff09;选择排序[3] &#xff08;3&#xff09;插入排序[3] 搜索(bfs, dfs)[1-5] 贪心[1-5] 模拟[1-3] 二分[2-5] DP(普通一维问题)[3-5] 高精度[1-5] 数据结构 &#xff08;1&#xff09;栈[2-4]&…...

探索 CodeWave低代码技术的魅力与应用

目录 前言1 低代码平台2 CodeWave简介3 CodeWave 的独特之处3.1 高保真还原交互视觉需求3.2 擅长复杂应用开发3.3 支持应用导出&独立部署3.4 金融级安全要求3.5 可集成性高3.6 可拓展性强 4 平台架构和核心功能4.1 数据模型设计4.2 页面设计4.3 逻辑设计4.4 流程设计4.5 接…...

《2023我的编程之旅》

一、背景 自从踏入编程的世界&#xff0c;我就像乘坐了一辆无法停下的列车&#xff0c;穿行在数据的丛林中&#xff0c;寻找解决问题的答案。编程不仅是我的职业&#xff0c;更是我表达自我、解决问题的工具。在这篇文章中&#xff0c;我将分享一段令人印象深刻的实战经历&…...

C++ 二进制图片的读取和blob插入mysql_stmt_init—新年第一课

关于二进制图片的读取和BLOB插入一共包含五步 第一步&#xff1a;初始化 MYSQL_STMT* stmt mysql_stmt_init(&mysql); 第二步&#xff1a;预处理sql语句 mysql_stmt_prepare(stmt,sql,sqllen); 第三步&#xff1a;绑定字段 mysql_stmt_bind_param(stmt,bind); 第四…...

向爬虫而生---Redis 基石篇2 <拓展Hash>

前言: 延续上一篇向爬虫而生---Redis 基石篇 &#xff1c;拓展str&#xff1e;-CSDN博客 这个章节拓展一下hash的玩法,主要是要挖一挖 ,啥时候用它最合适;让他并不是一无是处.. 正文: 哈希&#xff08;Hash&#xff09;数据结构是Redis中的一种常用的数据类型。它是一个键值…...

【论文精读】A Survey on Large Language Model based Autonomous Agents

A Survey on Large Language Model based Autonomous Agents 前言Abstract1 Introduction2 LLM-based Autonomous Agent Construction2.1 Agent Architecture Design2.1.1 Profiling Module2.1.2 Memory ModuleMemory StructuresMemory FormatsMemory Operations 2.1.3 Plannin…...

23款奔驰GLC260L升级原厂540全景影像 高清环绕的视野

嗨 今天给大家介绍一台奔驰GLC260L升级原厂360全景影像 新款GLC升级原厂360全景影像 也只需要安装前面 左右三个摄像头 后面的那个还是正常用的&#xff0c;不过不一样的是 升级完成之后会有多了个功能 那就是新款透明底盘&#xff0c;星骏汇小许Xjh15863 左右两边只需要更换后…...

SQL 在已有表中修改列名的方法

文章目录 1. MySQL2. SQL Server3. Oracle / PostgreSQL Question&#xff1a; 假设有一张表 StudentInfo&#xff0c;表中有一个列名是 Student_Name &#xff0c;想要把这个列名改成 StudentName 应该如何操作&#xff1f; 建表语句如下&#xff1a; --建表 if object_id(S…...

QT----Visual stdio翻金币案例,附源码

历经一个月&#xff0c;各种事情磕磕绊绊&#xff0c;终于结束了&#xff0c;自己还是太菜了 案例的文档写的教程已经很详细&#xff0c;这边主要是记录一些问题 github代码 gitee代码 1、图片无法加载 一开始加载首页图片和标题出不来&#xff0c;结果是paintEvent重写的字打…...

总结:浏览器解析html与执行JS之生命周期详解

总结&#xff1a;浏览器解析html与执行JS之生命周期详解 一浏览器解析html的生命周期&#xff1a;1.请求HTML文档&#xff1a;2接收响应&#xff1a;3构建DOM树&#xff1a;4加载外部资源&#xff1a;5DOMContentLoaded事件&#xff1a;6样式计算与布局&#xff1a;7绘制与渲染…...

aspose通过开始和结束位置关键词截取word另存为新文件

关键词匹配实体类&#xff1a; Data EqualsAndHashCode(callSuper false) public class TextConfig implements Serializable {private static final long serialVersionUID 1L;/*** 开始关键词&#xff0c;多个逗号分隔*/private String textStart ;/*** 结束关键词&#x…...

深入解析美颜SDK:绿幕抠图功能的算法原理

当下&#xff0c;美颜SDK绿幕抠图功能成为许多应用中不可或缺的一环。本文将深入解析美颜SDK中绿幕抠图功能的算法原理&#xff0c;揭示其背后的技术奥秘。 一、什么是美颜SDK绿幕抠图&#xff1f; 美颜SDK的绿幕抠图功能是一种通过计算机视觉技术&#xff0c;将视频或图像中…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式

简介 在我的 QT/C 开发工作中&#xff0c;合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式&#xff1a;工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...