当前位置: 首页 > 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 &…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...

STM32 低功耗设计全攻略:PWR 模块原理 + 睡眠 / 停止 / 待机模式实战(串口 + 红外 + RTC 应用全解析)

文章目录 PWRPWR&#xff08;电源控制模块&#xff09;核心功能 电源框图上电复位和掉电复位可编程电压监测器低功耗模式模式选择睡眠模式停止模式待机模式 修改主频一、准备工作二、修改主频的核心步骤&#xff1a;宏定义配置三、程序流程&#xff1a;时钟配置函数解析四、注意…...

[C++错误经验]case语句跳过变量初始化

标题&#xff1a;[C错误经验]case语句跳过变量初始化 水墨不写bug 文章目录 一、错误信息复现二、错误分析三、解决方法 一、错误信息复现 write.cc:80:14: error: jump to case label80 | case 2:| ^ write.cc:76:20: note: crosses initialization…...