力扣第55题 跳跃游戏 c++ 贪心 + 覆盖 加暴力超时参考

题目

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 <= nums.length <= 104
  • 0 <= nums[i] <= 105

思路和解题方法

  1. 首先,我们维护一个变量cover,表示当前能够覆盖的最远距离。如果数组只有一个元素,则一定可以到达终点,直接返回true
  2. 然后,我们从位置0开始遍历数组,遍历范围是当前可覆盖范围内的所有位置,包括位置i。在遍历过程中,不断更新cover,使其取最大值。
  3. 如果在遍历过程中发现cover已经覆盖了数组的最后一个位置(即cover >= nums.size() - 1),则说明可以到达终点,直接返回true
  4. 如果最终没有到达终点,则说明无法到达,返回false

复杂度

        时间复杂度:

                O(n)

        时间复杂度是O(n),其中n是输入数组的长度。这是因为我们只需要一次遍历数组即可完成判断。

        空间复杂度

                O(1)

        空间复杂度是O(1),即常数级别的额外空间。除了几个变量(coveri)以及函数返回值外,代码并没有使用额外的数组或数据结构来存储中间结果。因此,空间复杂度是常数级别的。

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++) { // 遍历当前可覆盖范围内的所有位置// 注意这里的等于号,因为 i 指的是当前位置,所以必须要考虑到 i 也可以到达cover = max(i + nums[i], cover); // 更新能够覆盖的最远距离// 这里的 max 函数是为了保证更新后的 cover 是最大的if (cover >= nums.size() - 1) return true; // 如果当前能够覆盖的最远距离已经覆盖了终点,则说明可以到达终点}return false; // 如果最后还没有到达终点,则说明无法到达}
};

本人试过了O(n*n)的代码,超出时间限制了

具体暴力的代码(c++)

class Solution {
public:bool canJump(vector<int>& nums) {int n = nums.size();vector<bool> canReach(n, false); // 创建一个长度为n的数组,初始值都为falsecanReach[0] = true; // 初始位置可达for (int i = 0; i < n; i++) {if (!canReach[i]) continue; // 如果当前位置不可达,则跳过int maxJump = min(i + nums[i], n - 1); // 当前位置最远能跳到的位置for (int j = i + 1; j <= maxJump; j++) {canReach[j] = true; // 将可达位置标记为true}}return canReach[n - 1]; // 返回最后一个位置是否可达}
};

觉得有用的话可以点点赞,支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/168752.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Unity编辑器扩展 --- AssetPostprocessor资源导入自动设置

unity导入资源的编辑器设置: 防止策划资源乱导入,资源导入需要的格式&#xff0c;统一资源管理 AssetPostprocessor资源导入管线 AssetPostprocessor用于在资源导入时自动做一些设置&#xff0c;比如当导入大量图片时&#xff0c;自动设置图片的类型&#xff0c;大小等。Ass…

AlDente Pro for Mac: 掌控电池充电的终极解决方案

你是否曾经为了保护你的MacBook的电池&#xff0c;而苦恼于无法控制它的充电速度&#xff1f;AlDente Pro for Mac 是一款专为Mac用户设计的电池管理工具&#xff0c;它能帮助你解决这个问题。 AlDente Pro for Mac 是一款电池最大充电限制软件&#xff0c;它能够让你自由地设…

【数据结构与算法】二叉树的运用要点

目录 一&#xff0c;二叉树的结构深入认识 二&#xff0c;二叉树的遍历 三&#xff0c;二叉树的基本运算 3-1&#xff0c;计算二叉树的大小 3-2&#xff0c;统计二叉树叶子结点个数 3-3&#xff0c;计算第k层的节点个数 3-4&#xff0c;查找指定值的结点 一&#xff0c;二叉…

ResNet论文精读,代码实现与拓展知识

文章目录 ResNet 论文精读代码实现网络可视化代码 拓展知识 ResNets残差的调参残差链接的渊源残差链接有效性的解释ResNet 深度ResNeXt代码实现 能够提点的技巧「Warmup」「Label-smoothing」「Random image cropping and patching」「Knowledge Distiallation」「Cutout」「Ra…

Centos 7 Zabbix配置安装

前言 Zabbix是一款开源的网络监控和管理软件&#xff0c;具有高度的可扩展性和灵活性。它可以监控各种网络设备、服务器、虚拟机以及应用程序等&#xff0c;收集并分析性能指标&#xff0c;并发送警报和报告。Zabbix具有以下特点&#xff1a; 1. 支持多种监控方式&#xff1a;可…

SAP POorPI RFC接口字段调整后需要的操作-针对SP24及以后的PO系统

文章目录 问题描述解决办法 问题描述 在SAP系统的RFC接口结构中添加了字段&#xff0c;RFC也重新引用到了PO系统&#xff0c;Cache和CommunicationChannel都刷新或启停了&#xff0c;但是新增的字段在调用接口的时候数据进不到SAP系统&#xff0c;SAP系统内的值也出不来。经过…

postgresql14-模式的管理(三)

基本概念 postgresql成为数据库管理系统DBMS&#xff0c;在内存中以进程的形态运行起来成为一个实例&#xff0c;可管理多个database。 数据库databases&#xff1a;包含表、索引、视图、存储过程&#xff1b; 模式schema&#xff1a;多个对象组成一个模式&#xff0c;多个模…

nodejs+vue大学生社团管理系统

通过软件的需求分析已经获得了系统的基本功能需求&#xff0c;根据需求&#xff0c;将大学生社团管理系统平台功能模块主要分为管理员模块。管理员添加社团成员管理、社团信息管理&#xff0c;社长管理、用户注册管理等操作。 目 录 摘 要 I ABSTRACT II 目 录 II 第1章 绪论 1…

JVM的几个面试重点

JVM的内存区域划分 JVM类加载机制 前言 Java程序最开始是一个 .java 的文件&#xff0c;JVM把它编译成 .closs 文件&#xff08;字节码文件&#xff09;&#xff0c;运行 Java 程序&#xff0c; JVM 就会读取 .class 文件&#xff0c;把文件内容读取到内存中&#xff0c;构造出…

多线程与高并发

1.线程创建的3种方式 2.线程的状态切换步骤 3.线程的5中状态 Java中的线程的生命周期大体可分为5种状态。 1. 新建(NEW)&#xff1a;新创建了一个线程对象。 2. 可运行(RUNNABLE)&#xff1a;线程对象创建后&#xff0c;其他线程(比如main线程&#xff09;调用了该对象的sta…

通义大模型使用指南之通义千问

一、注册 我们可以打开以下网站&#xff0c;用手机号注册一个账号即可。 通义大模型 (aliyun.com) 二、使用介绍 如图&#xff0c;我们可以看到有三个大项功能&#xff0c;通义千问、通义万相、通义听悟。下来我们体验一下通义千问的功能。 1、通义千问 通义千问主要有两个功能…

北邮22级信通院数电:Verilog-FPGA(6)第六周实验:全加器

北邮22信通一枚~ 跟随课程进度更新北邮信通院数字系统设计的笔记、代码和文章 持续关注作者 迎接数电实验学习~ 获取更多文章&#xff0c;请访问专栏&#xff1a; 北邮22级信通院数电实验_青山如墨雨如画的博客-CSDN博客 先抄作业&#xff01;&#xff01;&#xff01;&am…

人工智能算法PPT学习

YOLO You only look once 是一种图像识别算法&#xff0c;速度较快。高效、灵活、泛化性能好&#xff0c;在工业中较为受欢迎。 图像金字塔 一幅图像的多个不同分辨率的子图构成的图像集合。是通过一个图像不断的降低采样率产生的&#xff0c;最小的图像可能仅仅有一个像素点…

如何在Ubuntu下安装RabbitMQ服务并异地远程访问?

文章目录 前言1.安装erlang 语言2.安装rabbitMQ3. 内网穿透3.1 安装cpolar内网穿透(支持一键自动安装脚本)3.2 创建HTTP隧道 4. 公网远程连接5.固定公网TCP地址5.1 保留一个固定的公网TCP端口地址5.2 配置固定公网TCP端口地址 前言 RabbitMQ是一个在 AMQP(高级消息队列协议)基…

Elasticsearch 8.X 分词插件版本更新不及时解决方案

1、关于 Elasticsearch 8.X IK 分词插件相关问题 球友在 ElasticSearch 版本选型问题中提及&#xff1a;如果要使用ik插件&#xff0c;是不是就使用目前最新的IK对应elasticsearch的版本“8.8.2”&#xff1f; https://github.com/medcl/elasticsearch-analysis-ik/releases/ta…

强大的虚拟机软件 VMware Fusion Pro 13中文最新 for mac

VMware Fusion Pro是一款虚拟化软件&#xff0c;它允许在Mac电脑上同时运行Windows和其他操作系统&#xff0c;而无需重启电脑&#xff0c;它采用了领先的虚拟化技术&#xff0c;能够保证在Mac电脑在同时运行多个操作系统时表现出极高的效率和稳定性。 VMware Fusion Pro具有以…

计算机网络的七层结构、五层结构和四层结构

为什么要分层&#xff1a; 这个就和我们平常写程序一样&#xff0c;高内聚、低耦合。将网络进行分层我们就可以根据每一层的功能分开开发设计&#xff0c;将复杂的网络问题分解为更简单和清晰的小问题&#xff0c;方便设计、实现和标准化。无需在意其他层是如何实现的&#xff…

maven仓库改国内源

今天准备复现漏洞环境&#xff0c;发现太慢&#xff0c;需要配置国内源 file -> settings 搜索maven 修改settings.xml&#xff0c;这里的需要修改两个文件 1.上图的settings.xml文件 2.idea的maven模块 settings.xml文件将原来的注释掉&#xff0c;然后把阿里的添加上&…

保姆级阿里云ESC服务器安装nodejs和服务器node服务管理工具PM2安装使用

一、安装Node到服务器 1. 创建node文件夹 默认 /opt 下边 /opt/node 也可建到其他地方&#xff0c;如/usr/local/node 等 创建后切换到文件夹下 cd /opt/node cd /opt/node2. 下载node并解压 使用命令下载node wget https://nodejs.org/dist/v18.12.0/node-v18.12.0-linux-…

PLC单按钮启停算法汇总

单按钮启停在三菱PLC里可以通过简单的取反指令"ALT"实现,西门子PLC如何实现ALT指令,请参考下面文章链接,这篇博客我们汇总常用的单按钮启停实现方法,希望大家读了本篇博客后有所收获。 博途ALT指令 博途S7-1200/1500PLC 取反指令(ALT)-CSDN博客SMART PLC的ALT指…