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

【Leetcode 每日一题 - 扩展】45. 跳跃游戏 II

news 来源：原创 2025/6/18 3:43:41

问题背景

给定一个长度为 $n$ 的 $0$ 索引整数数组 $n u m s$ 。初始位置为 $n u m s [0]$ 。
每个元素 $n u m s [i]$ 表示从索引 $i$ 向前跳转的最大长度。换句话说，如果你在 $n u m s [i]$ 处，你可以跳转到任意 $n u m s [i + j]$ 处：

$\le j \le nums[i]$
$\lt n$

返回到达 $n u m s [n - 1]$ 的最小跳跃次数。生成的测试用例可以到达 $n u m s [n - 1]$ 。

数据约束

$\le nums.length \le 10 ^ 4$
$\le nums[i] \le 1000$
题目保证可以到达 $n u m s [n - 1]$

解题过程

经典跳跃问题，可以用造桥场景来理解。
题目描述不是很好懂，其实是在每个位置 $i$ 上，可以在 $[1, n u m s [i]]$ 中选择一个距离 $j$ 并从当前位置移动到 $i + j$ 这个位置上。
解决方案是一个比较明显的贪心算法，每次选择能够到达的最远位置来造桥，能尽可能地减少操作次数。
注意要到达的位置是 $n - 1$ ，所以循环应该在 $i < n - 1$ 处结束。通过样例的输出可能会想到在结果上进行修正，但这样是不对的，因为最后造额外的桥是有条件的。
由于题目保证了一定能够实现目标，不需要再做额外的处理，不保证一定能够全覆盖的情形，参见灌溉花园的最少水龙头数目。

具体实现

class Solution {public int jump(int[] nums) {int res = 0;int curEnd = 0;int nextEnd = 0;// 由于到达的位置是 n - 1，那么在 n - 2 的位置上有可能进行最后一次操作for(int i = 0; i < nums.length - 1; i++) {// 在每个位置上更新能够到达的最远边界nextEnd = Math.max(nextEnd, i + nums[i]);// 如果当前已经不能继续往前走，那么在这个位置上造桥if(i == curEnd) {curEnd = nextEnd;res++;}}return res;}
}

相关文章：

【Leetcode 每日一题 - 扩展】45. 跳跃游戏 II

问题背景给定一个长度为 n n n 的 0 0 0 索引整数数组 n u m s nums nums。初始位置为 n u m s [ 0 ] nums[0] nums[0]。每个元素 n u m s [ i ] nums[i] nums[i] 表示从索引 i i i 向前跳转的最大长度。换句话说，如果你在 n u m s [ i ] nums[i] nums[i…...

编程日记 2025/6/3 7:06:25

被裁20240927 --- YOLO 算法

背景在云端部署ViSP，ViSP实现视觉伺服、yolo实现视觉跟踪。开源的2d视觉跟踪算法有哪些？ 开源的2D视觉跟踪算法有很多呢，这里给你推荐一些比较知名和常用的吧。 ByteTrackV2：这是一个通用2D跟踪算法，提出了分层的…...

编程日记 2025/6/4 4:23:00

AI技术架构：从基础设施到应用

人工智能（AI）的发展，正以前所未有的速度重塑我们的世界。了解AI技术架构，不仅能帮助我们看懂 AI 的底层逻辑，还能掌握其对各行业变革的潜力与方向。一、基础设施层：AI 技术的坚实地基基础设施层是 AI 技…...

编程日记 2025/6/2 10:39:53

植物大战僵尸辅助【控制台版本】

前面介绍了使用CE和OD的简单使用：CE和OD介绍和使用CE查找阳光的教学：阳光基地址和偏移地址，下面先使用最简单的控制台程序来实现修改阳光的功能。项目地址 1.分析程序我们的控制台程序想要修改植物大战僵尸游戏内的数据，它们…...

编程日记 2025/6/1 6:45:28

css中样式前加 css样式前面加个圆点

创建CSS样式,样式名称的前面需要加什么 1、我们只知道符号代表的意思是at，其翻译是在... 例如media就是在媒介上。没人规定本身具有什么意义，或者说就算规定了我们也改变不了，只需要知道其规定属性的用法即可。 2、px;}然后根据你自己索要…...

编程日记 2025/6/3 7:31:52

算法刷题Day18: BM41 输出二叉树的右视图

题目链接描述思路： 递归构造二叉树在Day15有讲到。复习一下，就是使用递归构建左右子树。将中序和前序一分为二。接下来是找出每一层的最右边的节点，可以利用队列层次遍历。利用队列长度记录当前层有多少个节点，每次从队列里…...

编程日记 2025/6/3 16:06:57

如何实现规范化LabVIEW编程

规范编写LabVIEW程序的目的是提高代码的可读性、可维护性、可扩展性，并确保团队成员能够高效地理解和修改代码。以下是一些关键建议，帮助您编写更专业的LabVIEW代码，并确保它易于后续的升级和维护： 1. 合理的项目结构目录结构…...

编程日记 2025/6/1 6:45:22

TQ15EG开发板教程：使用SSH登录petalinux

本例程在上一章“创建运行petalinux2019.1”基础上进行，本例程将实现使用SSH登录petalinux。将上一章生成的BOOT.BIN与imag.ub文件放入到SD卡中启动。给开发板插入电源与串口，注意串口插入后会识别出两个串口号，都需要打开，查看串…...

编程日记 2025/6/1 6:45:21

Springboot+vue实现大文件上传

背景：为了实现大文件上传的功能 1新建数据表sql file_chunk CREATE TABLE file_chunk (id bigint UNSIGNED NOT NULL AUTO_INCREMENT,file_name varchar(255) CHARACTER SET utf8mb4 COLLATE utf8mb4_unicode_520_ci NULL DEFAULT NULL COMMENT 文件名,chunk_nu…...

编程日记 2025/6/2 11:16:08

Linux笔记

常用的基本命令查询某个安装包有没有安装某个软件使用的命令是rpm -qa |grep 软件名字卸载软件 rpm -e --nodeps 软件名称查看已经启动的服务 netstat -tunlp 一般我们在Linux系统中上传文件一般上传到 /usr/local/src的目录下查看防火墙的命令 firewall-cmd --sta…...

编程日记 2025/6/1 6:45:17

相机（Camera）成像原理详解

简介：个人学习分享，如有错误，欢迎批评指正。成像流程 1、光学相机的定义顾名思义，光学相机就是利用光学原理进行成像的相机，而且市面上的相机几乎都是光学相机，只不过随着时代的发展，胶卷式…...

编程日记 2025/6/4 8:50:13

计算机网络知识点全梳理（一.TCP/IP网络模型）

目录 TCP/IP网络模型概述应用层什么是应用层应用层功能应用层协议传输层什么是传输层传输层功能传输层协议网络层什么是网络层网络层功能网络层协议数据链路层什么是数据链路层数据链路层功能物理层物理层的概念和功能写在前面本系列文…...

编程日记 2025/6/1 6:45:13

后端接受前端传递数组进行批量删除

问题描述：当我们需要做批量删除功能的时候，我们循环单次删除的接口也能进行批量删除，但要删除100条数据就要调用100次接口，或者执行100次sql，这样系统开销是比较大的，那么我们直接采用接收的数组格式数据sq…...

编程日记 2025/6/4 16:23:17

理解数据结构 hashtable的简易理解思路

结构图为了方便演示，下图中分区算法为下标取模 private int hashFun(int id) {//使用 hash并取模return id % size;}Hashtable的结构如图所示：是一个数组（元素为各个链表的表头） 多个链表组成，也就是说 hashtable 结…...

编程日记 2025/6/2 21:48:50

大数据面试题--企业面试真题

大数据面试题--企业面试真题 PlanHub 点击访问获取： 大数据面试体系专栏_酷兜科技www.kudoumh.top/hlwai/85.html 点击访问获取： 大数据面试体系专栏_酷兜科技www.kudoumh.top/hlwai/85.html 大数据面试题汇总 HDFS 1、 HDFS 读写流程。 2、HDF…...

编程日记 2025/6/4 17:26:20

数据结构(C语言版)-6.查找

1. 查找的基本概念 2. 静态查找 2.1 顺序查找 typedef int KeyType; typedef int InfoType; typedef struct {KeyType key;InfoType otherdata; }SeqList; // 顺序表类型 // 顺序查找int SeqSearch(SeqList R[], int n, int k) {int i n;R[0].key k; // R[0].key为查找不成…...

编程日记 2025/6/3 20:44:29

RabbitMQ消息队列的笔记

Rabbit与Java相结合引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-amqp</artifactId> </dependency> 在配置文件中编写关于rabbitmq的配置 rabbitmq:host: 192.168.190.132 /…...

编程日记 2025/6/3 16:40:03

linux不同发行版中的主要差异

一、初始化系统 Linux不同发行版中的系统初始化系统（如 System V init、Upstart 或 systemd） System V init： 历史：System V init 是最传统的 Linux 系统初始化系统，起源于 Unix System V 操作系统。运行级别&#xff…...

编程日记 2025/6/4 1:30:26

Elasticsearch+Kibana分布式存储引擎

1.ElaticSearch介绍 ElaticSearch ，简称为 ES ， ES 是一个开源的高扩展的分布式全文检索引擎，它可以近乎实时的存储、检索数据；本身扩展性很好，可以扩展到上百台服务器，处理 PB 级别的数据。 ES 也使用 …...

编程日记 2025/5/30 17:18:14

spark 分布式原理

Apache Spark 是一个快速且通用的大数据处理引擎，它支持分布式计算。Spark 的设计旨在通过高效的内存内计算和对多种数据源的支持来简化大规模数据集的处理。以下是关于 Spark 分布式原理的详细介绍： 1. 架构概述 Driver Program（驱动程序&…...

编程日记 2025/6/4 10:03:01

Hadoop学习笔记（包括hadoop3.4.0集群安装）（黑马）

Hadoop学习笔记 0-前置章节-环境准备 0.1 环境介绍配置环境：hadoop-3.4.0，jdk-8u171-linux-x64 0.2 VMware准备Linux虚拟机 0.2.1主机名、IP、SSH免密登录 1.配置固定IP地址（root权限） 开启master，修改主机名为…...

编程日记 2025/6/4 7:01:27

thinkphp：try-catch捕获异常

使用简单的例子，实现了一个简单的try-catch捕获异常的实例 //开始事务Db::startTrans(); try{ //有异常抛出异常 if(存在错误){ throw new \Exception("异常信息"); } // 提交事务 Db::commit(); // 返回成功信息 ... } catch (\…...

编程日记 2025/6/4 2:10:44

如何使用 uni-app 构建直播应用程序？

使用uni-app构建直播应用程序涉及前端和后端的开发，以及音视频处理技术的选择。下面我将概述一个典型的直播应用架构，并详细说明如何在uni-app中实现关键功能。直播应用架构前端（uni-app）：负责用户界面展示、互动逻…...

编程日记 2025/6/3 22:41:44

正则表达式入门教程

正则表达式入门教程 1. 引言正则表达式（Regular Expression，简称Regex）是一种用于处理字符串的强大工具，它允许用户通过特定的模式（pattern）来搜索、匹配、查找和替换文本中的数据。正则表达式在文本处理、数据验证、数据提取等领域有着广泛的应用。本教程将带你了解正…...

编程日记 2025/6/4 4:59:46

uniapp 常用的指令语句

uniapp 是一个使用 Vue.js 开发的跨平台应用框架，因此，它继承了 Vue.js 的大部分指令。以下是一些在 uniapp 中常用的 Vue 指令语句及其用途： v-if / v-else-if / v-else 条件渲染。v-if 有条件地渲染元素，v-else-if 和 v-else 用…...

编程日记 2025/6/3 18:50:38

【Figma_01】Figma软件初始与使用

Figma初识与学习准备背景介绍软件使用1.1 切换主题1.2 官方社区设计界面2.1 创建一个项目2.2 修改文件名2.3 四种模式2.4 新增界面2.5 图层2.6 工具栏2.7 属性栏section透明度和圆角改变多边形的边数渐变效果描边设置阴影等特效拖拽相同的图形背景介绍 Ul设计:User Interfa…...

编程日记 2025/6/2 10:06:29

AI工具如何深刻改变我们的工作与生活

在当今这个科技日新月异的时代，人工智能（AI）已经从科幻小说中的概念变成了我们日常生活中不可或缺的一部分。从智能家居到自动驾驶汽车，从医疗诊断到金融服务，AI正以惊人的速度重塑着我们的世界。一、工作方式的革新…...

编程日记 2025/6/2 18:04:08

信息安全实训室网络攻防靶场实战核心平台解决方案

一、引言网络安全靶场，作为一种融合了虚拟与现实环境的综合性平台，专为基础设施、应用程序及物理系统等目标设计，旨在向系统用户提供全方位的安全服务，涵盖教学、研究、训练及测试等多个维度。随着网络空间对抗态势的日益复杂化…...

编程日记 2025/6/2 13:16:43

平方根无迹卡尔曼滤波（SR-UKF）的MATLAB例程，使用三维非线性的系统

本MATLAB 代码实现了平方根无迹卡尔曼滤波（SR-UKF）算法，用于处理三维非线性状态估计问题文章目录运行结果代码概述代码运行结果三轴状态曲线对比： 三轴误差曲线对比： 误差统计特性输出（命令行截图&…...

编程日记 2025/6/1 14:16:32

【从零开始入门unity游戏开发之——C#篇04】栈（Stack）和堆（Heap），值类型和引用类型，以及特殊的引用类型string，垃圾回收（ GC）

文章目录知识回顾一、栈（Stack）和堆（Heap）1、什么是栈和堆2、为什么要分栈和堆3、栈和堆的区别栈堆 4、总结二、值类型和引用类型1、那么值类型和引用类型到底有什么区别呢？值类型引用类型 2、总结三、特殊的引用类…...

编程日记 2025/6/1 11:06:45

人员离岗监测摄像机智能人员睡岗、逃岗监测 Python 语言结合 OpenCV

在安全生产领域，人员的在岗状态直接关系到生产流程的顺利进行和工作环境的安全稳定。人员离岗监测摄像机的出现，为智能人员睡岗、逃岗监测提供了高效精准的解决方案，而其中的核心技术如AI识别睡岗脱岗以及相关的算法盒子和常见的安全生产AI算…...

编程日记 2025/6/4 5:25:09

Linux-ubuntu点LED灯C语言版

一，C语言点灯 1.寄存器配置设置为SVC模式，复用寄存器设置GPIO1-IO003,设置电气属性，设置为输出模式。 2.软件汇编语言对模式设置，并且将堆栈指针指向主程序： .global _start_start: /*设置为svr模式 */mrs …...

编程日记 2025/6/2 0:02:54

第P3周：Pytorch实现天气识别

🍨 本文为🔗365天深度学习训练营中的学习记录博客🍖 原作者：K同学啊目标读取天气图片，按文件夹分类搭建CNN网络，保存网络模型并加载模型使用保存的模型预测真实天气具体实现 （一&#xf…...

编程日记 2025/6/2 3:39:10

代理IP与生成式AI：携手共创未来

目录代理IP：网络世界的“隐形斗篷” 1. 隐藏真实IP，保护隐私 2. 突破网络限制，访问更多资源生成式AI：创意与效率的“超级大脑” 1. 提高创作效率 2. 个性化定制代理IP与生成式AI的协同作用 1. 网络安全 2. 内容创作与…...

编程日记 2025/6/1 20:30:56

函数式编程

Lambda表达式 1、什么时候可以使用Lambda表达式呢？一般都是在简化匿名内部类，当这个函数是一个接口，并且接口中只要一个方法时，就可以使用Lambda表达式 2、格式 (参数列表)->{方法体} 其中形参也不需要传，只需要传实参只关注参数列表和方法体不关注方法啥的东西…...

编程日记 2025/5/29 18:45:52

抖音SEO短视频矩阵源码系统开发分享

在数字营销的前沿阵地，抖音短视频平台凭借其独特的魅力和庞大的用户基础，已成为社交媒体领域一股不可小觑的力量。随着平台影响力的持续扩大，如何有效提升视频内容的可见度与流量成为了内容创作者关注的焦点。在此背景下，一套专为…...

编程日记 2025/6/1 23:32:54

常见的锁与线程安全

目录一、STL,智能指针和线程安全 STL中的容器是否是线程安全的? 智能指针是否是线程安全的? 二、其他常见的各种锁三、自旋锁四、读者写者问题读写锁接口读者优先伪代码一、STL,智能指针和线程安全 STL中的容器是否是线程安全的? 不是 . 原因是 , STL 的设…...

编程日记 2025/6/2 4:29:04

java中的List、数组和set

在Java中，List、数组（Array）和Set 是三种常用的数据结构，它们各自有不同的特性、用途和实现方式。下面我们将深入探讨这三者的特点、区别以及它们在 Java 中的常见使用场景。 1. 数组（Array） 特性&#x…...

编程日记 2025/6/3 3:59:16

NLP-Huggingface基本使用方法

NLP的网络结构大同小异，只不过训练策略可能会不同。因为与图像cv不同，文本训练数据非常的多，cv可以使用10几张就可以获得特征向量，而文本做不到学几句话就能让计算机听得懂话。因此，我们都需要使用预训练模型&#xff…...

编程日记 2025/6/3 19:35:22

Liquibase结合SpringBoot使用实现数据库管理

Liquibase概述 Liquibase 是一个开源的数据库变更管理工具，用于跟踪、版本化、和管理数据库结构（如表、字段、索引等）的变更。它的目的是使数据库变更的过程更加透明、可控制、自动化，避免开发团队在多个环境中手动执行相同的数据…...

编程日记 2025/5/28 5:36:43

高防CDN 如何防止DDoS和CC攻击？

在数字化时代，网络安全威胁日益严重，尤其是DDoS（分布式拒绝服务）攻击和CC（Challenge Collapsar）攻击，已成为企业网站和网络服务最常见且最具破坏力的攻击手段。为了有效抵御这些攻击&#xff0c…...

编程日记 2025/6/1 15:41:25

15.初始接口1.0 C#

这是一个用于实验接口的代码适合初认识接口的人【CSDN开头介绍】（文心一言AI生成） 在C#编程世界中，接口（Interface）扮演着至关重要的角色，它定义了一组方法，但不提供这些方法的实现。接口作为…...

编程日记 2025/6/2 19:05:23

数据结构day5：单向循环链表代码作业

一、loopLink.h #ifndef __LOOPLINK_H__ #define __LOOPLINK_H__#include <stdio.h> #include <stdlib.h>typedef int DataType;typedef struct node {union{int len;DataType data;};struct node* next; }loopLink, *loopLinkPtr;//创建 loopLinkPtr create();//…...

编程日记 2025/6/4 1:52:33

利用CNN与多尺度特征、注意力机制的融合实现低分辨率人脸表情识别，并给出模型介绍与代码实现

大家好，我是微学AI，今天给大家介绍一下利用CNN与多尺度特征、注意力机制的融合实现低分辨率人脸表情识别，并给出模型介绍与代码实现。在当今社会，人脸识别技术已广泛应用，但特定场景下的低质量图像仍是一大挑战。低分…...

编程日记 2025/6/2 1:07:06

spring RestTemplate使用说明

rest-template是spring对httpclient的逻辑封装，它底层还是基于httpclient，所以一些配置其实跟httpclient是强相关的。基本配置 rest-template可以不带参数，使用默认配置，也可以指定ClientHttpRequestFactory参数，Cl…...

编程日记 2025/6/3 13:43:12

设置HP条UI

概述设置常见的生命值条， 实现过程设置UI/image作为形状设置UI/Image作为背景设置UI/image（healthfill）作为填充图片，层数低于背景设置heathfill的imagetype为filled fillmethod为horizontal [SerializeField] private Im…...

编程日记 2025/6/3 10:03:52

常见排序算法总结 (五) - 堆排序与堆操作

堆排序（借助 API） 算法思想利用堆能够维护数组中最大值的性质，根据数组元素建立最大堆，依次弹出元素并维护堆结构，直到堆为空。稳定性分析堆排序是不稳定的，因为堆本质上是完全二叉树，排…...

编程日记 2025/6/4 6:45:56

Linux 本地编译安装 gcc9

这里演示非sudo权限的本地linux 用户安装 gcc9 下载源代码： 可以从GCC官方网站或其镜像站点下载GCC 9的源代码压缩包。使用wget或curl命令，这通常不需要额外权限 wget https://ftp.gnu.org/gnu/gcc/gcc-9.5.0/gcc-9.5.0.tar.gz tar -xf gcc-9.5.0.tar…...

编程日记 2025/6/2 5:19:21

开源FreeSWITCH大模型智能客服系统的最佳实践

开源 FreeSWITCH 大模型智能客服系统的最佳实践原作者：开源呼叫中心FreeIPCC，其Github：https://github.com/lihaiya/freeipcc 引言开源 FreeSWITCH 大模型智能客服系统因其灵活性、成本效益和技术先进性，成为众多企业提升客户…...

编程日记 2025/6/1 6:36:35

大数据技术与应用——数据可视化（山东省大数据职称考试）

大数据分析应用-初级第一部分基础知识一、大数据法律法规、政策文件、相关标准二、计算机基础知识三、信息化基础知识四、密码学五、大数据安全六、数据库系统七、数据仓库. 第二部分专业知识一、大数据技术与应用二、大数据分析模型三、数据科学数据可视化大…...

编程日记 2025/6/1 15:47:22