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

刷题记录 HOT100 贪心-2:45. 跳跃游戏 II

题目:45. 跳跃游戏 II

难度:中等

给定一个长度为 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

提示:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • 题目保证可以到达 nums[n-1]

一、模式识别

1.贪心算法

跳跃游戏是常见的贪心算法题

通过贪心地计算本次的最远跳跃距离得到到终点的最远跳跃距离

方法是逐步遍历,动态更新下一个最远条约距离,

当达到本次的最远距离时,最小步数 + 1,且下一个变成本次的最远距离

二、代码实现

class Solution:def jump(self, nums: List[int]) -> int:ans = 0cur = nex = 0n = len(nums)for i in range(n - 1):nex = max(nex, i + nums[i])if i == cur:ans += 1cur = nexreturn ans

相关文章:

刷题记录 HOT100 贪心-2:45. 跳跃游戏 II

题目&#xff1a;45. 跳跃游戏 II 难度&#xff1a;中等 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说&#xff0c;如果你在 nums[i] 处&#xff0c;你可以跳转到任意 nums[i j] 处: 0 &l…...

7.2 奇异值分解的基与矩阵

一、奇异值分解 奇异值分解&#xff08;SVD&#xff09;是线性代数的高光时刻。 A A A 是一个 m n m\times n mn 的矩阵&#xff0c;可以是方阵或者长方形矩阵&#xff0c;秩为 r r r。我们要对角化 A A A&#xff0c;但并不是把它化成 X − 1 A X X^{-1}A X X−1AX 的形…...

PDFMathTranslate安装使用

PDF全文翻译&#xff01;&#xff01;&#xff01;&#xff01; PDFMathTranslate安装使用 它是个啥 PDFMathTranslate 可能是一个用于 PDF 文件的数学公式翻译 工具。它可能包含以下功能&#xff1a; 提取 PDF 内的数学公式 将数学公式转换成 LaTeX 代码 翻译数学公式的内…...

STL之list的使用(超详解)

目录 一、list的介绍及使用 1.1 list的介绍 1.2 list的使用 1.2.1 list的构造 1.2.2 iterator的使用 1.2.3capacity&#xff08;容量相关&#xff09; 1.2.4 element access&#xff08;元素访问&#xff09; 1.2.5 modifiers&#xff08;链表修改&#xff09;…...

动态 SQL 的使用

目录 1、< if> 标签2、< trim> 标签3、< where> 标签4、< set> 标签5、< foreach> 标签 1、< if> 标签 < if test“条件语句”> xxxx < /if> 只有当条件语句满足条件&#xff0c;才会拼接 < if> 标签内容&#xff0c;因…...

【如何删除在 Linux 系统中的删除乱码文件】

如何删除在 Linux 系统中的删除乱码文件 1. 列出文件并找到乱码文件&#xff1a;2. 使用通配符&#xff08;谨慎使用&#xff09;&#xff1a;3. 转义特殊字符&#xff1a;4. 使用 find 命令&#xff1a;5. 使用 inode 号删除文件&#xff1a;6. 图形界面文件管理器&#xff1a…...

防火墙IPSec (无固定IP地址---一对多)

目录 前言 一、场景&#xff1a; 二、实现 1.拓扑图 2.配置思路 ①基础通信配置 ②PPPoE配置 ③总部的模版IPSec配置 ④分部的IPSec配置 ⑤NAT配置 3.具体配置 ①基础配置 ②详细配置和顺序 效果测试&#xff1a; ③PPPOE ①配置PPPoE ②策略放行 ③IPSec与NA…...

基于SpringBoot的智能问诊系统设计与隐私保护策略

通过SpringBoot框架&#xff0c;我们可以快速搭建一个智能问诊系统&#xff0c;为用户提供便捷的线上医疗服务。然而&#xff0c;在系统设计和实现过程中&#xff0c;如何保障用户的隐私和数据安全&#xff0c;始终是一个亟需关注的问题。本文将探讨基于SpringBoot的智能问诊系…...

DeepSeek进阶应用(一):结合Mermaid绘图(流程图、时序图、类图、状态图、甘特图、饼图)

&#x1f31f;前言: 在软件开发、项目管理和系统设计等领域&#xff0c;图表是表达复杂信息的有效工具。随着AI助手如DeepSeek的普及&#xff0c;我们现在可以更轻松地创建各种专业图表。 名人说&#xff1a;博观而约取&#xff0c;厚积而薄发。——苏轼《稼说送张琥》 创作者&…...

Ubuntu 下 nginx-1.24.0 源码分析 - ngx_init_cycle 函数

nei声明在 src/core/ngx_cycle.h ngx_cycle_t *ngx_init_cycle(ngx_cycle_t *old_cycle);实现在 src/core/ngx_cycle.c ngx_cycle_t * ngx_init_cycle(ngx_cycle_t *old_cycle) {void *rv;char **senv;ngx_uint_t i, n;ngx_log_t …...

【redis】数据类型之geo

Redis的GEO数据类型用于存储地理位置信息&#xff08;如经纬度&#xff09;&#xff0c;并提供高效的地理位置查询功能&#xff08;如计算两地距离、搜索附近地点等&#xff09;。其底层基于Sorted Set&#xff08;有序集合&#xff09;实现&#xff0c;通过Geohash编码将经纬度…...

vue3 vite或者vue2 百度地图(卫星图)离线使用详细讲解

1、在Windows上下载瓦片&#xff0c;使用的工具为: 全能电子地图下载器3.0最新版&#xff08;推荐&#xff09; 下载后解压&#xff0c;然后进入目录"全能电子地图下载器3.0最新版&#xff08;推荐&#xff09;\全能电子地图下载器3.0\MapTileDownloader" 在这个目录…...

《Python实战进阶》No17: 数据库连接与 ORM(SQLAlchemy 实战)

No17: 数据库连接与 ORM&#xff08;SQLAlchemy 实战&#xff09; 摘要 本文深入探讨SQLAlchemy在复杂场景下的高级应用&#xff0c;涵盖四大核心主题&#xff1a; 会话生命周期管理&#xff1a;通过事件钩子实现事务监控与审计追踪混合继承映射&#xff1a;结合单表/连接表继…...

工程化与框架系列(27)--前端音视频处理

前端音视频处理 &#x1f3a5; 引言 前端音视频处理是现代Web应用中的重要组成部分&#xff0c;涉及音频播放、视频处理、流媒体传输等多个方面。本文将深入探讨前端音视频处理的关键技术和最佳实践&#xff0c;帮助开发者构建高质量的多媒体应用。 音视频技术概述 前端音视…...

芋道打包时报错:缺失@unocss插件

在遇到打包时&#xff0c;报这个错误&#xff0c;提示构建失败是因为 ESLint 在加载 unocss 插件时&#xff0c;找不到 unocss/eslint-plugin 模块 解决办法&#xff1a;安装缺失的依赖&#xff1a;保证unocss/eslint-plugin已经被正确安装&#xff0c; 使用以下命令安装&…...

PY32MD320单片机 QFN32封装,内置多功能三相 NN 型预驱。

PY32MD320单片机是普冉半导体的一款电机专用MCU&#xff0c;芯片采用了高性能的 32 位 ARM Cortex-M0 内核&#xff0c;主要用于电机控制。PY32MD320嵌入高达 64 KB Flash 和 8 KB SRAM 存储器&#xff0c;最高工作频率 48 MHz。PY32MD320单片机的工作温度范围为 -40 ~ 105 ℃&…...

深入解析 configService.addListener 使用中的注意事项

在使用 Nacos 的 configService.addListener 方法进行配置监听时&#xff0c;为了确保程序的稳定性、可靠性以及高效性&#xff0c;有诸多注意事项需要我们关注。下面将对这些关键要点进行详细阐述。 一、连接稳定性 1.1 网络连接问题 Nacos 客户端与服务端通过网络进行通信&…...

Windows控制台函数:控制台读取输入函数ReadConsoleA()

目录 什么是 ReadConsoleA&#xff1f; 它长什么样&#xff1f; 怎么用它&#xff1f; 它跟 std::cin 有什么不一样&#xff1f; 注意事项 什么是 ReadConsoleA&#xff1f; ReadConsoleA 是一个 Windows API 函数&#xff0c;用来从控制台读取用户输入。想象一下&#…...

奇安信 2025 年护网蓝队初选笔试题(附答案解析)

&#x1f525; 爆款 CSDN 题库 | 超全护网蓝队笔试真题 | 含详细答案解析 &#x1f525; 熬夜为大家整理了 奇安信 2025 年护网蓝队初选笔试题&#xff0c;&#xff08;关注我我会持续更新&#xff09;涵盖 SQL 注入、Web 安全、渗透测试、二进制安全 等核心知识点&#xff0c;…...

国产编辑器EverEdit - Web预览设置

1 设置-高级-Web预览 1.1 设置说明 选择主菜单工具 -> 设置 -> 常规&#xff0c;在弹出的选项窗口中选择Web预览分类&#xff0c;如下图所示&#xff1a; 1.1.1 本地浏览HTML文件 如果用户只是在本地浏览HTML文件&#xff0c;即直接用浏览器打开HTML文件&#xff0c;确…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

技术栈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 主题模式…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...