每日一题:跳跃游戏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 <= 10^{4}
  • 0 <= nums[i] <= 1000
  • 题目保证可以到达 nums[n-1]

分解题目:

  • 目标:求解跳到最后一个位置的最小跳跃数
  • 依赖于:存在一个位置能跳到最后一个位置(题目已经保证此项)
                  跳到这个位置的最小跳跃数。
  • 如果用 i 来表示最后一次跳跃,i - 1表示的倒数第二次跳跃,很明显,求解 i 的最小跳跃数可以转换为求解 i - 1的最小跳跃数。

至此,可以用动态规划进行解决。

定义:dp[ i ]表示跳跃到第 i 个位置的最小跳跃数。dp[n - 1]即为所求,边界值dp[0] = 0。

对于第 i 个位置,可能有多个前置的位置可以跳跃到达,我们需要找到其中的最小值,即:

j from 0 to i
if(nums[j]+j>i)  dp[i]=min(dp[i],dp[j]+1); 

完整代码:

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n,n);
        dp[0] = 0;
        for(int i = 1;i < n;++i){
            for(int j = 0; j < i;++j){
                if(nums[j] + j >= i){
                    dp[i] = min(dp[i],dp[j] + 1);
                }
            } 
        }
        return dp[n-1];
    }
};

然而这里的动态规划反而引入了更多的重复计算。

如果换成贪心算法:

class Solution {
public:
    int jump(vector<int>& nums) {
        int jumps = 0;
        int end = 0;
        int farthest = 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            farthest = max(farthest, nums[i] + i);
            if (i == end) {
                jumps++;
                end = farthest;
                if (end >= nums.size() - 1) {
                    break;
                }
            }
        }
    return jumps;
    }
};
  • jumps是跳跃的次数,end是当前的终点,farthest是当前点跳跃能够到达的最远点。
  • 遍历数组,除了最后一个元素,因为最后一个元素的位置不需要跳跃,自己就能到达自己。
  • 我们时刻维护从当前点到达的最远距离,当我们到达了当前终点,就把最远距离设置成终点,这里体现贪心的思想。
  • 同时,当到达了end时,也说明需要进行一次跳跃。

即:每次在上次能跳到的范围(i,end)内选择一个能跳的最远的位置(也就是能跳到farthest位置的点)作为下次的起跳点。

对于初学者,这看上去非常的反直觉,这是不是局部最优?为什么是全局最优?如果出现当前跳的最远,但是下下步跳得近了怎么办?

这里需要理解end的作用,如果把end抽象成一个分隔符,所谓跳跃过程就是在数组内插入分隔符的过程,使最终分出的子数组数量最小。

而fareset的作用是,保留上一个end到当前end这个区间范围内可以达到的最远值。

注意区间范围这个点。

在贪心算法中,每一步的end都是当前范围能到达的最远点,也即最大值farest,所以最终分出的间隔就会更少。

下面用一个具体图例做进一步解释,初始状态,进行第一次跳跃:

 跳跃后在区间内遍历维护最远值farest:

这里有人可能会说,看起来像恰好1就跳到了较大值10。那如果我们把这里的1换成0会发生什么?

可以看到维护的farest,才是起到关键作用的值。和nums[end]中的值并无全部关系。 这也是上面提到的,保留上一个end到当前end这个区间范围内可以达到的最远值。

图中箭头描述的是end变化的过程,真实的跳跃过程和end的变化过程数量相同,但是路径不一定相同。(每条end箭头仅对应一条跳跃,比如这里是从2跳到3跳到10。)

继续遍历:

只要理解了end表示间隔且和真实跳跃一一对应,farest表示一个区间内跳到的最远距离这两个概念,这里的贪心算法就很好理解了。

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

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

相关文章

YOLOv3没有比这详细的了吧

YOLOv3&#xff1a;目标检测基于YOLOv2的改进 在目标检测领域&#xff0c;YOLO&#xff08;You Only Look Once&#xff09;系列以其出色的性能和速度而闻名。YOLOv3作为该系列的第三个版本&#xff0c;不仅继承了前身YOLOv2的优势&#xff0c;还在多个方面进行了创新和改进。…

机器学习理论基础—支持向量机的推导(一)

机器学习理论基础—支持向量机的推导 算法原理 SVM:从几何角度&#xff0c;对于线性可分数据集&#xff0c;支持向量机就是找距离正负样本都最远的超平面&#xff0c;相比于感知机&#xff0c;其解是唯一的&#xff0c;且不偏不倚&#xff0c;泛化性能更好。 超平面 n维空间…

如何拿取 macOS 系统中的图标文件

如何拿取 macOS 系统中的图标文件 比如在 Finder 中看到这个文件夹图标很好看&#xff0c;想用一下&#xff0c;就是不知道它在什么位置&#xff0c;我来告诉你。 它在系统中的位置是 /System/Library/CoreServices/CoreTypes.bundle/Contents/Resources/如何打开这个位置&am…

计算机网络物理层思维导图+大纲笔记

大纲笔记&#xff1a; 物理层的基本概念 解决如何在连接各种计算机的传输媒体上传输数据比特流&#xff0c;而不是具体的传输媒体 主要任务 确定与传输媒体接口有关的一些特性 机械特性 电气特性 功能特性 规程特性信道上传送的信号 基带信号 来自信源的信号&#xff0c;直接表…

【CLI命令行接口和Java连接openLooKeng查询数据 】

CLI命令行接口和Java连接openLooKeng查询数据 一、摘要二、正文0. 环境说明1. CLI命令行工具的使用2. Java API 的使用三、小结一、摘要 通过CLI命令行接口工具连接openLooKeng,可帮助初学者能够使用SQL语句的方式快速操作openLooKeng,任何只要熟悉SQL的人都可以快速切换到op…

解决 uniapp uni.getLocation 定位经纬度不准问题

【问题描述】 直接使用uni.getLocation获取经纬度不准确&#xff0c;有几百米的偏移。 【解决办法】 加偏移量 //加偏移 let x longitude let y latitude let x_pi (3.14159265358979324 * 3000.0) / 180.0 let z Math.sqrt(x * x y * y) 0.00002 * Math.sin(y * x_pi)…

ArcGIS Pro专题地图系列教程

专题地图系列是ArcGIS Pro3.2的新功能。之前&#xff0c;如果要做8张相同区域的专题图&#xff0c;可能需要新建8个布局&#xff0c;分别进行排版&#xff0c;再导出。现在&#xff0c;一幅地图&#xff0c;一个布局&#xff0c;就可以完成这个流程。 原理是&#xff0c;根据单…

Swift-24-集合对象

概述 在了解正式内容之前可以先回顾下objectiveC中提供的集合特性。 它的特点是&#xff0c;拿NSArray举例&#xff0c;包含NSArray 和 NSMutableArray两个API&#xff0c;前者是不可变数组&#xff0c;一旦创建其值和数量就不能改变了&#xff1b;NSMutableArray是可变数组&…

tableau基础学习——添加标靶图、甘特图、瀑布图

标靶图 添加参考线 添加参考分布 甘特图 创建新的字段 如设置延迟天数****计划交货日期-实际交货日期 为正代表提前交货&#xff0c;负则代表延迟交货 步骤&#xff1a;创建——计算新字段 把延迟天数放在颜色、大小里面就可以 瀑布图 两个表按照地区连接 先做个条形图&…

工业4.0的基石:探索工业级光模块的力量

引言 工业4.0代表着智能制造的新时代&#xff0c;而工业级光模块则是这一革命性转变的基石。这些高科技组件不仅是现代通信网络的核心&#xff0c;更是连接智能工厂、智慧城市和远程服务的关键。本文将深入探讨工业级光模块的技术特性、应用领域以及它们如何塑造未来工业的面貌…

公司网页制作需要多少钱

公司网页制作需要多少钱&#xff1f;这是一个非常常见的问题。答案取决于您需要的功能和设计。一些小型企业网站可能只需要一些基本的功能&#xff0c;花费可能低至几百美元&#xff0c;而一些大型企业网站可能需要高级功能和设计&#xff0c;可能需要几万美元。 以下是一些考虑…

js如何获取对象的属性值

获取对象的属性值&#xff0c;有两种方式。 方式一&#xff1a; 对象.属性名 let obj {name:张三,age:23 }; console.log(obj.name); //张三方式二&#xff1a; 对象[属性名] let obj {name:张三,age:23 }; console.log(obj[name]); //张三 两种方式有什么不同&am…

Mac安装telnet

一、安装Homebrew 1、打开官网&#xff1a;Homebrew — The Missing Package Manager for macOS (or Linux) 2、打开终端输入&#xff1a; /usr/bin/ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)" 二、安装Telnet bre…

内容策略的精准定位:Kompas.ai的目标受众分析

在这个信息爆炸的时代&#xff0c;内容营销已经成为品牌与消费者沟通的重要桥梁。然而&#xff0c;随着内容的海量增长&#xff0c;品牌如何从众多信息中脱颖而出&#xff0c;成为营销人员面临的巨大挑战。精准定位目标受众&#xff0c;不仅能够帮助品牌更有效地传达信息&#…

nginx 的漏洞改造

Nginx 的漏洞扫描有很多整改项 资源下载地址&#xff1a;https://download.csdn.net/download/wangzhi291/89216805 资源里面需要conf/modules 需要上传 然后docker镜像文件 配置按下面的修改就行了 整改方法为增加 ngx_http_headers_more_filter_module模块 include /usr…

贪吃蛇详解

Win32 API介绍&#xff1a; 在写贪吃蛇这款游戏时需要用到一些有关Win32 API的知识&#xff0c; 接下来我会将设计到的知识点列举并讲解&#xff1a; 首先我们先了解一下Win32 API是什么&#xff0c;Windows这个多作业系统除了协调应⽤程序的执⾏、分配内存、管理资源之外&am…

Unity射线实现碰撞检测(不需要rigbody组件)

使用physic.CapsulCast&#xff08;&#xff09;&#xff1b; 前面3个参数生成一个胶囊体&#xff0c; 向着发射方向&#xff0c;发射出一串的胶囊&#xff08;没有最大距离&#xff09; 有最大距离&#xff0c;可以节约性能开销。 physic.CapsulCast&#xff08;&#xff0…

类的六个构造函数相关干货

构造函数 特点 1.名字与类名相同 2.无返回值 3.对象实例化的时候编译器自动调用这个函数 4.构造函数可以重载&#xff08;无参构造函数&#xff0c;拷贝构造等&#xff09; 5.如果类中没有显式定义构造函数&#xff08;深拷贝&#xff09;&#xff0c;则编译器会自动生成一个…

IP地址查询API接口怎么对接

IP地址查询API接口又叫IP归属地信息查询API接口&#xff0c;指的是根据IP地址查询归属地定位信息&#xff0c;包含国家、省、市、街道和运营商、区号、邮编、坐标等信息。那么IP地址查询API接口该怎么对接呢&#xff1f; 首先我们找到一家有做IP归属地信息查询API接口的服务商…

Python程序设计教案

文章目录&#xff1a; 一&#xff1a;软件环境安装 第一个软件&#xff1a;pycharm 第二个软件&#xff1a;thonny 第三个软件&#xff1a;IDIE&#xff08;自带的集成开发环境&#xff09; 二&#xff1a;相关 1.规范 2.关键字 3.Ascll码表 三&#xff1a;语法基础…