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

leetCode 55.跳跃游戏 贪心算法

给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 

示例 1:

输入:nums = [2,3,1,1,4]
输出:true
解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2:

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

>>思路和分析

示例1中,若站在元素3的位置,我究竟是跳一步还是跳两步,还是跳三步呢? 因为这是至多跳三步,那我究竟跳几步呢?然后我跳到下一个元素我又究竟要跳几步呢?能否跳到终点呢?

如果沿着这个思路去想,那本题就很难想出来了。其实可以换一个维度,不去纠结于在数组中得到一个元素往后具体去跳几步,我们只看覆盖范围。也就是说,在一开始站在起始位置,往后的覆盖范围就是覆盖了两步,然后站在元素3这个位置,往后的覆盖范围就是三步的覆盖范围。那么最终就把终点给覆盖了。

只要在覆盖范围内,那任何一个元素的下标位置,都可以跳到,别管我是跳几步,别管我是怎么跳的,我就是可以跳过来。那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖终点!

核心:怎么跳跃不重要,关键在覆盖范围

思路:每次移动取最大跳跃步数(得到最大的覆盖范围),每移动一个单位,就更新最大覆盖范围

>>贪心算法

  • 局部最优解:每次取最大跳跃步数(取最大覆盖范围
  • 整体最优解:最后得到整体最大覆盖范围,看是否能到终点

局部最优推出全局最优,找不到反例,试试贪心!

C++代码:

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;}
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

参考和推荐文章、视频

 代码随想录 (programmercarl.com)

 贪心算法,怎么跳跃不重要,关键在覆盖范围 | LeetCode:55.跳跃游戏_哔哩哔哩_bilibili

来自代码随想录的课堂截图:

相关文章:

leetCode 55.跳跃游戏 贪心算法

给你一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标&#xff0c;如果可以&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输入…...

CF505B Mr. Kitayuta‘s Colorful Graph

Mr. Kitayuta’s Colorful Graph 题面翻译 给出一个 n n n 个点&#xff0c; m m m 条边的无向图&#xff0c;每条边上是有颜色的。有 q q q 组询问 对于第 i i i 组询问&#xff0c;给出点对 u i , v i u_i,v_i ui​,vi​。求有多少种颜色 c c c 满足&#xff1a;有至…...

c#设计模式-结构型模式 之 组合模式

&#x1f680;简介 组合模式又名部分整体模式&#xff0c;是一种 结构型设计模式 &#xff0c;是用于把一组相似的对象当作一个 单一的对象 。组合模式 依据树形结构来组合对象 &#xff0c;用来表示部分以及整体层&#xff0c;它可以让你将对象组合成树形结构&#xff0c;并且…...

【Rust日报】2023-09-30 使用Rust做web抓取

CockroachDB 用rust重新实现 嘿&#xff0c;伙计们&#xff0c;我在 Rust 中实现了一个分布式 SQL 数据库。它就像 CockroachDB 和谷歌Google Spanner。告诉我你的想法。 注意: 这不是生产级别的数据库&#xff0c;这是一个以学习为目的的项目。有许多特性&#xff0c;但是缺少…...

【密评】商用密码应用安全性评估从业人员考核题库(三)

商用密码应用安全性评估从业人员考核题库&#xff08;三&#xff09; 国密局给的参考题库5000道只是基础题&#xff0c;后续更新完5000还会继续更其他高质量题库&#xff0c;持续学习&#xff0c;共同进步。 501 多项选择题 《个人信息保护法》要求个人信息处理者应当采取哪些…...

MySQL进阶_查询优化和索引优化

文章目录 第一节、索引失效案例1.1 数据准备1.2 全值匹配我最爱1.3 最佳左前缀法则 第一节、索引失效案例 可以从以下维度对数据库进行优化&#xff1a; 索引失效、没有充分利用到索引–索引建立关联查询太多JOIN (设计缺陷或不得已的需求)–SQL优化服务器调优及各个参数设置…...

Hadoop2复安装过程详细步骤

1、在vmware中更改了虚拟机的网络类型&#xff0c;--->NAT方式&#xff0c;&#xff08;虚拟交换机的ip可以从vmvare的edit-->vertual network editor看到&#xff09; 2、根据这个交换机&#xff08;网关&#xff09;的地址&#xff0c;来设置我们的客户端windows7的ip&…...

【Java-LangChain:面向开发者的提示工程-7】文本扩展

第七章 文本扩展 扩展是将短文本&#xff08;例如一组说明或主题列表&#xff09;输入到大型语言模型中&#xff0c;让模型生成更长的文本&#xff08;例如基于某个主题的电子邮件或论文&#xff09;。这种应用是一把双刃剑&#xff0c;好处例如将大型语言模型用作头脑风暴的伙…...

竞赛 基于设深度学习的人脸性别年龄识别系统

文章目录 0 前言1 课题描述2 实现效果3 算法实现原理3.1 数据集3.2 深度学习识别算法3.3 特征提取主干网络3.4 总体实现流程 4 具体实现4.1 预训练数据格式4.2 部分实现代码 5 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 基于深度学习机器视觉的…...

从技能需求到就业前景,了解前端和后端开发的优缺点和个人选择

文章目录 每日一句正能量一、引言前端开发后端开发 二、两者的对比分析三、技能转换和跨领域工作四&#xff1a;介绍全栈开发后记 每日一句正能量 命运决定的不是你的人生&#xff0c;能决定你人生的只有自己。 一、引言 前端和后端是Web开发中两个不可或缺的领域。前端开发主…...

Flutter笔记:AnimationMean、AnimationMax 和 AnimationMin 三个类的用法

Flutter笔记 AnimationMean、AnimationMax 和 AnimationMin三个类的用法 作者&#xff1a;李俊才 &#xff08;jcLee95&#xff09;&#xff1a;https://blog.csdn.net/qq_28550263 邮箱 &#xff1a;291148484163.com 本文地址&#xff1a;https://blog.csdn.net/qq_28550263/…...

华为云云耀云服务器L实例评测|云耀云服务器L实例部署Gogs服务器

华为云云耀云服务器L实例评测&#xff5c;云耀云服务器L实例部署Gogs服务器 一、云耀云服务器L实例介绍1.1 云耀云服务器L实例简介1.2 云耀云服务器L实例特点 二、Gogs介绍2.1 Gogs简介2.2 Gogs特点 三、本次实践介绍3.1 本次实践简介3.2 本次环境规划 四、远程登录华为云云耀云…...

操作系统--分页存储管理

一、概念介绍 分页存储&#xff1a;一是分内存地址&#xff0c;二是分逻辑地址。 1.分内存地址 将内存空间分为一个个大小相等的分区。比如&#xff0c;每个分区4KB。 每个分区就是一个“页框”&#xff0c;每个页框有个编号&#xff0c;即“页框号”&#xff0c;“页框号”…...

【算法练习Day10】有效的括号删除字符串中的所有相邻重复项逆波兰表达式求值

​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;练题 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录 有效的括号删除字符串中的所…...

10.1 校招 实习 内推 面经

绿泡*泡&#xff1a; neituijunsir 交流裙 &#xff0c;内推/实习/校招汇总表格 1、自动驾驶一周资讯 - 苹果汽车项目泡汤&#xff1f;纵目科技IPO终止&#xff0c;腾讯与岚图汽车合作升级&#xff0c;158亿元现金收购比亚迪“史上最大”并购案 自动驾驶一周资讯 - 苹果汽车…...

Redis中Set类型的操作

Set的结构与list相似&#xff0c;但底层存储结构是hashtable&#xff0c;因此它的值是唯一的&#xff0c;同时添加的顺序与保存的顺序并不一致。每一个Set类型的key中可以存储2^32-1个元素。 一、应用场景 1、保存用户的收藏 在小说网站中保存用户的收藏&#xff0c;收藏 的小…...

正确完成实时 AI

发表于 构建真实世界的实时 AI 一、说明 我们知道&#xff0c;当前的AI进展是扎根于历史数据&#xff0c;这就造成一个事实&#xff0c;模型总是赶不上实时进展&#xff0c;模型的洞察力不够尖锐&#xff0c;或者&#xff0c;时间损失等&#xff0c;本篇对这一系列AI的短板展开…...

深度学习笔记之线性代数

深度学习笔记之线性代数 一、向量 在数学表示法中&#xff0c;向量通常记为粗体小写的符号&#xff08;例如&#xff0c;x&#xff0c;y&#xff0c;z&#xff09;当向量表示数据集中的样本时&#xff0c;它们的值具有一定的现实意义。例如研究医院患者可能面临的心脏病发作风…...

Python与Scrapy:构建强大的网络爬虫

网络爬虫是一种用于自动化获取互联网信息的工具&#xff0c;在数据采集和处理方面具有重要的作用。Python语言和Scrapy框架是构建强大网络爬虫的理想选择。本文将分享使用Python和Scrapy构建强大的网络爬虫的方法和技巧&#xff0c;帮助您快速入门并实现实际操作价值。 一、Pyt…...

kind 安装 k8s 集群

在某些时候可能需要快速的部署一个k8s集群用于测试&#xff0c;不想部署复杂的k8s集群环境&#xff0c;这个时候我们就可以使用kind来部署一个k8s集群了&#xff0c;下面是使用kind部署的过程 一、安装单节点集群 1、下载kind二进制文件 [rootlocalhost knid]# curl -Lo ./kin…...

别再被‘小样本’难倒了!用Python的PyMC3库实战层次贝叶斯模型

用PyMC3解锁小样本分析&#xff1a;层次贝叶斯建模实战指南 当你的数据集像便利店冰柜里的酸奶——每个品类只有零星几瓶时&#xff0c;传统统计方法往往会束手无策。想象你正分析20个城市的新开门店周销售额&#xff0c;每个城市却只有3-5条数据记录。这时&#xff0c;层次贝叶…...

SGP30传感器数据不准?可能是你的I2C时序和初始化搞错了(避坑指南)

SGP30传感器数据异常排查指南&#xff1a;从硬件设计到软件调试的完整解决方案 1. 硬件设计中的常见陷阱与优化方案 SGP30作为一款高精度环境传感器&#xff0c;其硬件设计细节直接影响数据可靠性。许多开发者遇到的首要问题往往源于电路设计阶段被忽视的关键参数。 电源稳定性…...

深度解析:Beyond Compare 5授权机制与密钥生成技术

深度解析&#xff1a;Beyond Compare 5授权机制与密钥生成技术 【免费下载链接】BCompare_Keygen Keygen for BCompare 5 项目地址: https://gitcode.com/gh_mirrors/bc/BCompare_Keygen 在软件授权领域&#xff0c;Beyond Compare 5的RSA加密授权系统展现了商业软件保护…...

STP根桥选举避坑指南:华为交换机优先级设置的那些门道

STP根桥选举避坑指南&#xff1a;华为交换机优先级设置的那些门道 在网络工程师的日常工作中&#xff0c;生成树协议&#xff08;STP&#xff09;的配置看似简单&#xff0c;却暗藏玄机。特别是根桥选举这个基础环节&#xff0c;稍有不慎就会导致网络性能下降甚至环路问题。本文…...

SCI期刊AI率要求越来越严:一二区5%以下该怎么降

SCI一二区期刊AI率卡到5%以下&#xff0c;我的论文差点废了——后来这么救回来的 2026年开年&#xff0c;身边三个同学的SCI投稿被拒&#xff0c;理由都一样&#xff1a;AI-generated content detected。不是内容不行&#xff0c;是AI率没过关。 我的判断很直接&#xff1a;S…...

Llama-3.2V-11B-cot高效部署:双卡4090下11B模型加载时间缩短至92s

Llama-3.2V-11B-cot高效部署&#xff1a;双卡4090下11B模型加载时间缩短至92s 1. 项目概述 Llama-3.2V-11B-cot是基于Meta Llama-3.2V-11B-cot多模态大模型开发的高性能视觉推理工具。该工具针对双卡RTX 4090环境进行了深度优化&#xff0c;通过一系列技术创新将11B大模型的加…...

Leptin30;YQQVLTSLPSQNVLQIANDLENLRDLLHLL (mouse)

一、基本信息名称&#xff1a; Leptin30&#xff08;小鼠源瘦素功能片段肽&#xff09;单字母序列&#xff1a; YQQVLTSLPSQNVLQIANDLENLRDLLHLL三字母序列&#xff1a; Tyr-Gln-Gln-Val-Leu-Thr-Ser-Leu-Pro-Ser-Gln-Asn-Val-Leu-Gln-Ile-Ala-Asn-Asp-Leu-Glu-Asn-Leu-Arg-Asp…...

基于springboot框架的校园外卖管理系统的设计与实现

目录需求分析与功能规划技术选型与架构设计数据库设计与建模核心功能实现系统集成与测试部署与运维优化与扩展项目技术支持源码获取详细视频演示 &#xff1a;文章底部获取博主联系方式&#xff01;同行可合作需求分析与功能规划 明确校园外卖管理系统的核心需求&#xff0c;包…...

ADS 2025瞬态仿真实战:手把手教你搞定PCB微带线串扰分析(含变量单位避坑指南)

ADS 2025瞬态仿真实战&#xff1a;手把手教你搞定PCB微带线串扰分析&#xff08;含变量单位避坑指南&#xff09; 作为一名硬件工程师&#xff0c;在高速PCB设计中遇到串扰问题就像在迷宫里寻找出口——看似简单却处处暗藏陷阱。特别是当你在ADS 2025中按照教程一步步设置参数&…...

从数据包到DMA:图解GMAC传输描述符的完整生命周期(含TSO/VLAN案例)

从数据包到DMA&#xff1a;图解GMAC传输描述符的完整生命周期&#xff08;含TSO/VLAN案例&#xff09; 在网络硬件加速领域&#xff0c;GMAC&#xff08;Gigabit Media Access Control&#xff09;接口的传输描述符机制是提升数据吞吐效率的核心技术之一。本文将深入剖析一个网…...