透析跳跃游戏
| 关卡名 | 理解与贪心有关的高频问题 | 我会了✔️ |
| 内容 | 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.如果能到终点,如何确定最少跳跃次数 ✔️ 1. 跳跃游戏 leetCode 55 给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表…...
贵州开放大学形成性考核 平时作业 参考试题
试卷代号:1310 古代汉语专题 参考试题(开卷) 一、单项选择题(每题3分,共10题30分) 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. 代码实现 题目链接:2962. Count Subarrays Where Max Element Appears at Least K Times 1. 解题思路 这一题思路上同样很直接,就是找到最大的元素所在的全…...
Mybatis XML 配置文件
我们刚开始就有说Mybatis 的开发有两种方式: 1.注释 2.XML 注解和 XML 的方式是可以共存的 我们前面说的都是注释的方式,接下来是XML方式 XML的方式分为三步 : 1.配置数据库(配在 application.yml 里面) 这个跟注释的配置是一样的,username应该都是一样的,password记得写…...
CCF计算机软件能力认证202309-1坐标变换(其一)(C语言)
ccf-csp计算机软件能力认证202309-1坐标变换(其一)(C语言版) 题目内容: 问题描述 输入格式 输出格式 样例输入 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 界面进入名称空间 (自己的命令空间),点击 创建工作负载 按钮,并填写表单,如下图所示: 字段名称填写内容工作负载类型有状态副本集࿰…...
红队攻防实战之Redis-RCE集锦
心若有所向往,何惧道阻且长 Redis写入SSH公钥实现RCE 之前进行端口扫描时发现该机器开着6379,尝试Redis弱口令或未授权访问 尝试进行连接Redis,连接成功,存在未授权访问 尝试写入SSH公钥 设置redis的备份路径 设置保存文件名 …...
六级翻译之印章
好像大房子挺难得 三段式 1Since ancient from now,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(Linux Virtual Server)即Linux虚拟服务器&…...
Java程序设计基础 - 课程概述
文章目录 一、程序员最具共性的心理特征二、Java开发工程师的岗位要求(一)素质和职业道德需求(二)岗位能力需求统计三、针对Java工程师岗位需求的课程目标(一)熟练掌握Java编程语言,掌握编程技能(二)精通使用集成开发工具Eclipse或IntelliJ IDEA(三)需要将“用户体验…...
基于SpringBoot+Vue前后端分离的商城管理系统(Java毕业设计)
大家好,我是DeBug,很高兴你能来阅读!作为一名热爱编程的程序员,我希望通过这些教学笔记与大家分享我的编程经验和知识。在这里,我将会结合实际项目经验,分享编程技巧、最佳实践以及解决问题的方法。无论你是…...
vue3中实现el-tree通过ctrl或shift批量选择节点并高亮展示
一、看效果: 按住ctrl键实现单个多选 按住shift实现区间范围多选 二、代码: vue页面 <template><el-treeclass"w100%":data"$.treeData"ref"treeTab…...
HarmonyOS 振动效果开发指导
Vibrator 开发概述 振动器模块服务最大化开放硬工最新马达器件能力,通过拓展原生马达服务实现振动与交互融合设计,打造细腻精致的一体化振动体验和差异化体验,提升用户交互效率和易用性、提升用户体验、增强品牌竞争力。 运作机制 Vibrato…...
【ACM独立出版、确定的ISBN号】第三届密码学、网络安全和通信技术国际会议(CNSCT 2024)
第三届密码学、网络安全和通信技术国际会议(CNSCT 2024) 2024 3rd International Conference on Cryptography, Network Security and Communication Technology 随着互联网和网络应用的不断发展,网络安全在计算机科学中的地位越来越重要&…...
Qt12.8
使用手动连接,将登录框中的取消按钮使用qt4版本的连接到自定义的槽函数中,在自定义的槽函数中调用关闭函数 将登录按钮使用qt5版本的连接到自定义的槽函数中,在槽函数中判断ui界面上输入的账号是否为"admin",密码是否为…...
QT使用SQLite 超详细(增删改查、包括对大量数据快速存储和更新)
QTSQLite 在QT中使用sqlite数据库,有多种使用方法,在这里我只提供几种简单,代码简短的方法,包括一些特殊字符处理。在这里也给大家说明一下,如果你每次要存储的数据量很大,建议使用事务(代码中…...
基于Springboot+mybatis+mysql+jsp招聘网站
基于Springbootmybatismysqljsp招聘网站 一、系统介绍二、功能展示四、其他系统实现五、获取源码 一、系统介绍 项目类型:Java EE项目 项目名称:基于SPringBoot的照片网站 项目架构:B/S架构 开发语言:Java语言 前端技术&…...
PHP介绍及安装
一、PHP语言介绍 1. PHP是一种用于创建动态交互性网站的服务器端脚本语言。PHP文件通常包含HTML标签和一些PHP脚本代码,这些PHP代码可以放置在文档的任意位置。 2. PHP文件是什么 PHP文件是一种包含有效的HTML、JavaScript代码和PHP代码的文件。PHP代码在服务器上执行,并将…...
linux C++监听管道文件方式
方式一(传统读取文件,一直监听循环读取文件) 非阻塞打开文件,用read循环定时读取,性能不好 代码如下: #include <iostream> #include <fstream> #include <functional> #include <…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
Bean 作用域有哪些?如何答出技术深度?
导语: Spring 面试绕不开 Bean 的作用域问题,这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开,结合典型面试题及实战场景,帮你厘清重点,打破模板式回答,…...
AD学习(3)
1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分: (1)PCB焊盘:表层的铜 ,top层的铜 (2)管脚序号:用来关联原理图中的管脚的序号,原理图的序号需要和PCB封装一一…...
RushDB开源程序 是现代应用程序和 AI 的即时数据库。建立在 Neo4j 之上
一、软件介绍 文末提供程序和源码下载 RushDB 改变了您处理图形数据的方式 — 不需要 Schema,不需要复杂的查询,只需推送数据即可。 二、Key Features ✨ 主要特点 Instant Setup: Be productive in seconds, not days 即时设置 :在几秒钟…...
