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

算法通过村第十七关-贪心|黄金笔记|跳跃游戏

文章目录

  • 前言
  • 跳跃游戏
  • 最短跳跃游戏
  • 总结


前言


提示:曾走过山,走过水,其实只是借助他们走过我的生命;我看着天,看着地,其实只是借助它们确定我的位置;我爱这她,爱着你,其实只不过借助别人实现了我的爱欲。 --史铁生《务虚笔记》

跳跃问题也是常考的类型之一,这里务必学习以下,我们就接着往下看。

💕😎💡⭐🥰🌰😭😥😒💣❔😂🤩👌👍🤖✅🤔

跳跃游戏

参考题目地址:55. 跳跃游戏 - 力扣(LeetCode)

在这里插入图片描述

在这里插入图片描述
如果当前位置元素如果是3,我究竟是要跳几步呢?其实这不是考虑的重点,关键在于是否最终可以到达重点,而不是每一步跳到哪里,而是尽可能的跳跃到最远的位置,看看最多的可以覆盖到哪里,只要不断更新覆盖的距离没最终覆盖到结尾就可以了。

在这里插入图片描述
从上图可以看出:

第一组:

3可以覆盖到{2,1,0},2可以覆盖到{1,0},1可以覆盖到{0},最终无法达到4.

第二组:

2可以覆盖到{3,1},3可以覆盖到{1,1,4},1可以覆盖到{1},1可以覆盖到{4}.到达终点。可达路径有

3条,{2,1,1 ,4}和{2,3,1,1,4}两种走法。

我们可以定义一个cover表示最远可以到达的方位,也就是i每次移动只能在cover的范围内移动,每次一档,cover得到该元素的值(新的覆盖范围)的补充,让i继续移动下去,儿cover每次按照下面的结果判断,如果cover大于等于最终下标直接返回true就可以了。

cover = max(该元素可以覆盖到的范围,该元素数值补充后的范围)

针对这个判断:我们再看下序列图:

第二组数据:

nums[0] = 2,此时cover = 2 能覆盖到{3.1}两个元素。

继续第二个元素,nums[1] = 3,此时能继续覆盖的范围就是1 + 3 ,可以覆盖到{1,1,4}三个位置,此时cover = 2,而该元素数值的补充后的范围值1 + 3 = 4,所以新的cover = max{4,2}.当然在这里已经可以结束了,cover >= nums.length- 1.

其他的情况也是如此,我们看下代码实现:

    /*** 跳跃游戏* @param nums* @return*/public static 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;}

这个题目,如果你想到采用覆盖范围这个想法,我想解决不是难事,这里就是转换一下。

最短跳跃游戏

参考题目地址:45. 跳跃游戏 II - 力扣(LeetCode)

在这里插入图片描述
在这里插入图片描述
这是上一道题目的进阶版,假设一定到达末尾,求最短步数。就拿上图的3种走法,我们怎么选出最短的那个呢?

这里采用骨头哥的:贪婪+双指针

在上一题的基础上做改进,这里准备4个变量。

  1. left用来一步步遍历数组
  2. steps用来记录到达当前位置的最少步数
  3. right表示当前步数下能够覆盖到的最大范围
  4. 我们还需要一个临时变量cover,假如left到达right时才更新right。
    在这里插入图片描述

此时还么有达到终点,我们需要继续走,这是可以选择的元素是{2,4},如果选择2,则可以到达left+num[left]=3 + 2 = 5,如果选择4,则是left+num[left]=4 +8= 8,此时以已经过界了,一定可以覆盖到结尾的。
在这里插入图片描述
然后用left和right将step的范围标记一下:
在这里插入图片描述

此时还么有达到终点,我们需要继续走,这是可以选择的元素是{2,4},如果选择2,则可以到达left+num[left]=3 + 2 = 5,如果选择4,则是left+num[left]=4 +8= 8,此时以已经过界了,一定可以覆盖到结尾的。

在这里插入图片描述
也就是说,最后一定可以到达,至少需要走3步的。

看了这么多,代码要怎么写呢?

    /*** 跳跃游戏进阶* @param nums* @return*/public static int jump(int[] nums) {int step = 0;int maxPosition = 0;int right = 0;for(int left = 0; left < nums.length ; left++) {// 覆盖的最远距离maxPosition = Math.max(maxPosition, nums[left] + left);// 遇到边界,更新边界if (left == right){right = maxPosition;step++;}// 当然如果越界了,直接返回+1if (right >= nums.length - 1){return step;}}return step;}

总结

提示:贪婪算法;跳跃游戏;进阶游戏;跳跃问题;跳跃游戏进阶


如果有帮助到你,请给题解点个赞和收藏,让更多的人看到 ~ ("▔□▔)/

如有不理解的地方,欢迎你在评论区给我留言,我都会逐一回复 ~

也欢迎你 关注我 ,喜欢交朋友,喜欢一起探讨问题。

在这里插入图片描述

相关文章:

算法通过村第十七关-贪心|黄金笔记|跳跃游戏

文章目录 前言跳跃游戏最短跳跃游戏总结 前言 提示&#xff1a;曾走过山&#xff0c;走过水&#xff0c;其实只是借助他们走过我的生命&#xff1b;我看着天&#xff0c;看着地&#xff0c;其实只是借助它们确定我的位置&#xff1b;我爱这她&#xff0c;爱着你&#xff0c;其实…...

【精选】VMware部署ESXI6.5 vCenter Server详解

VMware部署ESXI6.5 vCenter Server 一、ESXi主机介绍1、虚拟机的好处2、为什么要使用虚拟机 二、虚拟化服务器概述1、VSphere物理架构2、体系架构3、VMware vSphere 组件 三、ESXi安装环境1、安装步骤2、使用VMware新建ESXi主机3、初始环境安装 四、创建虚拟机五、安装部署VMwa…...

如何借助数据集更好的评估NLP模型的性能?

随着信息时代的迅猛发展&#xff0c;每天有无数文本、声音、图片和视频不断涌入互联网。如何从海量数据中提炼有意义信息成为学术界和工业界迫切需要解决的问题。在此背景下&#xff0c;自然语言处理&#xff08;NLP&#xff09;应运而生&#xff0c;成为人工智能领域最为活跃的…...

2023年腾讯云服务器地域节点选择指南(亲自整理)

腾讯云轻量应用服务器地域是指轻量服务器数据中心所在的地理位置&#xff0c;如上海、广州和北京等地域&#xff0c;如何选择地域&#xff1f;腾讯云百科txybk.com建议地域选择遵循就近原则&#xff0c;用户距离轻量服务器地域越近&#xff0c;网络延迟越低&#xff0c;速度就越…...

华媒舍:日韩媒体发稿推广中8个关键因素帮助你实现突破

在当今经济全球化的时代背景下&#xff0c;日韩地域媒体影响力日益提高。对于需要在这一地区开展发稿推广的人来讲&#xff0c;掌握适度的思路和流程是十分重要的。下面我们就为大家介绍8个关键因素&#xff0c;以帮助你在日韩地域媒体发稿推广中实现突破。 1.科学研究行业在逐…...

Docker数据卷

目录 1.bind mount 2.docker managed volume 1.bind mount docker run -it --rm -v /tmp/data1:/data1 -v /tmp/data2:/data2:ro -v /etc/passwd:/mnt/passwd:ro busybox 2.docker managed volume docker run -d --name web1 webserver:v3 docker inspect web1 cd/var/lib/doc…...

LightGBM 的完整解释 - 最快的梯度提升模型

文章最前&#xff1a; 我是Octopus&#xff0c;这个名字来源于我的中文名--章鱼&#xff1b;我热爱编程、热爱算法、热爱开源。所有源码在我的个人github &#xff1b;这博客是记录我学习的点点滴滴&#xff0c;如果您对 Python、Java、AI、算法有兴趣&#xff0c;可以关注我的…...

Think-Queue3一直提示[Exception]redis扩展未安装

场景 tp6tq3实现的任务队列&#xff0c;使用redis作为数据驱动&#xff0c;目前是tp6可以正常使用redis了&#xff0c;但tq3不行&#xff0c;一直提示[Exception]redis扩展未安装。 解决思路 1.分析tq3源码 定位到是这一行出了问题 if (!extension_loaded(redis)) {throw n…...

Spring cloud教程Gateway服务网关

Spring cloud教程|Gateway服务网关 写在前面的话&#xff1a; 本笔记在参考网上视频以及博客的基础上&#xff0c;只做个人学习笔记&#xff0c;如有侵权&#xff0c;请联系删除&#xff0c;谢谢&#xff01; Spring Cloud Gateway 是 Spring Cloud 的一个全新项目&#xff0c;…...

【C++代码】爬楼梯,不同路径,整数拆分,不同搜索树,动态规划--代码随想录

动态规划&#xff0c;英文&#xff1a;Dynamic Programming&#xff0c;简称DP&#xff0c;如果某一问题有很多重叠子问题&#xff0c;使用动态规划是最有效的。所以动态规划中每一个状态一定是由上一个状态推导出来的&#xff0c;这一点就区分于贪心&#xff0c;贪心没有状态推…...

设计模式(单例模式、工厂模式及适配器模式、装饰器模式)

目录 0 、设计模式简介 一、单例模式 二、工厂模式 三、适配器模式 四、装饰器模式 0 、设计模式简介 设计模式可以分为以下三种: 创建型模式&#xff1a;用来描述 “如何创建对象”&#xff0c;它的主要特点是 “将对象的创建和使用分离”。包括单例、原型、工厂方法、…...

为wget命令设置代理

使用-e参数 wget本身没有专门设置代理的命令行参数&#xff0c;但是有一个"-e"参数&#xff0c;可以在命令行上指定一个原本出现在".wgetrc"中的设置。于是可以变相在命令行上指定代理&#xff1a; -e, --executeCOMMAND 执行.wgetrc格式的命令 例如&…...

【C++深入浅出】模版初识

目录 一. 前言 二. 泛型编程 三. 函数模版 3.1 函数模版的概念 3.2 函数模版的格式 3.3 函数模版的原理 3.4 函数模板的实例化 3.5 模板参数的匹配原则 四. 类模版 4.1 类模版的定义 4.2 类模版的实例化 一. 前言 本期我们要介绍的是C的又一大重要功能----模版。通…...

系统架构设计师-第18章-安全架构设计理论与实践-软考学习笔记

安全架构概述 信息的可用性、元略性、机密性、可控性和不可抵赖性等安全保障显得尤为重要&#xff0c;而满足这些诉求&#xff0c;离不开好的架构设计. 信息安全面临的威胁 常见的安全威胁有以下几种. (1)信息泄露 (2) 破坏信息的元整性: 数据被非授极地进行增删、修改成破坏…...

2023年吉安市“振兴杯”职业技能大赛网络安全项目样题

2023年吉安市“振兴杯”职业技能大赛 网络安全项目样题 需要竞赛环境可私信博主 赛题说明 一、竞赛项目简介 竞赛共分为&#xff1a;A.基础设施设置与安全加固&#xff1b;B.网络安全事件响应、数字取证调查和应用安全&#xff1b;C.CTF夺旗-攻击&#xff1b;D.CTF夺旗-防御等四…...

python爬虫selenium和ddddocr使用

python爬虫selenium和ddddocr使用 selenium使用 selenium实际上是web自动化测试工具&#xff0c;能够通过代码完全模拟人使用浏览器自动访问目标站点并操作来进行web测试。 通过pythonselenium结合来实现爬虫十分巧妙。 由于是模拟人的点击来操作&#xff0c;所以实际上被反…...

【vim 学习系列文章 12 -- vimrc 那点事】

文章目录 系统级及本地 vimrc 文件设置 vimrc 的路径 系统级及本地 vimrc 文件 当 Vim 启动时&#xff0c;编辑器会去搜索一个系统级的 vimrc 文件来进行系统范围内的默认初始化工作。 这个文件通常在你系统里 $VIM/vimrc 的路径下&#xff0c;如果没在那里&#xff0c;那你可…...

spring.factories介绍

spring.factories 是 Spring Framework 中的一个配置文件&#xff0c;它用于自动装配和加载 Spring 应用程序中的各种组件。该文件位于 META-INF/spring.factories&#xff0c;通常位于 JAR 文件的资源路径下。 spring.factories 文件采用键值对的形式&#xff0c;每个键代表一…...

业务设计——用户敏感信息展示脱敏及其反脱敏

业务需求 将用户敏感信息脱敏展示到前端是出于保护用户隐私和信息安全的考虑。 敏感信息包括但不限于手机号码、身份证号、银行卡号等&#xff0c;这些信息泄露可能导致用户个人信息的滥用、身份盗用等严重问题。脱敏是一种常用的保护用户隐私的方式&#xff0c;它的目的是减少…...

Hadoop分布式安装

首先准备好三台服务器或者虚拟机&#xff0c;我本机安装了三个虚拟机&#xff0c;安装虚拟机的步骤参考我之前的一篇 virtualBox虚拟机安装多个主机访问虚拟机虚拟机访问外网配置-CSDN博客 jdk安装 参考文档&#xff1a;Linux 环境下安装JDK1.8并配置环境变量_linux安装jdk1.8并…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...