跳跃游戏II-力扣45-java 动态规划
一、题目描述
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4]
输出: 2
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/jump-game-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、运行结果

三、解题思路
大致思路和另一道跳跃游戏的题目相似,可以参考另一篇文章:https://blog.csdn.net/LJH132465/article/details/129148688
有所不同的是,这里是按一段一段来计算的,比如从第一个位置开始可以调到第5个位置,那么,第一个位置到第五个位置就作为第一段,然后计算这几个位置中可以跳到的最远距离,设置last(比如last可能为9),从第一个位置到第五个位置算第一跳,下一跳为从第6个位置到第9个位置,并找到第6个到第9个位置中,所能跳到的最远位置,作为下一跳的最后一个位置,直至到达最后一个位置。
四、AC代码
class Solution {public int jump(int[] nums) {int len = nums.length;if(len < 2) return 0;int ans = 1, last = nums[0], index = 1;while(last < len-1){int curlast = 0; //记录这一段内可以跳到最远的位置for(int i=index; i<=last; i++){ //看当前位置是否可以跳到更远的位置curlast = (i+nums[i]) > curlast ? (i+nums[i]):curlast;}ans++; //当前这一段作为一跳index = last + 1; //下一段开始的位置last = curlast; //下一段的最后一个位置}return ans;}
}
相关文章:
跳跃游戏II-力扣45-java 动态规划
一、题目描述给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i j] 处:0 < j < nums[i] i j < n返回到达 nums[n - …...
【算法】用python代码解决“鬼谷问徒”问题
文章目录题目相关链接算法代码代码可优化的点喜欢这种搞逻辑的题目。据说chatGPT暂时还不会写hhh。水平有限,我自己花了两个小时才实现,不过解决问题的过程还是很快乐的。题目 一天,鬼谷子随意从2-99中选取了两个数。他把这两个数的和告诉了…...
【1】linux命令每日分享——mkdir创建目录
大家好,这里是sdust-vrlab,Linux是一种免费使用和自由传播的类UNIX操作系统,Linux的基本思想有两点:一切都是文件;每个文件都有确定的用途;linux涉及到IT行业的方方面面,在我们日常的学习中&…...
TPM 2.0实例探索1
1. 获取用户名 命令及结果如下所示: $ whoami ph2. 获取设备序列号(串号) 命令及结果如下所示: $ sudo dmidecode | grep "Serial Number" | head -n 1Serial Number: MP260S483. 将用户名和设备序列号放入到一个文…...
buu [BJDCTF2020]signin 1
题目描述: 题目分析: 打开发现是16 进制数(我也不知道我是怎么发现的,先是尝试了md5和rot-n,发现都不行,然后参考大佬的才知道是16进制)使用 在线16进制转字符串 便能得到 flag但我如果不想用线上工具&…...
Storage
WebStorage主要提供了一种机制,可以让浏览器提供一种比cookie更直观的key、value存储方式: localStorage:本地存储,提供的是一种永久性的存储方法,在关闭掉网页重新打开时,存储的内容依然保留;…...
CAS底层原理及ABA问题
一、案例CAS是Java中Unsafe类里面的一个方法,它的全称是叫CompareAndSwap比较并交换的一个意思,它的主要功能是能够去保证在多线程的环境下对于共享变量修改的一个原子性。例如,比如说像这样一个场景,有一个成员变量state…...
华为OD机试真题Python实现【单词反转】真题+解题思路+代码(20222023)
题目 输入一个英文文章片段, 翻转指定区域的单词顺序, 标点符号和普通字母一样处理, 例如输入字符串 I am a developer. [0,3] 则输出 developer. a am I 🔥🔥🔥🔥🔥👉👉👉👉👉👉 华为OD机试(Python)真题目录汇总 输入 使用换行隔开 3 个参数 第一…...
嵌入式linux驱动学习-用cdev代替register_chrdev()
上回说到字符设备驱动程序的注册与销毁register_chrdev()和unregister_chrdev()这是有缺陷的。 嵌入式lnux驱动学习-2.一个驱动程序的流程 现在用另外一个更好的方法代替,我们先来看看register_chrdev()实际上是调用了 __register_chrdev(major, 0, 256, name,…...
技术更新!10个MySQL性能调优技巧
MySQL是世界上使用最广泛的开源数据库,它在业界的受欢迎程度让其他数据库望尘莫及。它是一个关系型数据库管理系统,多年来依然是应用程序的核心。在过去几年里,MySQL有一些重要发展。因此,整理更新10个MySQL性能调优技巧。 模式设…...
ICLR 2023|VLDet:从图像-文本对中学习区域-词语对齐的开放词汇式目标检测
原文链接:https://www.techbeat.net/article-info?id4614&isPreview1 作者:林闯 目标检测任务在AI工业界具有非常广泛的应用,但由于数据获取和标注的昂贵,检测的目标一直被限制在预先设定好的有限类别上。而在学术界…...
如何效率搭建企业流程系统?试试低代码平台吧
编者按:本文介绍了一款可私有化部署的低代码平台,可用于搭建团队流程管理体系,并详细介绍了该平台可实现的流程管理功能。关键词:可视化设计,集成能力,流程审批,流程调试天翎是国内最早从事快速开发平台研发…...
嵌入式开发:C++在深度嵌入式系统中的应用
深度嵌入式系统通常在C语言中实现。为什么会这样?这样的系统是否也能从C中获益?嵌入式开发人员在将广泛、高效的深度嵌入式代码库从C转换为C方面的实践经验的贡献。嵌入式和深度嵌入式系统通常用C而不是C实现。软件开发人员必须放弃C作为强类型系统、模板元编程(TMP)和面向对…...
快鲸scrm发布快递行业私域运营解决方案
现如今,快递行业竞争格局日益激烈,前有“四通一达”等传统快递企业,后有自带互联网基因、绑定电商流量新贵快递企业,如菜鸟、京东等。在这一背景下,很多快递企业开启了增长破局之旅,他们纷纷搭建起私域运营…...
【蓝桥杯集训·每日一题】AcWing 1497. 树的遍历
文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴递归一、题目 1、原题链接 1497. 树的遍历 2、题目描述 一个二叉树,树中每个节点的权值互不相同。 现在给出它的后序遍历和中序遍历,请你输出它的 …...
详解matplotlib的color配置
详解matplotlib的color配置 Matplotlib可识别的color格式 格式举例RGB或RGBA,由[0, 1]之间的浮点数组成的元组,分别代表红色、绿色、蓝色和透明度(0.1, 0.2, 0.5), (0.1, 0.2, 0.5, 0.3不区分大小写的十六进制RGB或RGBA字符串。‘#0f0f0f’, ‘#0f0f0f…...
Oracle删除表数据的三种方式
简介 oracle数据库mysql数据库都是如此 drop命令>truncate命令>delete命令,它们的执行方式、效率和结果各有不同。还是万年的student 学生表 自己可以建个尝试这玩一下。 drop命令 语句: drop table 表名; 理由:1、用drop删除表数据&…...
第 16 章_多版本并发控制
第 16 章_多版本并发控制 1. 什么是MVCC MVCC (Multiversion Concurrency Control),多版本并发控制。顾名思义,MVCC 是通过数据行的多个版本管理来实现数据库的并发控制。这项技术使得在InnoDB的事务隔离级别下执行一致性读操作…...
五种 IO 模型
文章目录操作系统和内存内核空间和用户空间应用程序的内核态和用户态网络 IO 和磁盘 IO简易的网络通信流程阻塞和非阻塞阻塞 IO 模型非阻塞 IO 模型IO 复用模型SelectPollEpoll小结信号驱动 IO 模型异步 IO 模型五种 IO 模型的对比IO 模型里的同步和异步5种 IO 模型分别是&…...
34-Golang中的结构体!!!
Golang中的结构体结构体和结构体变量(实例)的区别和联系结构体变量(实例)在内存中的布局如何声明结构体字段/属性注意事项和细节说明创建结构体实例的四种方式结构体使用细节结构体和结构体变量(实例)的区别和联系 1.结构体是自定义的数据类型,代表一类事物2.结构体…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?
Pod IP 的本质与特性 Pod IP 的定位 纯端点地址:Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址(如 10.244.1.2)无特殊名称:在 Kubernetes 中,它通常被称为 “Pod IP” 或 “容器 IP”生命周期:与 Pod …...
恶补电源:1.电桥
一、元器件的选择 搜索并选择电桥,再multisim中选择FWB,就有各种型号的电桥: 电桥是用来干嘛的呢? 它是一个由四个二极管搭成的“桥梁”形状的电路,用来把交流电(AC)变成直流电(DC)。…...
何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡
何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践,很多人以为AI已经强大到不需要程序员了,其实不是,AI更加需要程序员,普通人…...
数据结构:泰勒展开式:霍纳法则(Horner‘s Rule)
目录 🔍 若用递归计算每一项,会发生什么? Horners Rule(霍纳法则) 第一步:我们从最原始的泰勒公式出发 第二步:从形式上重新观察展开式 🌟 第三步:引出霍纳法则&…...
Yii2项目自动向GitLab上报Bug
Yii2 项目自动上报Bug 原理 yii2在程序报错时, 会执行指定action, 通过重写ErrorAction, 实现Bug自动提交至GitLab的issue 步骤 配置SiteController中的actions方法 public function actions(){return [error > [class > app\helpers\web\ErrorAction,],];}重写Error…...
