力扣刷题 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

解题思路

贪心算法的核心思想是选择每一阶段的局部最优,从而达到全局最优。

因此,我们以数组遍历元素作为题目的大背景,每遍历一个元素,就是一个阶段,在这个阶段下去做操作,而这个操作要是当前阶段最优的。

for(int i = 0;i <nums.size();i++){

本题的目标是使用最少的跳跃步数达到数组的最后一个位置,那么怎么才能实现这一目标呢?

我们可能会想到每次跳当前元素的最大距离,但是这其实是错误的,让我们看一组例子,当前我们在下标为0,最大跳跃距离为2的格子,它的覆盖范围为从0到2,如果我们每次跳当前元素的最大距离,那么就会跳到下标为2,跳跃距离为1的元素,后面的过程就不一一罗列,整体的跳跃次数为3,下标由0到2到3再到4。

很明显这不是最优解,如果在下标为1的元素起跳,只需两步就到终点了。

最优策略应该是在当前覆盖范围内中,选出具有最大跳跃能力的元素,作为下一个起跳点。这样的意义是实现了每一阶段可以覆盖最大的范围,全局上就可以最优地覆盖到终点。而这也正是本题的难点,不太容易想到。

那么现在我们的目标是在当前覆盖范围内中,选出具有最大跳跃能力的元素。但是怎么把这一策略转换成代码?

作为下一个起跳点选出最大跳跃能力的元素很简单,可以用max函数更新。但是现在的问题是怎么

用代码实现在覆盖范围内,用遍历?还是用index记录?还有下一个起跳点怎么实现,用回溯吗?

第一个起跳点是默认的,就是第一个元素,如果我们要去思考,怎么选择到第一个元素作为起跳点,第一个起跳步数是怎么增加的,思路会很变扭。所以我们可以选择先不考虑这种特殊情况,从常规的阶段中找思路。最后再来验证我们写的代码是否兼容了这个特殊情况

我们假设从第一个元素开始遍历,下标为0,它的最大跳跃距离是2,因此它可以实现的覆盖范围为从0到2。当我们移动指针,指到下标为1的元素时,我们要记录他的值,以找到再覆盖范围内具有最大跳跃能力的元素,  这里有个点需要注意,我们记录的值是它的跳跃距离,还是它所能更新的覆盖范围。这里我们先记录它的最大跳跃距离。
for(int i = 0;i <nums.size();i++){
       next =  max(next,nums[i]);

然后我们移动指针指向下标为2的元素,记录他的值,这时我们已经遍历到覆盖范围的末端了,那么机器怎么知道已经到覆盖范围的末端了呢,我们很自然地联想到增加一个覆盖范围的变量cover,再使用一个判断语句去判断i是否等于覆盖范围cover。

}
    for(int i = 0;i <nums.size();i++){
       next =  max(next,nums[i]);
       if(i == cover){

下一步就是要从覆盖范围中,找到具有最大跳跃距离的元素。易知这个元素是下标为1的元素,我们要选这个元素为起跳点,但是我们的指针已经超过了这个元素,难不成要回溯回去吗?

其实不用,我们可以把覆盖范围cover更新,这样就在效果上实现了选下标为1的元素作为起跳点。因此,我们之前记录的值应该是覆盖范围cover,也就是nums[i]+i。这时,我们选定后下标为1的元素后,也就意味着实现了一次跳跃,步数要加一。修改和增加后的代码如下

   int cover = 0;
   int next = 0;
   int result = 0;
    
    for(int i = 0;i <nums.size();i++){
       next =  max(next,nums[i] + i);
       if(i == cover){
             cover = next;
             result ++;

下一步我们发现cover这个时候为4,已经覆盖到终点了,所以应该可以直接返回步数了。

所以我们在后面增加一个判断语句去判断覆盖范围是否大于等于数组末元素的下标,如果满足直接跳出循环。如果小于那就继续循环。

int jump(vector<int>& nums) {
   int cover = 0;
   int next = 0;
   int result = 0;

    for(int i = 0;i <nums.size();i++){
       next =  max(next,nums[i] + i);
       if(i == cover){
             cover = next;
             result ++;
             if(cover>=nums.size()-1){
                 break;
              }
       }
    }
    return result;
    }

现在我们来验证我们的代码是否兼容特殊情况,cover的初始值为0,i=0,next=2,因为i=cover=0,所以cover=2,result+1。不难发现,我们的代码是正确的,特殊情况也完美符合我们代码的逻辑。

但是在提交代码后,我们发现出错了,检查用例后,发现是当数组仅有一个元素的时候,不用跳跃就已经到终点,所以我们直接做一个剪枝操作,用一个if判断语句,跳出循环。

完整代码如下

class Solution {
public:
    int jump(vector<int>& nums) {
   int cover = 0;
   int next = 0;
   int result = 0;
    if(nums.size() == 1){
        return result;
    }
    for(int i = 0;i <nums.size();i++){
       next =  max(next,nums[i] + i);
       if(i == cover){
             cover = next;
             result ++;
             if(cover>=nums.size()-1){
                 break;
              }
       }
    }
    return result;
    }
};

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

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

相关文章

稀碎从零算法笔记Day39-LeetCode:有向无环图中一个节点的所有祖先

感觉写的越来越难了hhh&#xff0c;一晚上只研究明白了2道题 题型&#xff1a;拓扑排序、BFS、图 链接&#xff1a;2192. 有向无环图中一个节点的所有祖先 - 力扣&#xff08;LeetCode&#xff09; 来源&#xff1a;LeetCode 题目描述&#xff08;红字为笔者添加&#xff0…

FPGA实现Canny算法(Verilog)

在边缘检测算法里面Sobel是比较简单的一个算法&#xff0c;但是其检测出来的边缘往往是比较粗的&#xff0c;效果不是很好&#xff0c;因为我们最理想的边缘肯定就是一个宽度为1的细线。 Canny算法在此基础上进行了改进&#xff0c;通过使用边缘的梯度信息进行非最大值抑制(NM…

基于单片机的数字万用表设计

**单片机设计介绍&#xff0c;基于单片机的数字万用表设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机的数字万用表设计概要是关于使用单片机技术来实现数字万用表功能的一种设计方案。下面将详细概述该设计的各个…

C++ | Leetcode C++题解之第8题字符串转换整数atoi

题目&#xff1a; 题解&#xff1a; class Automaton {string state "start";unordered_map<string, vector<string>> table {{"start", {"start", "signed", "in_number", "end"}},{"signed…

Linux 多线程与线程控制(程序均有详细注释)

多线程与线程控制 线程的基本概念线程的特点页表多线程 线程控制线程的创建线程传参线程id资源回收---线程等待线程id和LWP 封装一个线程库线程互斥和线程同步线程互斥基本原理线程安全VS线程不安全锁的诞生可重入VS线程安全 死锁死锁的定义 线程同步条件变量接口 生成消费者模…

使用阿里云试用Elasticsearch学习:1.2 基础入门——数据输入和输出

什么是文档? 在大多数应用中&#xff0c;多数实体或对象可以被序列化为包含键值对的 JSON 对象。 一个 键 可以是一个字段或字段的名称&#xff0c;一个 值 可以是一个字符串&#xff0c;一个数字&#xff0c;一个布尔值&#xff0c; 另一个对象&#xff0c;一些数组值&#…

全流程基于GIS、python机器学习技术的地质灾害风险评价与信息化建库应用

入门篇&#xff0c;ArcGIS软件的快速入门与GIS数据源的获取与理解&#xff1b;方法篇&#xff0c;致灾因子提取方法、灾害危险性因子分析指标体系的建立方法和灾害危险性评价模型构建方法&#xff1b;拓展篇&#xff0c;GIS在灾害重建中的应用方法&#xff1b;高阶篇&#xff1…

Cisco路由器配置IPv6 Manual隧道

Cisco路由器配置IPv6 Manual隧道 IPv6与IPv4共存的方式 IPv6与IPv4共存方式大致有三种&#xff1a; 双栈&#xff1a;要求网络中所有设备均同时支持IPv4和IPv6转换&#xff1a;转换这种方式将IPv6协议的报头转换成IPv4协议报头。隧道&#xff1a;假定两个IPv6节点要使用IPv6…

redis---哨兵模式Sentinel

上次搭建了一主两从的Redis集群&#xff0c;来实现了一定程度上的高可用。相比一个单节点的Redis来说已经有了很大的提升。 但是这个集群还是有一些问题的&#xff0c;主节点宕机了&#xff0c;我们还是需要手动去把另一台从节点提升为主节点&#xff0c;这样就不能实现真正的…

JDK、JRE和JDK的关系

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a;每天一个知识点 ✨特色专栏&#xff1a…

【考研经验贴】24考研860软件工程佛系上岸经验分享【丰富简历、初复试攻略、导师志愿、资料汇总】

&#x1f60a;你好&#xff0c;我是小航&#xff0c;一个正在变秃、变强的文艺倾年。 &#x1f514;本文讲解24考研860软件工程佛系上岸经验分享【丰富简历、初复试攻略、导师志愿、资料汇总】&#xff0c;期待与你一同探索、学习、进步&#xff0c;一起卷起来叭&#xff01; 目…

《YOLOv8:从入门到实战》专栏介绍 专栏目录

&#x1f31f;YOLOv8&#xff1a;从入门到实战 | 目录 | 使用教程&#x1f31f; 本专栏涵盖了丰富的YOLOv8基础知识源码解析入门实践算法改进项目实战系列教程&#xff0c;专为学习YOLOv8的同学而设计&#xff0c;堪称全网最详细的教程&#xff01;该专栏针对YOLOv8内容的学习…

蓝桥杯2015年第十三届省赛真题-三羊献瑞

一、题目 观察下面的加法算式&#xff1a; 祥 瑞 生 辉 三 羊 献 瑞 ---------------------- 三 羊 生 瑞 气 (如果有对齐问题&#xff0c;可以参看【图1】) 其中&#xff0c;相同的汉字代表相同的数字&#xff0c;不同的汉字代表不同的数字。 请你填写“三羊献瑞”所…

AcWing-游戏

1388. 游戏 - AcWing题库 所需知识&#xff1a;博弈论&#xff0c;区间dp 由于双方都采取最优的策略来取数字&#xff0c;所以结果为确定的&#xff0c;有可能会有多个不同的过程&#xff0c;但是我们只需要关注最终结果就行了。 方法一&#xff1a; 定义dp[i][j] 表示区间…

【Pt】马灯贴图绘制过程 05-铁丝与渲染出图

目录 效果 步骤 一、基本材质 二、浮尘 三、渲染 效果 步骤 一、基本材质 CtrlAlt鼠标右键选中指定的纹理集 在智能材质中将“Iron Forged Old”加入图层 将智能材质“Iron Forged Old”文件夹打开&#xff0c;将图层“Base”和“Edge”的基本颜色改暗一点 二、浮尘 新…

解锁行业潜力:国内十大低代码平台全面盘点

在数字化转型的浪潮中&#xff0c;低代码开发平台以其快速开发、简化流程和降低技术门槛的优势&#xff0c;成为企业信息化建设的重要推手。 本篇文章将为您盘点十个低代码平台有&#xff1a;Zoho Creator、明道云、腾讯云低代码平台、华为云Astro、金蝶云苍穹、用友YonBuilder…

VS Code 配置 cmake

手动添加 CMake 编译器的搜索路径 如果没有设置上面的路径&#xff0c;有些编译器是找不到的

兼顾性能的数据倾斜处理方案

目录 前言 一、场景描述 二、常见的优化方法 2.1 Mapjoin 2.2 特殊值/空值打散 2.3 热点值打散&#xff0c;副表呈倍数扩散 2.4 热点数据单独处理/SkewJoin 2.5 方案总结 三、Distmapjoin 3.1 核心思路 3.2 代码实现 3.3 真实效果 四、方案总结 文章主要是介绍在支…

使用自己训练的superpoint与superglue模型进行图像配准

基于官方团队发布的预训练模型&#xff0c;使用SuperPoint与SuperGlue实现图像配准&#xff0c;可以参考https://blog.csdn.net/a486259/article/details/129093084 基于官方团队发布的代码训练自己的模型&#xff0c;可以参考https://blog.csdn.net/a486259/article/details/…

xilinx原语详解及仿真——ISERDESE2

前面在讲解HDMI接口之前&#xff0c;讲解过IDDR、ODDR、OSERDESE2、IBUFDS等原语&#xff0c;之后一直有读者在问什么时候更新ISERDESE2这个原语。前文讲解过这些原语都在HDMI或者RGMII中使用过&#xff0c;但是ISERDESE2这个原语目前我的板子除了HDMI输入&#xff0c;其余并不…