贪心 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 &…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...
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.…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
