力扣第 55 题 跳跃游戏

力扣第 55 题 跳跃游戏(Jump Game)。题目要求判断一个非负整数数组中,是否能够从第一个位置跳跃到最后一个位置。每个元素表示从当前位置最多可以跳跃的步数。

解题思路

我们可以用 贪心算法 来解决这个问题。贪心的核心思想是始终维护当前能够到达的最远位置,并判断是否可以覆盖到数组的最后一个位置。

  1. 初始化变量 maxReach 为 0,表示当前能够跳到的最远位置。
  2. 遍历数组的每个位置 i,判断:
    • 如果当前下标 i 大于 maxReach,说明无法从前面的跳跃到达位置 i,返回 false
    • 更新 maxReachmax(maxReach, i + nums[i]),表示当前能够跳到的最远位置。
  3. 如果遍历结束后,maxReach 大于等于数组的最后一个下标,则返回 true

C语言实现

#include <stdio.h>
#include <stdbool.h>// 跳跃游戏判断函数
bool canJump(int* nums, int numsSize) {int maxReach = 0;  // 能到达的最远位置for (int i = 0; i < numsSize; i++) {// 如果当前位置超过能到达的最远位置,说明无法继续跳跃if (i > maxReach) {return false;}// 更新能到达的最远位置if (i + nums[i] > maxReach) {maxReach = i + nums[i];}// 如果最远位置已经可以覆盖最后一个位置,则直接返回 trueif (maxReach >= numsSize - 1) {return true;}}return false;
}int main() {int nums[] = {2, 3, 1, 1, 4};int numsSize = sizeof(nums) / sizeof(nums[0]);if (canJump(nums, numsSize)) {printf("可以跳到最后一个位置!\n");} else {printf("无法跳到最后一个位置!\n");}return 0;
}

示例解析

示例 1:

输入:

int nums[] = {2, 3, 1, 1, 4};

输出:

可以跳到最后一个位置!

解释:

  • 从第一个位置跳跃 2 步到索引 1,接着跳跃 3 步到最后一个位置。
示例 2:

输入:

int nums[] = {3, 2, 1, 0, 4};

输出:

无法跳到最后一个位置!

解释:

  • 无论怎么跳跃,都无法跳过索引 3 的位置,因为索引 3 的值为 0。

复杂度分析

  1. 时间复杂度 O ( n ) O(n) O(n)
    • 遍历数组中的每个元素一次,线性时间复杂度。
  2. 空间复杂度 O ( 1 ) O(1) O(1)
    • 只使用了一个变量 maxReach,空间复杂度为常数。

贪心算法的核心

贪心的本质是:

  • 只关心是否能到达尽可能远的位置,而不需要模拟实际的跳跃过程。
  • 一旦 maxReach 无法覆盖某个位置,直接返回 false;如果能够覆盖到最后一个位置,返回 true

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

富士施乐DocuContre S2520报打开盖子A,取出纸张。代码077-900故障检修

故障描述: 一台富士施乐DocuContre S2520复印机开机报错:打开盖子A,取出纸张。代码077-900故障,用户之前经常卡纸,卡着、卡着就一直提示打开盖子A,取出纸张了;复印机屏幕提示如下图: 故障检修: 富士施乐DocuContre S2520复印机报打开盖子A,取出纸张。077-900的错误代…

MySQL事务相关面试题

MySQL事务 事务的特性是什么&#xff1f; 事务是一组操作的集合&#xff0c;是不可分割的单位&#xff0c;把所有操作作为一个整体要么同时成功&#xff0c;要么同时失败 ACID 并发事务问题 脏读&#xff1a;一个事务读到了另外一个事务还没有提交的数据 不可重复读&#x…

深度学习与飞桨 PaddlePaddle Fluid

编辑推荐 飞桨PaddlePaddle是百度推出的深度学习框架&#xff0c;不仅支撑了百度公司的很多业务和应用&#xff0c;而且随着其开源过程的推进&#xff0c;在其他行业得到普及和应用。 本书基于2019年7月4日发布的飞桨PaddlePaddle Fluid 1.5版本&#xff08;后续版本会兼容旧版…

C++ | Leetcode C++题解之第564题寻找最近的回文数

题目&#xff1a; 题解&#xff1a; using ULL unsigned long long;class Solution { public:vector<ULL> getCandidates(const string& n) {int len n.length();vector<ULL> candidates {(ULL)pow(10, len - 1) - 1,(ULL)pow(10, len) 1,};ULL selfPrefi…

解决IDEA报包不存在,但实际存在的问题

前言 最近在把一个亿老项目交割给同事&#xff0c;同事在导入项目运行时遇到IDEA报包不存在&#xff0c;但实际存在的问题&#xff0c;最终通过以下方式解决 现象 在IDEA里启动运行项目&#xff0c;报某个类有问题&#xff0c;引入的包不存在。 点击这个引入的包&#xff0c;可…

Jenkins下载安装、构建部署到linux远程启动运行

Jenkins详细教程 Winodws下载安装Jenkins一、Jenkins配置Plugins插件管理1、汉化插件2、Maven插件3、重启Jenkins&#xff1a;Restart Safely插件4、文件传输&#xff1a;Publish Over SSH5、gitee插件6、清理插件&#xff1a;workspace cleanup system系统配置1、Gitee配置2、…

三、计算机视觉_04AlexNet、VggNet、ResNet设计思想

1、AlexNet 1.1 基本介绍 AlexNet是由Alex Krizhevsky、Ilya Sutskever和Geoffrey Hinton在2012年ImageNet大规模视觉识别挑战赛&#xff08;ILSVRC&#xff09;中提出的&#xff0c;它不仅赢得了当届的比赛&#xff0c;还激发了后续许多创新的神经网络架构&#xff08;如VGGN…

基于SpringBoot的在线考试系统的设计与实现+文档

&#x1f497;博主介绍&#x1f497;&#xff1a;✌在职Java研发工程师、专注于程序设计、源码分享、技术交流、专注于Java技术领域和毕业设计✌ 温馨提示&#xff1a;文末有 CSDN 平台官方提供的老师 Wechat / QQ 名片 :) Java精品实战案例《700套》 2025最新毕业设计选题推荐…

LabVIEW三针自动校准系统

基于LabVIEW的智能三针自动校准系统采用非接触式激光测径仪对标准三针进行精确测量。系统通过LabVIEW软件平台与硬件设备的协同工作&#xff0c;实现了数据自动采集、处理及报告生成&#xff0c;大幅提高了校准精度与效率&#xff0c;并有效降低了人为操作误差。 一、项目背景…

群控系统服务端开发模式-应用开发-前端上传配置功能开发

一、添加视图 在根目录下src文件夹下views文件夹下param文件夹下system文件夹下&#xff0c;新建index.vue&#xff0c;代码如下 <template><el-tabs type"border-card"><el-tab-pane v-if"$store.getters.butts.includes(ParamSystemIndexDeta…

VAM本体整合包,本体人物卡

已更至2024年11月】全网人物卡最全&#xff01;所见即所得解压既玩。资源整合包较大&#xff0c;选择性下载想玩什么下什么&#xff01;&#xff01;&#xff01; 1.包含上千付费级精品场景&#xff0c;新增数位神佬合集&#xff0c;新增绝版素材。 2.没有场景是没有灵魂的&…

jmeter常用配置元件介绍总结之监听器

系列文章目录 1.windows、linux安装jmeter及设置中文显示 2.jmeter常用配置元件介绍总结之安装插件 3.jmeter常用配置元件介绍总结之线程组 4.jmeter常用配置元件介绍总结之函数助手 5.jmeter常用配置元件介绍总结之取样器 6.jmeter常用配置元件介绍总结之jsr223执行pytho…

蓝绿色电影风格滑板运动自拍照Lr调色教程,手机滤镜PS+Lightroom预设下载!

调色教程 蓝绿色电影风格的滑板运动自拍照&#xff0c;通过 Lightroom 调色&#xff0c;将滑板运动的活力与电影般的质感相结合。这种风格以独特的蓝绿色调为主&#xff0c;营造出一种神秘、宁静又充满活力的氛围&#xff0c;仿佛将瞬间定格成电影画面中的一帧。 预设信息 调…

通用定时器---输入捕获功能

目录 一、概念 二、输入捕获的结构图 三、配置的基本步骤 一、概念 STM32的输入捕获功能是一种强大的特性&#xff0c;他允许处理器捕获外部输入信号&#xff0c;并基于定时器抓取输入信号指定触发方式&#xff08;上升沿/下降沿&#xff09;之间的长度。这对于测量信号的脉…

Comsol 大功率超声波清洗机

大功率超声波清洗机是利用超声波在清洗液中产生的空化作用来清洗物体表面的设备。这种清洗机通常用于清洗工业零部件、实验器皿、医疗器械等物体&#xff0c;能够高效去除表面附着的污垢、油脂、细菌等。 大功率超声波清洗机的工作原理是通过超声波换能器将电能转换成机械振动…

计算机视觉中的双边滤波:经典案例与Python代码解析

&#x1f31f; 计算机视觉中的双边滤波&#xff1a;经典案例与Python代码解析 &#x1f680; Hey小伙伴们&#xff01;今天我们要聊的是计算机视觉中的一个重要技术——双边滤波。双边滤波是一种非线性滤波方法&#xff0c;主要用于图像去噪和平滑&#xff0c;同时保留图像的边…

模板——实现泛型编程的有力武器

模板——实现泛型编程的有力武器 我们为什么需要模板&#xff1f;模板 前言&#xff1a;关于模板&#xff0c;相信大家都有所而闻&#xff0c;以下是我对C模板的个人看法&#xff0c;希望能够帮助到你们呀&#xff01; 我们为什么需要模板&#xff1f; 请到大家看这一段代码&a…

Hugging_Face下载

能进huggingface的就能翻过去 不行的话可以去参考这个:mojie.app 1.直接原网下载 2.git(小白勿入) 如果是Linux&#xff0c;可以搜一个叫HFD&#xff08;HuggingFace_Download&#xff09; Windows的git安装参考如下&#xff1a;Git安装 建议先看看这个文档&#xff0c; 如果…

C++之内存管理

​ &#x1f339;个人主页&#x1f339;&#xff1a;喜欢草莓熊的bear &#x1f339;专栏&#x1f339;&#xff1a;C入门 目录 前言 一、C/C内存分配 二、 malloc、calloc、realloc、free 三、C内存管理方式 3.1 new/delete 操作内置类型 3.2 new和detele操作自定义类型…

QT适配最新版Android SDK

从AndroidStudio的SDK管理下载最新版SDK 从https://www.androiddevtools.cn/下载国内安卓SKDTools 这里下载SKDTools后不需要使用SDK Manager.exe下载SDK&#xff08;SDK Manager.exe下载的SDK都是旧版&#xff0c;没法支持新版本&#xff09;&#xff0c;直接使用从AndroidS…