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

贪心算法题解——跳跃游戏【LeetCode】

55. 跳跃游戏


一、算法逻辑(逐步思路)

问题描述:

给定一个非负整数数组 nums,其中 nums[i] 表示从位置 i 最多可以跳跃的步数。
从起点 0 出发,判断是否能够到达最后一个位置


解题思路:

  1. 设一个变量 mx 表示目前能跳到的最远位置索引(初始为 0);
  2. 从左往右遍历每个索引 i
    • 如果当前位置 i 已经超过了当前最远能跳的位置 mx,说明跳不到这里,返回 False
    • 否则,更新最远可达位置 mx = max(mx, i + nums[i])
    • 如果最远位置已经大于等于终点(len(nums) - 1),说明可以到达终点,提前返回 True
  1. 如果遍历结束也没有提前返回 True,表示终点不可达,默认返回 False(此代码中漏了 return,但符合题意的测试数据一定会在中途 return)。

二、算法核心点

✅ 核心思想:贪心 + 动态维护最远可达索引

  • 每次更新目前为止能跳到的最远位置;
  • 如果当前下标不可达(即 i > mx),则直接失败;
  • 一旦最远可达位置覆盖到终点,立即返回成功;
  • 本质是将原本可能用 DFS/BFS 的可达性问题,用贪心方式优化为线性扫描
class Solution:def canJump(self, nums: List[int]) -> bool:mx = 0for i, jump in enumerate(nums):if i >mx:return Falsemx = max(mx, i+jump)if mx>len(nums)-1:return True

三、复杂度分析

  • 时间复杂度:O(n)
    只遍历了一次数组,每个元素处理一次;
  • 空间复杂度:O(1)
    只使用了一个整型变量 mx

总结表:

维度

内容

✅ 思路逻辑

从左向右遍历,维护最远可达位置,遇到不可达立即返回 False

✅ 核心技巧

贪心更新最远跳跃索引,判断当前位置是否可达,提早终止

✅ 时间复杂度

O(n)

✅ 空间复杂度

O(1)

http://www.xdnf.cn/news/15257.html

相关文章:

  • Windows 用户账户控制(UAC)绕过漏洞
  • python学习笔记【1】对字符串的处理
  • 《Java Web程序设计》实验报告六 JSP+JDBC+MySQL实现登录注册
  • [vroom] 启发式算法(路径评估) | 局部搜索优化引擎 | 解决方案输出解析
  • 自助KTV选址指南与优化策略
  • 系统分析师-计算机系统-输入输出系统
  • 十三、K8s自定义资源Operator
  • 仅27M参数!SamOutVX轻量级语言模型刷新认知,小身材也有大智慧
  • 2025.7.12总结
  • Vue 项目打包部署还存在问题?你知道怎么做吧?
  • JVM回收
  • 内部类 示例
  • 【java安全】springBoot配置文件属性名自定义及属性值加密
  • 【6.1.0 漫画数据库技术选型】
  • 建造者模式(Builder)
  • 【Datawhale AI 夏令营】 用AI做带货视频评论分析(二)
  • 微服务环境下的灰度发布与金丝雀发布实战经验分享
  • 【电脑】硬盘驱动器(HDD)的基础知识
  • 消息认证码(message authentication code)MAC
  • skywalking镜像应用springboot的例子
  • 【设计模式】单例模式 饿汉式单例与懒汉式单例
  • jenkins自动化部署前端vue+docker项目
  • 并发--Callable vs Runnable
  • 代码随想录算法训练营第三十二天|LeetCode 509 斐波那契数,LeetCode 70 爬楼梯,LeetCode 746 使用最小花费爬楼梯
  • 笔记-分布式计算基础
  • 云计算三大服务模式深度解析:IaaS、PaaS、SaaS
  • zynq-PS篇——bperez77中DMA驱动注意事项
  • 飞算 JavaAI 智能编程助手:颠覆编程旧模式,重构新生态
  • 深入解析Java的G1收集器:原理、实战与优缺点
  • Umi-OCR 的 Docker安装(win制作镜像,Linux(Ubuntu Server 22.04)离线部署)