【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^40 <= nums[i] <= 1000- 保证你能到达
nums[n - 1]。
解题思路
算法描述
此代码解决了在给定的整数数组中计算到达数组末尾所需的最小跳跃次数的问题。
将这个遍历过程分为step轮,每一轮将一些可以到达的点搜罗进来,并且记录可以到达的最远的点 next_max_reach。
在每轮结束的时候更新max_reach。
每走一轮相当于走一步。
算法的关键步骤如下:
-
初始化变量:
start: 表示当前步骤中考虑跳跃的起始索引。max_reach: 表示当前步骤能够到达的最远索引。next_max_reach: 表示下一步能够到达的最远索引。step: 用于记录到达数组末尾所需的步数。
-
遍历数组:
- 使用一个
while循环,条件为max_reach小于数组的最后一个索引(nums.size() - 1)。 - 在每一步中,增加
step的计数,并更新next_max_reach。 - 通过内部的
for循环,遍历从start到max_reach之间的所有索引。 - 在每次迭代中,计算并更新可以到达的最远索引
next_max_reach。 - 循环结束后,更新
start和max_reach为下一轮迭代的值。
- 使用一个
-
返回结果:
- 当
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 库,它提供了一个高级 API 来通过 DevTools 协议控制 Chromium 或 Chrome。 二、使用 1、安装nodejs最新版 2、安装puppeteer-core npm install puppeteer-core 3、编写main.js const puppeteer require(puppeteer-core);(as…...
vue3按钮点击频率控制
现有一个按钮,如下图 点击时 再次点击 刷新窗口再次点击 刷新窗口依然可以实现点击频率控制。 代码实现: <template><!--<el-config-provider :locale"locale"><router-view/></el-config-provider>--><el…...
(一)Matlab数值计算基础
目录 1.2Matlab中的数据类型 1.2Matlab中的数据类型 逻辑型 逻辑型变量值为1或0字符型 MATLAB的字符型输入使用单引号括起来,字符串存储为字符数组,每个元素占一个ASCII字符数值型 数值型分为整型(int)、单精度浮点型࿰…...
《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(思维) 题意: 有一个序列 A a 1 , a 2 , . . . , a n k A a_1, a_2, ..., a_{n k} Aa1,a2,...,ank,且这个序列满足 ∏ i 1 n k a i 2023 \prod\limits_{i 1}^{n k}a_i 2023 i1∏nkai2023,而这个序列中的 k k k个…...
【蓝桥杯】比赛大纲整理
枚举[1-3] 排序 (1)冒泡排序[2] (2)选择排序[3] (3)插入排序[3] 搜索(bfs, dfs)[1-5] 贪心[1-5] 模拟[1-3] 二分[2-5] DP(普通一维问题)[3-5] 高精度[1-5] 数据结构 (1)栈[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我的编程之旅》
一、背景 自从踏入编程的世界,我就像乘坐了一辆无法停下的列车,穿行在数据的丛林中,寻找解决问题的答案。编程不仅是我的职业,更是我表达自我、解决问题的工具。在这篇文章中,我将分享一段令人印象深刻的实战经历&…...
C++ 二进制图片的读取和blob插入mysql_stmt_init—新年第一课
关于二进制图片的读取和BLOB插入一共包含五步 第一步:初始化 MYSQL_STMT* stmt mysql_stmt_init(&mysql); 第二步:预处理sql语句 mysql_stmt_prepare(stmt,sql,sqllen); 第三步:绑定字段 mysql_stmt_bind_param(stmt,bind); 第四…...
向爬虫而生---Redis 基石篇2 <拓展Hash>
前言: 延续上一篇向爬虫而生---Redis 基石篇 <拓展str>-CSDN博客 这个章节拓展一下hash的玩法,主要是要挖一挖 ,啥时候用它最合适;让他并不是一无是处.. 正文: 哈希(Hash)数据结构是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全景影像 也只需要安装前面 左右三个摄像头 后面的那个还是正常用的,不过不一样的是 升级完成之后会有多了个功能 那就是新款透明底盘,星骏汇小许Xjh15863 左右两边只需要更换后…...
SQL 在已有表中修改列名的方法
文章目录 1. MySQL2. SQL Server3. Oracle / PostgreSQL Question: 假设有一张表 StudentInfo,表中有一个列名是 Student_Name ,想要把这个列名改成 StudentName 应该如何操作? 建表语句如下: --建表 if object_id(S…...
QT----Visual stdio翻金币案例,附源码
历经一个月,各种事情磕磕绊绊,终于结束了,自己还是太菜了 案例的文档写的教程已经很详细,这边主要是记录一些问题 github代码 gitee代码 1、图片无法加载 一开始加载首页图片和标题出不来,结果是paintEvent重写的字打…...
总结:浏览器解析html与执行JS之生命周期详解
总结:浏览器解析html与执行JS之生命周期详解 一浏览器解析html的生命周期:1.请求HTML文档:2接收响应:3构建DOM树:4加载外部资源:5DOMContentLoaded事件:6样式计算与布局:7绘制与渲染…...
aspose通过开始和结束位置关键词截取word另存为新文件
关键词匹配实体类: Data EqualsAndHashCode(callSuper false) public class TextConfig implements Serializable {private static final long serialVersionUID 1L;/*** 开始关键词,多个逗号分隔*/private String textStart ;/*** 结束关键词&#x…...
深入解析美颜SDK:绿幕抠图功能的算法原理
当下,美颜SDK绿幕抠图功能成为许多应用中不可或缺的一环。本文将深入解析美颜SDK中绿幕抠图功能的算法原理,揭示其背后的技术奥秘。 一、什么是美颜SDK绿幕抠图? 美颜SDK的绿幕抠图功能是一种通过计算机视觉技术,将视频或图像中…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命
在华东塑料包装行业面临限塑令深度调整的背景下,江苏艾立泰以一场跨国资源接力的创新实践,重新定义了绿色供应链的边界。 跨国回收网络:废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点,将海外废弃包装箱通过标准…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
