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

透析跳跃游戏

关卡名

理解与贪心有关的高频问题

我会了✔️

内容

1.理解跳跃游戏问题如何判断是否能到达终点

✔️

2.如果能到终点,如何确定最少跳跃次数

✔️

1. 跳跃游戏 

leetCode 55 给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度,判断你是否能够到达最后一个位置。

示例1:

输入: [2,3,1,1,4]

输出: true

解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例2:

输入: [3,2,1,0,4]

输出: false

解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ,所以你永远不可能到达最后一个位置。

如果当前位置元素如果是3,我究竟是跳几步呢,一步,两步,还是三步?这里的关键是判断能否到达终点,不用每一步跳跃到哪个位置,而是尽可能的跳跃到最远的位置,看最多能覆盖到哪里,只要不断更新能覆盖的距离,最后能覆盖到末尾就行了。

 

例如上面的第一个例子,3能覆盖的范围是后面的{2,1,0},2接下来能覆盖后面的{1,0},而1只能覆盖到{0},所以无法到达4。
而第二组序列,2能覆盖{3,1},3可以覆盖后面的{1,1,4},已经找到一条路了。1只能到下一个1,下一个1能到4,所以这里有{2,1,1,4}和{2,3,1,1,4}两种走法,加起来有3种跳法。
我们可以定义一个cover表示最远能够到达的方位,也就是i每次移动只能在其cover的范围内移动,每移动一次,cover得到该元素数值(新的覆盖范围)的补充,让i继续移动下去。而cover每次按照下面的结果判断。如果cover大于等于了终点下标,直接return true就可以了:
cover= max(该元素数值补充后的范围, cover本身范围)
针对上图的两个序列再解释一下:
1.在第二个图中,第一个元素,nums[0]=2,此时conver=2能覆盖到{3,1}两个元素。
2.继续,第二个元素nums[1]=3,此时能继续覆盖的范围就是1+3,能覆盖{1,1,4}三个位置。此时cover=2,而”该元素数值补充后的范围“是1+3=4,所以新的conver=max{4,2},此时就是cover>=nums.length-1。
其他情况都可以使用类似的方式来判断 ,所以代码就是:

public boolean canJump(int[] nums) {if (nums.length == 1) {return true;}//覆盖范围, 初始覆盖范围应该是0,因为下面的迭代是从下标0开始的int cover = 0;//在覆盖范围内更新最大的覆盖范围for (int i = 0; i <= cover; i++) {cover = Math.max(cover, i + nums[i]);if (cover >= nums.length - 1) {return true;}}return false;
}

这道题目的难点是要想到覆盖范围,而不用拘泥于每次究竟跳几步,覆盖范围是可以逐步扩展的,只有能覆盖就一定是可以跳过来的,不用管是怎么跳的。

2 最短跳跃游戏

在上题再进一步,假设一定能到达末尾,然后让你求最少到达的步数该怎么办呢?这就是LeetCode45上面的例子。可以看到,有三种走法{2,3,4}、{2,1,1,4}和{2,3,1,1,4},那这时候该怎么办呢?
具体该怎么实现呢?网上有很多解释,代码也基本雷同,而且也很明显是将上一题的代码修改了一下,但是难在不好理解,我现在给一个比较好理解的方式:贪心+双指针。
我们重新观察一下结构图,为了便于分析,我们修改一下元素序列,我们需要四个变量:

  • left用来一步步遍历数组
  • steps用来记录到达当前位置的最少步数
  • right表示当前步数下能够覆盖到的最大范围
  • 我们还需要一个临时变量conver,假如left到达right时才更新right

在这个图中,开始的元素是 2,如果只走一步,step=1,可跳的范围是{3,1}。也就是如果只走一步,最远只能到达1,此时conver=nums[0]=2,因此我们用right=nums[2]来保存这个位置,这表示的就是走一步最远只能到nums[2]。
接下来,我们必须再走一步,step=2,如下图,此时可选元素是{3,1}, 3能让我们到达的距离是left+nums[left]=1+3=4,而1能让我们到达的位置是left+nums[left]=2+1=3,而所以我们获得最远覆盖距离conver=4 。

然后用left和right将step=2的范围标记一下:

 此时还没有到终点,我们要继续走,在这里我们可选择的元素是{2,4},如果选择2,则可以到达left+nums[left]=3+2=5,如果选择4则是left+nums[left]=4+4=8,已经超越边界了,所以此时一定将末尾覆盖了。

这样我们就知道最少需要走3次。
这个过程怎么用代码表示呢?看代码:

public int jump(int[] nums) {int right = 0;int maxPosition = 0;int steps = 0;for(int left=0;i<nums.length;left++){//找能跳的最远的maxPosition = Math.max(maxPosition,nums[left]+left);if(left==right){ //遇到边界,就更新边界,并且步数加一right = maxPosition;steps++;}//right指针到达末尾了。if (right >= nums.length - 1) {return steps;}}return steps;
}

相关文章:

透析跳跃游戏

关卡名 理解与贪心有关的高频问题 我会了✔️ 内容 1.理解跳跃游戏问题如何判断是否能到达终点 ✔️ 2.如果能到终点&#xff0c;如何确定最少跳跃次数 ✔️ 1. 跳跃游戏 leetCode 55 给定一个非负整数数组&#xff0c;你最初位于数组的第一个位置。数组中的每个元素代表…...

贵州开放大学形成性考核 平时作业 参考试题

试卷代号&#xff1a;1310 古代汉语专题 参考试题&#xff08;开卷&#xff09; 一、单项选择题&#xff08;每题3分&#xff0c;共10题30分&#xff09; 1.“六书”的具体类别名称始见于( )。 A.《汉书艺文志》 B.《说文解字》 C.《周礼》 2.汉字的…...

Leetcode 2962. Count Subarrays Where Max Element Appears at Least K Times

Leetcode 2962. Count Subarrays Where Max Element Appears at Least K Times 1. 解题思路2. 代码实现 题目链接&#xff1a;2962. Count Subarrays Where Max Element Appears at Least K Times 1. 解题思路 这一题思路上同样很直接&#xff0c;就是找到最大的元素所在的全…...

Mybatis XML 配置文件

我们刚开始就有说Mybatis 的开发有两种方式: 1.注释 2.XML 注解和 XML 的方式是可以共存的 我们前面说的都是注释的方式,接下来是XML方式 XML的方式分为三步 : 1.配置数据库(配在 application.yml 里面) 这个跟注释的配置是一样的,username应该都是一样的,password记得写…...

CCF计算机软件能力认证202309-1坐标变换(其一)(C语言)

ccf-csp计算机软件能力认证202309-1坐标变换&#xff08;其一&#xff09;(C语言版) 题目内容&#xff1a; 问题描述 输入格式 输出格式 样例输入 3 2 10 10 0 0 10 -20 1 -1 0 0样例输出 21 -11 20 -10样例解释 评测用例规模与约定 解题思路 1.第一步分析问题&…...

k8s 如何部署Mysql(史上最权威教程)?

Kuboard K8s 部署Mysql5.7-8.x版本 部署Mysql5.7 在 Kuboard 界面进入名称空间 &#xff08;自己的命令空间&#xff09;&#xff0c;点击 创建工作负载 按钮&#xff0c;并填写表单&#xff0c;如下图所示&#xff1a; 字段名称填写内容工作负载类型有状态副本集&#xff0…...

红队攻防实战之Redis-RCE集锦

心若有所向往&#xff0c;何惧道阻且长 Redis写入SSH公钥实现RCE 之前进行端口扫描时发现该机器开着6379&#xff0c;尝试Redis弱口令或未授权访问 尝试进行连接Redis&#xff0c;连接成功&#xff0c;存在未授权访问 尝试写入SSH公钥 设置redis的备份路径 设置保存文件名 …...

六级翻译之印章

好像大房子挺难得 三段式 1Since ancient from now&#xff0c;seals have been a symbol of power and certerfiction of identity.seals not only practical but also is a form of art.Seal is an ancient art combining with manafutuer of crafting and desgin of…...

PHP数据库操作实例 - 学生信息管理

文章目录 一、启动Apache与MySQL服务二、创建数据库与表(一)创建数据库(二)创建表并插入记录三、项目实现步骤(一)创建项目(二)创建学生类(二)获取数据库连接(三)学生数据访问对象(四)创建功能页面1、按学号查询学生页面2、处理按学号查找学生记录页面3、插入学生…...

企业架构LB-服务器的负载均衡之LVS实现

企业架构LB-服务器的负载均衡之LVS实现 学习目标和内容 1、能够了解LVS的基本工作方式 2、能够安装配置LVS实现负载均衡 3、能够了解LVS-NAT的配置方式 4、能够了解LVS-DR的配置方式 #一、LVS介绍和安装 LVS&#xff08;Linux Virtual Server&#xff09;即Linux虚拟服务器&…...

Java程序设计基础 - 课程概述

文章目录 一、程序员最具共性的心理特征二、Java开发工程师的岗位要求(一)素质和职业道德需求(二)岗位能力需求统计三、针对Java工程师岗位需求的课程目标(一)熟练掌握Java编程语言,掌握编程技能(二)精通使用集成开发工具Eclipse或IntelliJ IDEA(三)需要将“用户体验…...

基于SpringBoot+Vue前后端分离的商城管理系统(Java毕业设计)

大家好&#xff0c;我是DeBug&#xff0c;很高兴你能来阅读&#xff01;作为一名热爱编程的程序员&#xff0c;我希望通过这些教学笔记与大家分享我的编程经验和知识。在这里&#xff0c;我将会结合实际项目经验&#xff0c;分享编程技巧、最佳实践以及解决问题的方法。无论你是…...

vue3中实现el-tree通过ctrl或shift批量选择节点并高亮展示

一、看效果&#xff1a; 按住ctrl键实现单个多选 按住shift实现区间范围多选 二、代码&#xff1a; vue页面 <template><el-treeclass"w100%":data"$.treeData"ref"treeTab…...

HarmonyOS 振动效果开发指导

Vibrator 开发概述 振动器模块服务最大化开放硬工最新马达器件能力&#xff0c;通过拓展原生马达服务实现振动与交互融合设计&#xff0c;打造细腻精致的一体化振动体验和差异化体验&#xff0c;提升用户交互效率和易用性、提升用户体验、增强品牌竞争力。 运作机制 Vibrato…...

【ACM独立出版、确定的ISBN号】第三届密码学、网络安全和通信技术国际会议(CNSCT 2024)

第三届密码学、网络安全和通信技术国际会议&#xff08;CNSCT 2024&#xff09; 2024 3rd International Conference on Cryptography, Network Security and Communication Technology 随着互联网和网络应用的不断发展&#xff0c;网络安全在计算机科学中的地位越来越重要&…...

Qt12.8

使用手动连接&#xff0c;将登录框中的取消按钮使用qt4版本的连接到自定义的槽函数中&#xff0c;在自定义的槽函数中调用关闭函数 将登录按钮使用qt5版本的连接到自定义的槽函数中&#xff0c;在槽函数中判断ui界面上输入的账号是否为"admin"&#xff0c;密码是否为…...

QT使用SQLite 超详细(增删改查、包括对大量数据快速存储和更新)

QTSQLite 在QT中使用sqlite数据库&#xff0c;有多种使用方法&#xff0c;在这里我只提供几种简单&#xff0c;代码简短的方法&#xff0c;包括一些特殊字符处理。在这里也给大家说明一下&#xff0c;如果你每次要存储的数据量很大&#xff0c;建议使用事务&#xff08;代码中…...

基于Springboot+mybatis+mysql+jsp招聘网站

基于Springbootmybatismysqljsp招聘网站 一、系统介绍二、功能展示四、其他系统实现五、获取源码 一、系统介绍 项目类型&#xff1a;Java EE项目 项目名称&#xff1a;基于SPringBoot的照片网站 项目架构&#xff1a;B/S架构 开发语言&#xff1a;Java语言 前端技术&…...

PHP介绍及安装

一、PHP语言介绍 1. PHP是一种用于创建动态交互性网站的服务器端脚本语言。PHP文件通常包含HTML标签和一些PHP脚本代码,这些PHP代码可以放置在文档的任意位置。 2. PHP文件是什么 PHP文件是一种包含有效的HTML、JavaScript代码和PHP代码的文件。PHP代码在服务器上执行,并将…...

linux C++监听管道文件方式

方式一&#xff08;传统读取文件&#xff0c;一直监听循环读取文件&#xff09; 非阻塞打开文件&#xff0c;用read循环定时读取&#xff0c;性能不好 代码如下&#xff1a; #include <iostream> #include <fstream> #include <functional> #include <…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

Unity中的transform.up

2025年6月8日&#xff0c;周日下午 在Unity中&#xff0c;transform.up是Transform组件的一个属性&#xff0c;表示游戏对象在世界空间中的“上”方向&#xff08;Y轴正方向&#xff09;&#xff0c;且会随对象旋转动态变化。以下是关键点解析&#xff1a; 基本定义 transfor…...