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

贪心 55. 跳跃游戏 45.跳跃游戏 II

55. 跳跃游戏

题目:

给定非负数组,初始位置在数组第一格,数组值是可以选择的最大跳跃步数,判断能不能达到数组末尾。

示例  1:
* 输入: [2,3,1,1,4]
* 输出: true
* 解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例  2:
* 输入: [3,2,1,0,4]
* 输出: false
* 解释: 无论怎样,你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 , 所以你永远不可能到达最后一个位置。

贪心思路:

局部:求每一步的最大覆盖范围,记录下来,有更大的范围更新
全局:当遍历完,最大覆盖范围的i大于等于末尾的i,判断可以,否则不行。

如下图过程

 代码如下:  

class Solution {
public:bool canJump(vector<int>& nums) {int cover = 0;if (nums.size() == 1) return true; // 只有一个元素,就是能达到for (int i = 0; i <= cover; i++) { // 注意这里是小于等于covercover = max(i + nums[i], cover);if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了}return false;}
};

45.跳跃游戏 II

题目

给定一个非负整数数组,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置,然后返回最少的步数

(这里默认可以走到末尾)

示例1:
* 输入: [2,3,1,1,4]
* 输出: 2
* 解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置,跳  1  步,然后      跳  3  步到达数组的最后一个位置。


贪心思路:

局部最优:当前可移动距离尽可能多走,如果还没到终点,步数再加一。

全局最优:一步尽可能多走,从而达到最少步数。

从覆盖范围出发,不管怎么跳,覆盖范围内一定是可以跳到的,以最小的步数增加覆盖范围,覆盖范围一旦覆盖了终点,得到的就是最少步数!

这里需要统计两个覆盖范围,当前这一步的最大覆盖和下一步最大覆盖

如果移动下标达到了当前这一步的最大覆盖最远距离了,还没有到终点的话,那么就必须再走一步来增加覆盖范围,直到覆盖范围覆盖了终点。

求出遍历下标的最大覆盖范围内所有下标可以走的最大距离,比如从下标0开始,如果下标的范围不能覆盖末尾,那么遍历下标0覆盖范围的所有下标,比如下标1,下标2,看看当下一步走到下标1和下标3的时候,可不可以让整体的跳跃覆盖范围到末尾,如果这样覆盖范围到末尾了,比如下图1,它的值是3覆盖到末尾了,那么说明这里就是最短路径。

如果范围内的下标的可覆盖范围都没到末尾,说明要前进一步继续寻找。比如下图如果到了下标2如果还没找到就需要前进一步,i++了。

代码如下:

// 版本一
class Solution {
public:int jump(vector<int>& nums) {if (nums.size() == 1) return 0;int curDistance = 0;    // 当前覆盖范围最远距离下标(当前步数最远边界)int ans = 0;            // 记录走的最大步数int nextDistance = 0;   // 下一步的最大覆盖范围for (int i = 0; i < nums.size(); i++) {// 当前最大跳跃覆盖范围 和 之前的下一步最大覆盖距离 对比来 更新 这个时候的下一步最大覆盖距离nextDistance = max(nums[i] + i, nextDistance);// 更新下一步的最大覆盖范围,if (i == curDistance) {                   // 遇到当前覆盖最远距离下标  (这个一开始,0=0会运行一次,可参考上面图片)ans++;                                  // 需要走下一步curDistance = nextDistance;             // 更新当前覆盖最远距离下标(相当于加油了)if (nextDistance >= nums.size() - 1) break;  // 当前覆盖最远距到达集合终点,不用做ans++操作了,直接结束}}return ans;}
};
 疑问1:

nextDistance = max(nums[i] + i, nextDistance) 这段代码什么意思?

nums[i] + i表示从当前位置 i 在单次跳跃中可以到达的最远范围。而nextDistance 表示在之前的遍历过程中可达的最远范围,确保nextDistance始终是下一步最大的可达范围。

相关文章:

贪心 55. 跳跃游戏 45.跳跃游戏 II

55. 跳跃游戏 题目&#xff1a; 给定非负数组&#xff0c;初始位置在数组第一格&#xff0c;数组值是可以选择的最大跳跃步数&#xff0c;判断能不能达到数组末尾。 示例 1: * 输入: [2,3,1,1,4] * 输出: true * 解释: 我们可以先跳 1 步&#xff0c;从位置 0 到达 位置 1,…...

为XiunoBBS4.0开启redis缓存且支持密码验证

修改模块文件1 xiunoPHP/cache_redis.class.php: <?phpclass cache_redis {public $conf array();public $link NULL;public $cachepre ;public $errno 0;public $errstr ;public function __construct($conf array()) {if(!extension_loaded(Redis)) {return $thi…...

手把手教你写一个Shell脚本部署你的服务

我们都知道&#xff0c;在开发的过程中&#xff0c;有很多部署自己微服务的方式&#xff0c;其中有各种各样的不同操作&#xff0c;比如使用 docker 打包为镜像的方式&#xff0c;还有基础使用 jar 包的方式进行部署&#xff0c;但是呢&#xff1f;使用 jar 包部署&#xff0c;…...

银行数字化产品方案

在互联网及金融科技公司快速发展的时代背景下&#xff0c;银行客户普遍都意识到了自己在客户体验、客户洞察、产品服务方面受到的来自互联网的挑战 。为了更好地面对各方面的挑战&#xff0c;传统的业务模式必须革新。传统银行都在积极进行数字化转型。同时&#xff0c;也要面对…...

C# datagridview控件 绑定数据库中表中数据的方式-3

1.如下图所示&#xff0c;为数据库中的一张表结构&#xff0c;注意该表中共有11个字段 2.首先在窗体后台代码中拖入一个datagridview控件&#xff0c;并在窗体加载时&#xff0c;给datagridview控件添加列&#xff0c;添加的方式如下所示&#xff1a;请注意&#xff0c;每个列…...

Amazon CodeWhisperer 正式发布可免费供个人使用

文章作者&#xff1a;sunny 亚马逊云科技日前推出了实时 AI 编程助手 Amazon CodeWhisperer&#xff0c;包括个人套餐和专业套餐&#xff0c;所有开发人员均可免费使用个人套餐。Amazon CodeWhisperer 让开发人员能够保持专注、高效&#xff0c;帮助他们快速、安全地编写代码&a…...

el-table根据返回数据回显选择复选框

接口给你返回一个集合&#xff0c;然后如果这个集合里面的status2&#xff0c;就把这一行的复选框给选中 注意&#xff1a; 绑定的ref :row-key"getRowKeys" this.$refs.multiTableInst.toggleRowSelection(this.list[i], true); <el-table :data"list"…...

代码随想录算法训练营第四十二天 _ 动态规划_01背包问题。

学习目标&#xff1a; 动态规划五部曲&#xff1a; ① 确定dp[i]的含义 ② 求递推公式 ③ dp数组如何初始化 ④ 确定遍历顺序 ⑤ 打印递归数组 ---- 调试 引用自代码随想录&#xff01; 60天训练营打卡计划&#xff01; 学习内容&#xff1a; 二维数组处理01背包问题 听起来…...

会话 cookie 及隐私的那些事

什么是会话 Cookie? 会话 Cookie 的概念非常简单。 会话 Cookie,也称为临时 Cookie 或内存 Cookie,是网站在浏览会话期间存储在用户计算机或设备上的小数据片段。 它是由网站生成并由您的浏览器存储和使用的多种 Cookie 之一。 常规 Cookie 或“持久”Cookie 是通常在您的…...

前端知识笔记(二十九)———MySQL通配符和正则表达式

一、通配符 1.% 匹配0&#xff0c;1&#xff0c;多个字符&#xff0c;但不匹配NULL 2._ 匹配单个字符 3.[charlist] 匹配字符列中的任何单一字符 4.[^charlist] 或 [!charlist] 匹配不在字符列中的任何单一字符 二、正则表达式 通配符的LIKE替换为REGEXP LIKE 匹配整个列&…...

C#网络编程(System.Net.Sockets命名空间)

目录 一、Socket类 1.示例源码 2.生成效果 二、TcpClient类和TcpListener类 1.示例源码 2.生成效果 三、UdpClient类 1.示例源码 2.生成效果 System.Net.Sockets命名空间主要提供制作Sockets网络应用程序的相关类&#xff0c;其中Socket类、TcpClient类、TcpListener类…...

linux 系统重装 ssh 连接失败

一.错误描述 WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED 二.解决方案 输入以下指令&#xff1a; ssh-keygen -R XXX&#xff08;ip地址&#xff09; 按照我的例子&#xff08;ip:10.165.7.136&#xff09;&#xff0c;会返回以下信息: 重新尝试连…...

stream流操作List对象,指定属性,取差集、交集

差集 // 差集 (list1 - list2 list1 中不同数据)List<Person> reduce1 list1.stream().filter(a -> !list2.stream().map(b -> b.getAge() "&" b.getName()).collect(Collectors.toList()).contains(a.getAge() "&" a.getName()…...

计算机相关行业在大数据库时代下的潮流和趁势

还记得当初自己为什么选择计算机&#xff1f; 随着数据的爆炸性增长&#xff0c;数据科学和数据分析成为了热门的领域。这些专业涉及处理和分析大规模数据集的技术和方法&#xff0c;以从中提取有价值的信息和洞察。数据科学家和数据分析师在各个行业中的需求不断增加&#xf…...

Mac苹果视频剪辑:Final Cut Pro Mac

Final Cut Pro是一款由Apple公司开发的专业视频非线性编辑软件&#xff0c;是业界著名的视频剪辑软件之一。它最初发布于1999年&#xff0c;是Mac电脑上的一款独占软件。Final Cut Pro具有先进的剪辑工具、丰富的特效和颜色分级、音频处理等功能&#xff0c;使得用户可以轻松地…...

高德Map

使用 官网&#xff1a;JS API 结合Vue使用 npm i amap/amap-jsapi-loader --saveimport AMapLoader from amap/amap-jsapi-loader;marker的属性、事件、方法 https://lbs.amap.com/api/javascript-api-v2/documentation#marker 自定义marker 为创建的 Marker 指定自定义图…...

SSM新闻发布管理系统

SSM毕设分享 序号1&#xff1a;SSM新闻发布管理系统 1 项目简介 Hi&#xff0c;各位同学好&#xff0c;这里是郑师兄&#xff01; 今天向大家分享一个毕业设计项目作品【SSM新闻发布管理系统】 师兄根据实现的难度和等级对项目进行评分(最低0分&#xff0c;满分5分) 难度系数…...

客户销售目标拆解:数据驱动的方法和策略

写在开头 在当今竞争激烈的商业环境中,企业需要更加精准地制定销售目标以实现业务增长。数据驱动的方法在这一过程中扮演着关键的角色,帮助企业深入了解客户特征、行为和需求。本篇博客将深入探讨销售目标拆解在企业管理中的重要性,并介绍如何利用数据驱动的方法和策略来制…...

“丝路电商”与泛欧在线公共采购平台Peppol

近期上海商务委员会公布《关于在上海市创建“丝路电商”合作先行区的方案》&#xff08;以下简称方案&#xff09;&#xff0c;方案中提出&#xff1a;“全面贯彻落实党的二十大精神&#xff0c;立足新发展阶段&#xff0c;完整、准确、全面贯彻新发展理念&#xff0c;加快构建…...

今日思考 -- 创新领导力(CIO)读后感

收获3个观点&#xff1a; 1 &#xff0c;IT DT 商业&#xff0c;才是未来IT人的出路之一 &#xff01; 2 &#xff0c;在CXO中&#xff0c;CIO像CEO一样&#xff0c;具备了整个企业的业务全视角 &#xff0c;同时也更具解决 ‘’系统性‘’问题的能力 &#xff01; 3 &…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...