力扣第 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.rhkb.cn/news/473763.html

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

相关文章

自动化运维(k8s):一键获取指定命名空间镜像包脚本

前言&#xff1a;脚本写成并非一蹴而就&#xff0c;需要不断的调式和修改&#xff0c;这里也是改到了7版本才在 生产环境 中验证成功。 该命令 和 脚本适用于以下场景&#xff1a;在某些项目中&#xff0c;由于特定的安全或政策要求&#xff0c;不允许连接到你的镜像仓库。然而…

Vue2+ElementUI:用计算属性实现搜索框功能

前言&#xff1a; 本文代码使用vue2element UI。 输入框搜索的功能&#xff0c;可以在前端通过计算属性过滤实现&#xff0c;也可以调用后端写好的接口。本文介绍的是通过计算属性对表格数据实时过滤&#xff0c;后附完整代码&#xff0c;代码中提供的是死数据&#xff0c;可…

机器学习(1)

一、机器学习 机器学习&#xff08;Machine Learning, ML&#xff09;是人工智能&#xff08;Artificial Intelligence, AI&#xff09;的一个分支&#xff0c;它致力于开发能够从数据中学习并改进性能的算法和模型。机器学习的核心思想是通过数据和经验自动优化算法&#xff…

【Linux学习】【Ubuntu入门】1-4 ubuntu终端操作与shell命令1

1.使用快捷键CtrlAltT打开命令终端&#xff0c;或者单击右键点击… 2.常用shell命令 目录信息查看命令&#xff1a;ls ls -a&#xff1a;显示目录所有文件及文件夹&#xff0c;包括隐藏文件&#xff0c;比如以.开头的 ls -l&#xff1a;显示文件的详细信息 ls -al&#xff1…

Oracle OCP认证考试考点详解082系列19

题记&#xff1a; 本系列主要讲解Oracle OCP认证考试考点&#xff08;题目&#xff09;&#xff0c;适用于19C/21C,跟着学OCP考试必过。 91. 第91题&#xff1a; 题目 解析及答案&#xff1a; 关于 Oracle 数据库中的索引及其管理&#xff0c;以下哪三个陈述是正确的&#x…

智能网页内容截图工具:AI助力内容提取与可视化

我们每天都会接触到大量的网页内容。然而&#xff0c;如何从这些内容中快速提取关键信息&#xff0c;并有效地进行整理和分享&#xff0c;一直是困扰我们的问题。本文将介绍一款我近期完成的基于AI技术的智能网页内容截图工具&#xff0c;它能够自动分析网页内容&#xff0c;截…

基于单片机智能温室大棚监测系统

本设计以单片机为核心的智能温室大棚监测系统&#xff0c;用于监测大棚内的温湿度、土壤湿度、CO2浓度和光照强度。该系统以STM32F103C8T6芯片为核心控制单元&#xff0c;涵盖电源、按键、NB-IoT模块、显示屏模块、空气温湿度检测、土壤湿度检测、二氧化碳检测和光敏电阻等模块…

深挖C++赋值

详解赋值 const int a 10; int b a;&a 0x000000b7c6afef34 {56496} &a 0x000000b7c6afef34 {10} 3. &b 0x000000b7c6afef54 {10} 总结&#xff1a; int a 10 是指在内存中&#xff08;栈&#xff09;中创建一个int &#xff08;4 byte&#xff09;大小的空间…

【Golang】——Gin 框架中的模板渲染详解

Gin 框架支持动态网页开发&#xff0c;能够通过模板渲染结合数据生成动态页面。在这篇文章中&#xff0c;我们将一步步学习如何在 Gin 框架中配置模板、渲染动态数据&#xff0c;并结合静态资源文件创建一个功能完整的动态网站。 文章目录 1. 什么是模板渲染&#xff1f;1.1 概…

创建vue3项目步骤

脚手架创建项目&#xff1a; pnpm create vue Cd 项目名称安装依赖&#xff1a;Pnpm iPnpm Lint&#xff1a;修复所有文件风格 &#xff0c;不然eslint语法警告报错要双引号Pnpm dev启动项目 拦截错误代码提交到git仓库&#xff1a;提交前做代码检查 pnpm dlx husky-in…

【爬虫实战】抓取某站评论

【爬虫实战】抓取某站评论 声明&#xff1a;本文中所有内容仅供学习交流使用&#xff0c;不用于其他任何目的&#xff0c;不提供完整代码&#xff0c;严禁用于商业用途和非法用途&#xff0c;否则由此产生的一切后果均与作者无关&#xff01; 方式一&#xff1a;JS逆向request发…

OpenSSL 自签名

参考文档&#xff1a;unigui开发人员工作手册2021 参考文章&#xff1a;保姆级OpenSSL下载及安装教程-CSDN博客 下载 Win32/Win64 OpenSSL Installer for Windows - Shining Light Productions 进入后向下拉找到下载位置&#xff0c;建议下载二进制版本的精简版&#xff0c…

基于YOLOv8深度学习的公共卫生防护口罩佩戴检测系统(PyQt5界面+数据集+训练代码)

在全球公共卫生事件频发的背景下&#xff0c;防护口罩佩戴检测成为保障公众健康和控制病毒传播的重要手段之一。特别是在人员密集的公共场所&#xff0c;例如医院、学校、公共交通工具等地&#xff0c;口罩的正确佩戴对降低病毒传播风险、保护易感人群、遏制疫情扩散有着至关重…

stm32下的ADC转换(江科协 HAL版)

十二. ADC采样 文章目录 十二. ADC采样12.1 ADC的采样原理12.2 STM32的采样基本过程1.引脚与GPIO端口的对应关系2.ADC规则组的四种转换模式(**)2.2 关于转换模式与配置之间的关系 12.3 ADC的时钟12.4 代码实现(ADC单通道 & ADC多通道)1. 单通道采样2. 多通道采样 19.ADC模数…

“fc-async”提供了基本的异步处理能力

在开发中,异步处理已经成为提升系统性能和用户体验的常用方式。然而,传统的@Async注解和基础的异步处理工具在面对复杂的任务场景时,存在局限性。这些局限性包括但不限于高并发环境下的稳定性、任务失败后的恢复机制、以及任务的监控和管理。 开源项目“fc-async”提供了基…

【linux】如何扩展磁盘容量(VMware虚拟机)-转载

如何扩展磁盘容量(VMware虚拟机) 一、前置准备工作 扩展虚拟机磁盘前&#xff0c;需要先把虚拟机关机才能进行扩展磁盘操作 1.选择虚拟机设置&#xff0c;如下图所示 2.输入你想扩展的磁盘容量&#xff0c;以本次实操为例&#xff0c;我这里输入的30G&#xff08;具体按照实…

记录配置ubuntu18.04下运行ORBSLAM3的ros接口的过程及执行单目imu模式遇到的问题(详细说明防止忘记)

今天的工作需要自己录制的数据集来验证昨天的标定结果 用ORBSLAM3单目imu模式运行&#xff0c;mentor给的是一个rosbag格式的数据包&#xff0c;配置过程出了几个问题记录一下&#xff0c;沿配置流程写。 一.orbslam3编译安装 1.首先是安装各种依赖 这里不再赘述&#xff0…

STM32设计井下瓦斯检测联网WIFI加Zigbee多路节点协调器传输

目录 目录 前言 一、本设计主要实现哪些很“开门”功能&#xff1f; 二、电路设计原理图 1.电路图采用Altium Designer进行设计&#xff1a; 2.实物展示图片 三、程序源代码设计 四、获取资料内容 前言 本系统基于STM32微控制器和Zigbee无线通信技术&#xff0c;设计了…

华为HCIP——MSTP/RSTP与STP的兼容性

一、MSTP/RSTP与STP的兼容性的原理&#xff1a; 1.BPDU版本号识别&#xff1a;运行MSTP/RSTP协议的交换机会根据收到的BPDU&#xff08;Bridge Protocol Data Unit&#xff0c;桥协议数据单元&#xff09;版本号信息自动判断与之相连的交换机的运行模式。如果收到的是STP BPDU…

Python绘制雪花

文章目录 系列目录写在前面技术需求完整代码代码分析1. 代码初始化部分分析2. 雪花绘制核心逻辑分析3. 窗口保持部分分析4. 美学与几何特点总结 写在后面 系列目录 序号直达链接爱心系列1Python制作一个无法拒绝的表白界面2Python满屏飘字表白代码3Python无限弹窗满屏表白代码4…