LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射详解】

来源：好游戏攻略时间：2024-11-25 11:38

2024-06-09 85 发布于北京

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射详解】

作者介绍：10年大厂数据经营分析经验，现任大厂数据部门负责人。

会一些的技术：数据分析、算法、SQL、大数据相关、python

欢迎加入社区：码上找工作

作者专栏每日更新：

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化：企业实战案例

备注说明：方便大家阅读，统一使用python，带必要注释，公众号数据分析螺丝钉一起打怪升级

题目描述

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

输入格式nums：一个由非负整数构成的数组。输出格式返回一个布尔值，表示是否能到达最后一个位置。示例示例 1

输入: nums = [2,3,1,1,4] 输出: true 解释: 可以先跳 1 步，从位置 0 到 1，然后从位置 1 跳 3 步到最后一个位置。示例 2

输入: nums = [3,2,1,0,4] 输出: false 解释: 无论如何，你总会到达位置 3，但该位置的最大跳跃长度是 0，所以你永远不可能到达最后一个位置。方法一：贪心算法解题步骤初始化最远距离：max_reach 初始化为 0，用于记录能到达的最远位置。遍历数组：遍历数组中的每个位置，并更新 max_reach。判断可达性：如果在某个位置 i，max_reach < i，说明无法继续向前跳跃，返回 false；如果 max_reach 大于等于数组的最后一个位置，则返回 true。完整的规范代码

def canJump(nums): """ 使用贪心算法判断能否跳到最后一个位置 :param nums: List[int], 输入的数组 :return: bool, 是否能到达最后一个位置 """ max_reach, n = 0, len(nums) for i in range(n): if i > max_reach: return False max_reach = max(max_reach, i + nums[i]) if max_reach >= n - 1: return True return False # 示例调用 print(canJump([2,3,1,1,4])) # 输出: True print(canJump([3,2,1,0,4])) # 输出: False算法分析时间复杂度：(O(n))，其中 n 是数组 nums 的长度。空间复杂度：(O(1))，使用了常数额外空间。方法二：回溯算法解题步骤定义回溯函数：尝试从当前位置开始，模拟所有可能的跳跃步数，向前递归探索。递归跳跃：从当前位置起跳，逐步减小跳跃距离直到 0，递归调用自身。终止条件：如果到达数组末尾，返回 true；如果所有跳跃尝试都失败，返回 false。完整的规范代码

def canJumpFromPosition(position, nums): if position == len(nums) - 1: return True furthest_jump = min(position + nums[position], len(nums) - 1) for next_position in range(position + 1, furthest_jump + 1): if canJumpFromPosition(next_position, nums): return True return False def canJump(nums): """ 使用回溯算法判断能否跳到最后一个位置 :param nums: List[int], 输入的数组 :return: bool, 是否能到达最后一个位置 """ return canJumpFromPosition(0, nums) # 示例调用 print(canJump([2,3,1,1,4])) # 输出: True print(canJump([3,2,1,0,4])) # 输出: False算法分析时间复杂度：(O(2^n))，其中 n 是数组 nums 的长度，每个位置都可能产生递归调用。空间复杂度：(O(n))，递归的深度最多为 n。方法三：动态规划（自底向上）解题步骤初始化状态数组：dp[i] 表示从位置 i 开始是否能到达数组的末尾。状态转移：从后向前填充 dp 数组，根据 dp[j] (对于所有 i < j <= i+nums[i]) 更新 dp[i]。结果返回：返回 dp[0]。完整的规范代码

def canJump(nums): """ 使用动态规划算法判断能否跳到最后一个位置 :param nums: List[int], 输入的数组 :return: bool, 是否能到达最后一个位置 """ n = len(nums) dp = [False] * n dp[n - 1] = True for i in range(n - 2, -1, -1): furthest_jump = min(i + nums[i], n - 1) for j in range(i + 1, furthest_jump + 1): if dp[j]: dp[i] = True break return dp[0] # 示例调用 print(canJump([2,3,1,1,4])) # 输出: True print(canJump([3,2,1,0,4])) # 输出: False算法分析时间复杂度：(O(n^2))，其中 n 是数组 nums 的长度，对于每个元素，可能需要遍历 nums[i] 次。空间复杂度：(O(n))，存储状态数组 dp 需要 n 个额外空间。方法四：优化的贪心算法解题步骤从后向前遍历：从数组的倒数第二个元素开始，向前遍历数组。更新目标位置：如果当前位置加上可跳跃的最大长度大于或等于目标位置，则更新目标位置为当前位置。结果判断：遍历结束后，如果目标位置更新为数组的起始位置，则返回 true，否则返回 false。完整的规范代码

def canJump(nums): """ 使用优化的贪心算法判断能否跳到最后一个位置 :param nums: List[int], 输入的数组 :return: bool, 是否能到达最后一个位置 """ n = len(nums) lastPos = n - 1 # 最初目标位置为数组的最后一个位置 for i in range(n - 2, -1, -1): # 从倒数第二个位置向前遍历 if i + nums[i] >= lastPos: # 如果当前位置能跳到或跳过目标位置 lastPos = i # 更新目标位置为当前位置 return lastPos == 0 # 最终目标位置是否为起始位置 # 示例调用 print(canJump([2,3,1,1,4])) # 输出: True print(canJump([3,2,1,0,4])) # 输出: False算法分析时间复杂度：(O(n))，其中 n 是数组 nums 的长度，只需遍历一次数组。空间复杂度：(O(1))，使用了常数的额外空间。方法五：索引哈希映射解题步骤建立索引哈希映射：创建一个字典来记录每个元素能达到的最远距离。判断可达性：从第一个元素开始，逐个检查每个元素是否可达，同时更新可达的最远距离。递归结束条件：如果在某个点发现最远距离无法继续向前或已覆盖数组末尾，则停止。完整的规范代码

def canJump(nums): """ 使用索引哈希映射法判断能否跳到最后一个位置 :param nums: List[int], 输入的数组 :return: bool, 是否能到达最后一个位置 """ max_reach = 0 # 初始化最远可达位置 for i in range(len(nums)): if i > max_reach: return False # 当前索引不可达 max_reach = max(max_reach, i + nums[i]) # 更新最远可达位置 if max_reach >= len(nums) - 1: return True # 已可达数组末尾 return False # 示例调用 print(canJump([2,3,1,1,4])) # 输出: True print(canJump([3,2,1,0,4])) # 输出: False算法分析时间复杂度：(O(n))，其中 n 是数组 nums 的长度，只需遍历一次数组。空间复杂度：(O(1))，使用了常数的额外空间。不同算法的优劣势对比应用示例详解

跳跃游戏的算法在多个领域内都有广泛的应用，特别是在游戏开发、动画制作、机器学习等领域。以下是两个具体的应用场景，展示如何将跳跃游戏算法转化为实际可用的技术解决方案。

应用一：游戏开发中的关卡可玩性验证

在平台跳跃游戏的开发过程中，设计师常常需要创建出既具有挑战性又能确保玩家能够完成的关卡。使用跳跃游戏算法可以帮助开发者验证任何给定关卡的可玩性。

场景描述：

设计师创建了一个关卡，其中包含不同高度和间隔的平台，玩家从起点开始，需要通过跳跃到达终点。每个平台的数字表示玩家从该点最多可以向前跳跃的距离（即 nums 数组）。

技术实现：

开发者使用贪心算法，从起点开始，实时计算玩家可以到达的最远距离。如果在任一点，计算得到的最远距离小于该点的索引，意味着玩家无法从当前平台跳到下一个平台，关卡不可通行。

代码示例：

def verify_level(nums): max_reach = 0 for i, jump in enumerate(nums): if i > max_reach: return False, i # 返回不可通行的最远点 max_reach = max(max_reach, i + jump) if max_reach >= len(nums) - 1: return True, None # 关卡可通行 return False, len(nums) - 1 # 关卡设计示例：玩家可以从每个位置跳跃的最大长度 level_design = [2, 3, 1, 0, 4, 2, 1] is_playable, fail_point = verify_level(level_design) print(f"Level Playable: {is_playable}, Failure Point: {fail_point}")

输出解析：

如果关卡可通行，函数返回 True 和 None。如果关卡不可通行，函数指出玩家被卡住的具体位置。应用二：动画制作中的运动路径规划

动画制作中，制定角色或物体的移动路径是一个核心任务，跳跃游戏算法可以用来确保动画中的运动路径是连贯和逻辑上可行的。

场景描述：

动画师需要创建一个场景，其中一个角色需要从场景的一端跳跃到另一端。每个可能的着陆点的数字表示从该点角色能够跳跃的最大长度。

技术实现：

使用贪心算法来确定角色的每一步是否都能顺利落到一个合法的着陆点。这样的算法保证了动画的连贯性和视觉上的合理性。

代码示例：

def plan_animation_path(spots): reach = 0 for i in range(len(spots)): if i > reach: return False # 角色无法继续前进 reach = max(reach, i + spots[i]) return True # 角色可以顺利完成动画 # 动画路径设计示例：角色可以从每个位置跳跃的最大长度 animation_path = [1, 2, 0, 3, 2, 0, 1] can_complete = plan_animation_path(animation_path) print(f"Animation Path Complete: {can_complete}")

输出解析：

返回 True 表示角色可以顺利从起点跳到终点。返回 False 表示存在至少一个点使得角色无法从该点继续前进。总结

通过上述应用示例，我们可以看到跳跃游戏算法不仅仅局限于理论问题，它可以广泛应用于实际项目中，如游戏开发和动画制作，帮助开发者和设计师验证和规划合理的路径和策略。这种算法的实际应用强调了线性代数在现代编程中的实用价值和广泛适用性。

欢迎关注微信公众号数据分析螺丝钉

Linux内核中的调度算法演变：从O(1)到CFS的优化之旅###

本文深入探讨了Linux操作系统内核中进程调度算法的发展历程，聚焦于O(1)调度器向完全公平调度器（CFS）的转变。不同于传统摘要对研究背景、方法、结果和结论的概述，本文创新性地采用“技术演进时间线”的形式，简明扼要地勾勒出这一转变背后的关键技术里程碑，旨在为读者提供一个清晰的历史脉络，引领其深入了解Linux调度机制的革新之路。 ###

基于遗传优化的SVD水印嵌入提取算法matlab仿真

该算法基于遗传优化的SVD水印嵌入与提取技术，通过遗传算法优化水印嵌入参数，提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试，展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化，有效提升了水印技术的应用价值。

优化轮询算法以提高资源分配的效率

【10月更文挑战第13天】通过以上这些优化措施，可以在一定程度上提高轮询算法的资源分配效率，使其更好地适应不同的应用场景和需求。但需要注意的是，优化策略的选择和实施需要根据具体情况进行详细的分析和评估，以确保优化效果的最大化。

在 Python 中，三个关于可哈希不可不知的问题

云栖号资讯：【点击查看更多行业资讯】在这里您可以找到不同行业的第一手的上云资讯，还在等什么，快来！作为一种通用的编程语言，Python 为不同的用户场景提供了一系列内置的数据结构。当你学习 Python 基础知识的时候，你可能在某些地方看到有提及可哈希。

在 Python 中，三个关于可哈希不可不知的问题

人工智能浪潮下的自我修养：从Python编程入门到深度学习实践

【10月更文挑战第39天】本文旨在为初学者提供一条清晰的道路，从Python基础语法的掌握到深度学习领域的探索。我们将通过简明扼要的语言和实际代码示例，引导读者逐步构建起对人工智能技术的理解和应用能力。文章不仅涵盖Python编程的基础，还将深入探讨深度学习的核心概念、工具和实战技巧，帮助读者在AI的浪潮中找到自己的位置。

Python编程入门——从零开始构建你的第一个程序

【10月更文挑战第39天】本文将带你走进Python的世界，通过简单易懂的语言和实际的代码示例，让你快速掌握Python的基础语法。无论你是编程新手还是想学习新语言的老手，这篇文章都能为你提供有价值的信息。我们将从变量、数据类型、控制结构等基本概念入手，逐步过渡到函数、模块等高级特性，最后通过一个综合示例来巩固所学知识。让我们一起开启Python编程之旅吧！

Python编程入门：打造你的第一个程序

【10月更文挑战第39天】在数字时代的浪潮中，掌握编程技能如同掌握了一门新时代的语言。本文将引导你步入Python编程的奇妙世界，从零基础出发，一步步构建你的第一个程序。我们将探索编程的基本概念，通过简单示例理解变量、数据类型和控制结构，最终实现一个简单的猜数字游戏。这不仅是一段代码的旅程，更是逻辑思维和问题解决能力的锻炼之旅。准备好了吗？让我们开始吧！

Python编程中的设计模式：优雅解决复杂问题的钥匙####

本文将探讨Python编程中几种核心设计模式的应用实例与优势，不涉及具体代码示例，而是聚焦于每种模式背后的设计理念、适用场景及其如何促进代码的可维护性和扩展性。通过理解这些设计模式，开发者可以更加高效地构建软件系统，实现代码复用，提升项目质量。 ####

探索Python编程：从基础到高级应用

【10月更文挑战第38天】本文旨在引导读者从Python的基础知识出发，逐渐深入到高级编程概念。通过简明的语言和实际代码示例，我们将一起探索这门语言的魅力和潜力，理解它如何帮助解决现实问题，并启发我们思考编程在现代社会中的作用和意义。

题目描述输入格式输出格式示例示例 1 示例 2 方法一：贪心算法解题步骤完整的规范代码算法分析方法二：回溯算法解题步骤完整的规范代码算法分析方法三：动态规划（自底向上）解题步骤完整的规范代码算法分析方法四：优化的贪心算法解题步骤完整的规范代码算法分析方法五：索引哈希映射解题步骤完整的规范代码算法分析不同算法的优劣势对比应用示例详解应用一：游戏开发中的关卡可玩性验证应用二：动画制作中的运动路径规划总结