【Leetcode刷题Python】55. 跳跃游戏

简介: 解决LeetCode "跳跃游戏"问题的Python实现代码,使用了贪心算法的思路。代码中初始化最远可到达位置 max_k,并遍历数组 nums,通过更新 max_k 来记录每次能跳到的最远位置,如果在任何时刻 max_k 大于或等于数组的最后一个索引,则返回 True,表示可以到达数组的末尾;如果当前索引 i 超出了 max_k,则返回 False,表示无法继续前进。时间复杂度为 O(n),空间复杂度为 O(1)。

1 题目

给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1:

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

示例 2:

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

2 解析

思路: 尽可能到达最远位置(贪心)。
如果能到达某个位置,那一定能到达它前面的所有位置。

方法: 初始化最远位置为 0,然后遍历数组,如果当前位置能到达,并且当前位置+跳数>最远位置,就更新最远位置。最后比较最远位置和数组长度。

复杂度:时间复杂度 O(n)O(n),空间复杂度 O(1)O(1)。

3 Python实现

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # 初始化当前位置能到达的最远位置
        max_k = 0 
        end_index = len(nums)-1
        for i in range(len(nums)):
            # 判断如果最远距离能够超过最后一个位置,提前结束,减少循环次数,能够提高运行时间
            if max_k >= end_index:
                return True
            # 如果当前位置超过能到达位置的最大值,则失败
            if i > max_k:
                return False
            # 更新最远位置
            max_k = max(max_k, i+nums[i])
        return True
目录
相关文章
|
5月前
|
算法 Go 索引
【LeetCode 热题100】45:跳跃游戏 II(详细解析)(Go语言版)
本文详细解析了力扣第45题“跳跃游戏II”的三种解法:贪心算法、动态规划和反向贪心。贪心算法通过选择每一步能跳到的最远位置,实现O(n)时间复杂度与O(1)空间复杂度,是面试首选;动态规划以自底向上的方式构建状态转移方程,适合初学者理解但效率较低;反向贪心从终点逆向寻找最优跳点,逻辑清晰但性能欠佳。文章对比了各方法的优劣,并提供了Go语言代码实现,助你掌握最小跳跃次数问题的核心技巧。
216 15
|
10天前
|
小程序 PHP 图形学
热门小游戏源码(Python+PHP)下载-微信小程序游戏源码Unity发实战指南​
本文详解如何结合Python、PHP与Unity开发并部署小游戏至微信小程序。涵盖技术选型、Pygame实战、PHP后端对接、Unity转换适配及性能优化,提供从原型到发布的完整指南,助力开发者快速上手并发布游戏。
|
8月前
|
存储 人工智能 运维
【01】做一个精美的打飞机小游戏,浅尝阿里云通义灵码python小游戏开发AI编程-之飞机大战小游戏上手实践-优雅草央千澈-用ai开发小游戏尝试-分享源代码和游戏包
【01】做一个精美的打飞机小游戏,浅尝阿里云通义灵码python小游戏开发AI编程-之飞机大战小游戏上手实践-优雅草央千澈-用ai开发小游戏尝试-分享源代码和游戏包
473 48
【01】做一个精美的打飞机小游戏,浅尝阿里云通义灵码python小游戏开发AI编程-之飞机大战小游戏上手实践-优雅草央千澈-用ai开发小游戏尝试-分享源代码和游戏包
|
2月前
|
存储 算法 区块链
从零实现Python扫雷游戏:完整开发指南与深度解析
扫雷作为Windows经典游戏,承载了许多人的童年回忆。本文将详细介绍如何使用Python和Tkinter库从零开始构建一个功能完整的扫雷游戏,涵盖游戏设计、算法实现和界面开发的全过程。
191 1
|
8月前
|
人工智能 Python
【02】做一个精美的打飞机小游戏,python开发小游戏-鹰击长空—优雅草央千澈-持续更新-分享源代码和游戏包供游玩-记录完整开发过程-用做好的素材来完善鹰击长空1.0.1版本
【02】做一个精美的打飞机小游戏,python开发小游戏-鹰击长空—优雅草央千澈-持续更新-分享源代码和游戏包供游玩-记录完整开发过程-用做好的素材来完善鹰击长空1.0.1版本
251 7
|
3月前
|
人工智能 搜索推荐 数据可视化
用 Python 制作简单小游戏教程:手把手教你开发猜数字游戏
本教程详细讲解了用Python实现经典猜数字游戏的完整流程,涵盖从基础规则到高级功能的全方位开发。内容包括游戏逻辑设计、输入验证与错误处理、猜测次数统计、难度选择、彩色输出等核心功能,并提供完整代码示例。同时,介绍了开发环境搭建及调试方法,帮助初学者快速上手。最后还提出了图形界面、网络对战、成就系统等扩展方向,鼓励读者自主创新,打造个性化游戏版本。适合Python入门者实践与进阶学习。
328 1
|
3月前
|
存储 算法 数据可视化
用Python开发猜数字游戏:从零开始的手把手教程
猜数字游戏是编程入门经典项目,涵盖变量、循环、条件判断等核心概念。玩家通过输入猜测电脑生成的随机数,程序给出提示直至猜中。项目从基础实现到功能扩展,逐步提升难度,适合各阶段Python学习者。
187 0
|
5月前
|
算法 Go
【LeetCode 热题100】55:跳跃游戏(详细解析)(Go语言版)
本篇解析详细讲解了 LeetCode 热题 55——跳跃游戏(Jump Game)。通过判断是否能从数组起点跳至终点,介绍了两种高效解法:贪心算法和反向思维。贪心法通过维护最远可达位置 `maxReach` 实现一次遍历,时间复杂度 O(n),空间复杂度 O(1);反向法则从终点回溯,判断是否可到达起点。两者均简洁高效,适合面试使用。延伸题目如 LeetCode 45 进一步提升挑战。
172 7
|
8月前
|
测试技术 Python
【03】做一个精美的打飞机小游戏,规划游戏项目目录-分门别类所有的资源-库-类-逻辑-打包为可玩的exe-练习python打包为可执行exe-优雅草卓伊凡-持续更新-分享源代码和游戏包供游玩-1.0.2版本
【03】做一个精美的打飞机小游戏,规划游戏项目目录-分门别类所有的资源-库-类-逻辑-打包为可玩的exe-练习python打包为可执行exe-优雅草卓伊凡-持续更新-分享源代码和游戏包供游玩-1.0.2版本
353 31
【03】做一个精美的打飞机小游戏,规划游戏项目目录-分门别类所有的资源-库-类-逻辑-打包为可玩的exe-练习python打包为可执行exe-优雅草卓伊凡-持续更新-分享源代码和游戏包供游玩-1.0.2版本
|
9月前
|
Python
课程设计项目之基于Python实现围棋游戏代码
游戏进去默认为九路玩法,当然也可以选择十三路或是十九路玩法 使用pycharam打开项目,pip安装模块并引用,然后运行即可, 代码每行都有详细的注释,可以做课程设计或者毕业设计项目参考
191 33

热门文章

最新文章

推荐镜像

更多