LeetCode45:跳跃游戏Ⅱ

题目描述
给定一个长度为 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.当前能走到的最远位置maxPos 2.上次跳跃能走到的右边界end
如果遍历的时候到达了end但是并没有到达终点就说明需要进行跳跃

代码

class Solution {
public:
    int jump(vector<int>& nums) {
        //在遍历的同时维护两个变量:1.当前能走到的最远位置maxPos   2.上次跳跃能走到的右边界end
        int maxPos = 0, end = 0;
        int step = 0;

  
        for (int i = 0; i < nums.size() - 1; i++) {
            maxPos = max(maxPos, nums[i] + i);
            //如果已经到达上次跳跃所能到达的右边界,就说明需要进行跳跃,更新右边界
            if (i == end) {
                end = maxPos;
                step++;

                //如果当前更新的右边界能够抵达终点,就退出循环
                if (end >= nums.size() - 1) break;
            }
        }
        return step;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/586973.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C++成员初始化列表

我们在类的构造函数中使用成员初始化列表可以带来效率上的提升&#xff0c;那么成员初始化列表在编译后会发生什么就是这篇文章要探究的问题 文章目录 引入成员初始化列表用成员初始化列表优化上面的代码成员初始化列表展开成员初始化列表的潜在危险 参考资料 引入 考虑下面这…

TDengine写入2000万数据查询体验

最近在寻找时序数据库&#xff0c;想应用在公司的项目上。 上一篇文章实验了InfluxDB:windows上使用influx2.7学习,还学习了flux语言&#xff0c;最后发现宽表查询比较困难&#xff0c;就放弃了&#xff0c;于是决定试试国产时序数据库TDengine 参考 官方文档&#xff1a;htt…

有货源和分销单品爆款玩法课

该课程专注于教授如何利用有货源和分销渠道&#xff0c;打造单品爆款销售策略。学员将学习货源获取、产品定位、市场推广等关键技巧&#xff0c;通过实战案例和实操训练&#xff0c;掌握成功销售单品爆款的方法&#xff0c;提升销售业绩和市场竞争力。 课程大小&#xff1a;6.…

RabbitMq基础概念知识复习

消息拥有消息头和消息体&#xff0c;消息具有rounting key&#xff0c;主题交换机和扇形交换机都是发布与订阅的实现方式&#xff0c;主题交换机用于匹配接收的消息的rount key 动态匹配模式匹配到多个符合的队列&#xff0c;扇形fanout交换机则不会使用消息的路由key&#xff…

【AIGC调研系列】InternVL开源多模态模型与GPT-4V的性能对比

InternVL和GPT-4V都是多模态模型&#xff0c;但它们在性能、参数量以及应用领域上有所不同。 InternVL是一个开源的多模态模型&#xff0c;其参数量为60亿&#xff0c;覆盖了图像/视频分类、检索等关键任务&#xff0c;并在32个视觉-语言基准测试中展现了卓越性能[2]。InternV…

CYP76AKs的功能分化塑造了鼠尾草属中松香烷型二萜化合物的化学多样性-比较转录组-文献精读12

Functional divergence of CYP76AKs shapes the chemodiversity of abietane-type diterpenoids in genus Salvia "CYP76AKs的功能分化塑造了鼠尾草属中松香烷型二萜化合物的化学多样性"&#xff0c;一片比较转录组的文献&#xff0c;类似比较转录组分析揭示了116种…

数据仓库Data Warehouse

数据仓库Data Warehouse 数仓是一种思想,数仓是一种规范,数仓是一种解决方案 1. 数据处理方式 数据处理大致可以分成两大类: 联机事务处理OLTP(on-line transaction processing)联机分析处理OLAP(On-Line Analytical Processing)1.1. OLTP OLTP的全称是On-line Transa…

O2OA开发平台前端源码级二次开发(Vue3,React)

在使用O2OA进行项目定制化开发时&#xff0c;我们可以开发新的前端组件&#xff08;x_component&#xff09;以扩展O2OA来实现更多的业务。这种新增前端组件或者前端业务的开发通常会配合后端自定义应用实现的服务来完成系统内数据的交互。在当系统默认的界面不符合系统UI/UE设…

283. 移动零 11. 盛最多水的容器

283. 移动零 把非零的数全交换到前面去 11. 盛最多水的容器 双指针&#xff1a; 双指针一个在头 一个在尾部 计算两个边的盛水量并更新数值 左右两边 哪边矮就移动哪边

区块链快速参考(三)

原文&#xff1a;zh.annas-archive.org/md5/b5e57485b0609afbfba46ff759c5d264 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 第十七章&#xff1a;去中心化应用程序 去中心化应用&#xff08;DApps&#xff09;是在去中心化网络上运行的应用程序&#xff0c;不受集…

2024五一杯数学建模B题思路分析 - 未来新城背景下的交通需求规划与可达率问题

文章目录 1 赛题选题分析 2 解题思路详细的思路过程放在文档中 ! ! &#xff01;&#xff01;&#xff01;&#xff01;&#xff01;3 最新思路更新 1 赛题 B题 未来新城背景下的交通需求规划与可达率问题 随着城市化的持续发展&#xff0c;交通规划在新兴城市建设中显得尤为关…

Linux搭建靶场

提前准备&#xff1a; 文章中所使用到的Linux系统&#xff1a;Ubantu20.4sqlilabs靶场下载地址&#xff1a;GitHub - Audi-1/sqli-labs: SQLI labs to test error based, Blind boolean based, Time based. 一. 安装phpstudy phpstudy安装命令&#xff1a;wget -O install.sh h…

Map和Set基础

目录 一、导论 二、Map 三、Set 本文找先不涉及两种数据结构的底层&#xff0c;目标是&#xff1a; 理解Map和Set的大体框架&#xff0c;了解他们有什么用&#xff0c;用在哪里的&#xff0c;然后再从浅层深入底层。 小编认为&#xff1a; 先了解也下Map和Set大体是用来做…

Mysql--创建数据库

一、创建一个数据库 “db_classes” mysql> create database db_classes; mysql> show databases; -------------------- | Database | -------------------- | db_classes | | information_schema | | mysql | | performance_schema | |…

开通Jetbrains个人账号,赠送这些付费插件

开通Jetbrains个人账号&#xff0c;或者Jetbrains现成账号的, 可赠送以下付费插件 现成账号&#xff1a;https://web.52shizhan.cn/activity/xqt8ly 个人账号&#xff1a;https://web.52shizhan.cn/legal 账号支持全家桶系列&#xff1a;AppCode,CLion,DataGrip,GoLand,Intell…

Codeforces Round 941 (Div. 2) (A~D)

1966A - Card Exchange 题意&#xff1a; 思路&#xff1a;手玩一下发现当存在某个数字个数超过k个&#xff0c;那么就能一直操作下去。那么答案就是k-1. void solve() {cin >> n >> m;map<int,int>mp;int maxx 1;for(int i 0 ; i < n ; i ){int x;c…

手把手教数据结构与算法:优先级队列(银行排队问题)

队列 基本概念 队列的定义 队列&#xff08;Queue&#xff09;&#xff1a;队列是一种常见的数据结构&#xff0c;遵循先进先出&#xff08;First-In-First-Out, FIFO&#xff09;的原则。在队列中&#xff0c;元素按照进入队列的顺序排列。队列是一个线性的数据结构&#x…

深入解析yolov5,为什么算法都是基于yolov5做改进的?(一)

YOLOv5简介 YOLOv5是一种单阶段目标检测算法&#xff0c;它在YOLOv4的基础上引入了多项改进&#xff0c;显著提升了检测的速度和精度。YOLOv5的设计哲学是简洁高效&#xff0c;它有四个版本&#xff1a;YOLOv5s、YOLOv5m、YOLOv5l、YOLOv5x&#xff0c;分别对应不同的模型大小…

深度学习从入门到精通——词向量介绍及应用

词向量介绍 词向量&#xff08;Word embedding&#xff09;&#xff0c;即把词语表示成实数向量。“好”的词向量能体现词语直接的相近关系。词向量已经被证明可以提高NLP任务的性能&#xff0c;例如语法分析和情感分析。词向量与词嵌入技术的提出是为了解决onehot的缺陷。它把…

pytorch中创建maskrcnn模型

0.模型输入/输出参数参见 链接: pytorch的mask-rcnn的模型参数解释 核心代码 GeneralizedRCNN(这里以mask-rcnn来解释说明) # 通过输入图像获取fpn特征图,注意这里的backbone不是直接的resnet,而是fpn化后的 features self.backbone(images.tensors) # 由于是mask-rcnn,故而…