贪心 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. 跳跃游戏 题目: 给定非负数组,初始位置在数组第一格,数组值是可以选择的最大跳跃步数,判断能不能达到数组末尾。 示例 1: * 输入: [2,3,1,1,4] * 输出: true * 解释: 我们可以先跳 1 步,从位置 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脚本部署你的服务
我们都知道,在开发的过程中,有很多部署自己微服务的方式,其中有各种各样的不同操作,比如使用 docker 打包为镜像的方式,还有基础使用 jar 包的方式进行部署,但是呢?使用 jar 包部署,…...
银行数字化产品方案
在互联网及金融科技公司快速发展的时代背景下,银行客户普遍都意识到了自己在客户体验、客户洞察、产品服务方面受到的来自互联网的挑战 。为了更好地面对各方面的挑战,传统的业务模式必须革新。传统银行都在积极进行数字化转型。同时,也要面对…...

C# datagridview控件 绑定数据库中表中数据的方式-3
1.如下图所示,为数据库中的一张表结构,注意该表中共有11个字段 2.首先在窗体后台代码中拖入一个datagridview控件,并在窗体加载时,给datagridview控件添加列,添加的方式如下所示:请注意,每个列…...
Amazon CodeWhisperer 正式发布可免费供个人使用
文章作者:sunny 亚马逊云科技日前推出了实时 AI 编程助手 Amazon CodeWhisperer,包括个人套餐和专业套餐,所有开发人员均可免费使用个人套餐。Amazon CodeWhisperer 让开发人员能够保持专注、高效,帮助他们快速、安全地编写代码&a…...
el-table根据返回数据回显选择复选框
接口给你返回一个集合,然后如果这个集合里面的status2,就把这一行的复选框给选中 注意: 绑定的ref :row-key"getRowKeys" this.$refs.multiTableInst.toggleRowSelection(this.list[i], true); <el-table :data"list"…...

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

会话 cookie 及隐私的那些事
什么是会话 Cookie? 会话 Cookie 的概念非常简单。 会话 Cookie,也称为临时 Cookie 或内存 Cookie,是网站在浏览会话期间存储在用户计算机或设备上的小数据片段。 它是由网站生成并由您的浏览器存储和使用的多种 Cookie 之一。 常规 Cookie 或“持久”Cookie 是通常在您的…...
前端知识笔记(二十九)———MySQL通配符和正则表达式
一、通配符 1.% 匹配0,1,多个字符,但不匹配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网络应用程序的相关类,其中Socket类、TcpClient类、TcpListener类…...
linux 系统重装 ssh 连接失败
一.错误描述 WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED 二.解决方案 输入以下指令: ssh-keygen -R XXX(ip地址) 按照我的例子(ip:10.165.7.136),会返回以下信息: 重新尝试连…...
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()…...
计算机相关行业在大数据库时代下的潮流和趁势
还记得当初自己为什么选择计算机? 随着数据的爆炸性增长,数据科学和数据分析成为了热门的领域。这些专业涉及处理和分析大规模数据集的技术和方法,以从中提取有价值的信息和洞察。数据科学家和数据分析师在各个行业中的需求不断增加…...

Mac苹果视频剪辑:Final Cut Pro Mac
Final Cut Pro是一款由Apple公司开发的专业视频非线性编辑软件,是业界著名的视频剪辑软件之一。它最初发布于1999年,是Mac电脑上的一款独占软件。Final Cut Pro具有先进的剪辑工具、丰富的特效和颜色分级、音频处理等功能,使得用户可以轻松地…...
高德Map
使用 官网: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:SSM新闻发布管理系统 1 项目简介 Hi,各位同学好,这里是郑师兄! 今天向大家分享一个毕业设计项目作品【SSM新闻发布管理系统】 师兄根据实现的难度和等级对项目进行评分(最低0分,满分5分) 难度系数…...

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

“丝路电商”与泛欧在线公共采购平台Peppol
近期上海商务委员会公布《关于在上海市创建“丝路电商”合作先行区的方案》(以下简称方案),方案中提出:“全面贯彻落实党的二十大精神,立足新发展阶段,完整、准确、全面贯彻新发展理念,加快构建…...

今日思考 -- 创新领导力(CIO)读后感
收获3个观点: 1 ,IT DT 商业,才是未来IT人的出路之一 ! 2 ,在CXO中,CIO像CEO一样,具备了整个企业的业务全视角 ,同时也更具解决 ‘’系统性‘’问题的能力 ! 3 &…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...

label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
A2A JS SDK 完整教程:快速入门指南
目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库ÿ…...

Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...