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

本文主要是介绍LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

给定一个非负整数数组 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,所以你永远不可能到达最后一个位置。

方法一:贪心算法

解题步骤
  1. 初始化最远距离max_reach 初始化为 0,用于记录能到达的最远位置。
  2. 遍历数组:遍历数组中的每个位置,并更新 max_reach
  3. 判断可达性:如果在某个位置 imax_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 Falsemax_reach = max(max_reach, i + nums[i])if max_reach >= n - 1:return Truereturn False# 示例调用
print(canJump([2,3,1,1,4]))  # 输出: True
print(canJump([3,2,1,0,4]))  # 输出: False
算法分析
  • 时间复杂度:(O(n)),其中 n 是数组 nums 的长度。
  • 空间复杂度:(O(1)),使用了常数额外空间。

方法二:回溯算法

解题步骤
  1. 定义回溯函数:尝试从当前位置开始,模拟所有可能的跳跃步数,向前递归探索。
  2. 递归跳跃:从当前位置起跳,逐步减小跳跃距离直到 0,递归调用自身。
  3. 终止条件:如果到达数组末尾,返回 true;如果所有跳跃尝试都失败,返回 false
完整的规范代码
def canJumpFromPosition(position, nums):if position == len(nums) - 1:return Truefurthest_jump = min(position + nums[position], len(nums) - 1)for next_position in range(position + 1, furthest_jump + 1):if canJumpFromPosition(next_position, nums):return Truereturn Falsedef 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

方法三:动态规划(自底向上)

解题步骤
  1. 初始化状态数组dp[i] 表示从位置 i 开始是否能到达数组的末尾。
  2. 状态转移:从后向前填充 dp 数组,根据 dp[j] (对于所有 i < j <= i+nums[i]) 更新 dp[i]
  3. 结果返回:返回 dp[0]
完整的规范代码
def canJump(nums):"""使用动态规划算法判断能否跳到最后一个位置:param nums: List[int], 输入的数组:return: bool, 是否能到达最后一个位置"""n = len(nums)dp = [False] * ndp[n - 1] = Truefor 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] = Truebreakreturn 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 个额外空间。

方法四:优化的贪心算法

解题步骤
  1. 从后向前遍历:从数组的倒数第二个元素开始,向前遍历数组。
  2. 更新目标位置:如果当前位置加上可跳跃的最大长度大于或等于目标位置,则更新目标位置为当前位置。
  3. 结果判断:遍历结束后,如果目标位置更新为数组的起始位置,则返回 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)),使用了常数的额外空间。

方法五:索引哈希映射

解题步骤
  1. 建立索引哈希映射:创建一个字典来记录每个元素能达到的最远距离。
  2. 判断可达性:从第一个元素开始,逐个检查每个元素是否可达,同时更新可达的最远距离。
  3. 递归结束条件:如果在某个点发现最远距离无法继续向前或已覆盖数组末尾,则停止。
完整的规范代码
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)),使用了常数的额外空间。

不同算法的优劣势对比

特征方法一: 贪心算法方法二: 回溯算法方法三: 动态规划方法四: 优化贪心方法五: 索引哈希映射
时间复杂度(O(n))(O(2^n))(O(n^2))(O(n))(O(n))
空间复杂度(O(1))(O(n))(O(n))(O(1))(O(1))
优势快速简单理论上完备结构清晰更直观高效直观简洁
劣势基本无极度低效空间复杂需逆向思维与方法一类似

应用示例详解

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

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

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

场景描述

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

技术实现

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

代码示例

def verify_level(nums):max_reach = 0for 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}")

输出解析

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

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

场景描述

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

技术实现

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

代码示例

def plan_animation_path(spots):reach = 0for 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 表示存在至少一个点使得角色无法从该点继续前进。

总结

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

这篇关于LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/925485

相关文章

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

C#读写文本文件的多种方式详解

《C#读写文本文件的多种方式详解》这篇文章主要为大家详细介绍了C#中各种常用的文件读写方式,包括文本文件,二进制文件、CSV文件、JSON文件等,有需要的小伙伴可以参考一下... 目录一、文本文件读写1. 使用 File 类的静态方法2. 使用 StreamReader 和 StreamWriter二、二进

Conda与Python venv虚拟环境的区别与使用方法详解

《Conda与Pythonvenv虚拟环境的区别与使用方法详解》随着Python社区的成长,虚拟环境的概念和技术也在不断发展,:本文主要介绍Conda与Pythonvenv虚拟环境的区别与使用... 目录前言一、Conda 与 python venv 的核心区别1. Conda 的特点2. Python v

Spring Boot中WebSocket常用使用方法详解

《SpringBoot中WebSocket常用使用方法详解》本文从WebSocket的基础概念出发,详细介绍了SpringBoot集成WebSocket的步骤,并重点讲解了常用的使用方法,包括简单消... 目录一、WebSocket基础概念1.1 什么是WebSocket1.2 WebSocket与HTTP

java中反射Reflection的4个作用详解

《java中反射Reflection的4个作用详解》反射Reflection是Java等编程语言中的一个重要特性,它允许程序在运行时进行自我检查和对内部成员(如字段、方法、类等)的操作,本文将详细介绍... 目录作用1、在运行时判断任意一个对象所属的类作用2、在运行时构造任意一个类的对象作用3、在运行时判断

MySQL 中的 CAST 函数详解及常见用法

《MySQL中的CAST函数详解及常见用法》CAST函数是MySQL中用于数据类型转换的重要函数,它允许你将一个值从一种数据类型转换为另一种数据类型,本文给大家介绍MySQL中的CAST... 目录mysql 中的 CAST 函数详解一、基本语法二、支持的数据类型三、常见用法示例1. 字符串转数字2. 数字

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具

MyBatis-Plus 中 nested() 与 and() 方法详解(最佳实践场景)

《MyBatis-Plus中nested()与and()方法详解(最佳实践场景)》在MyBatis-Plus的条件构造器中,nested()和and()都是用于构建复杂查询条件的关键方法,但... 目录MyBATis-Plus 中nested()与and()方法详解一、核心区别对比二、方法详解1.and()

Spring IoC 容器的使用详解(最新整理)

《SpringIoC容器的使用详解(最新整理)》文章介绍了Spring框架中的应用分层思想与IoC容器原理,通过分层解耦业务逻辑、数据访问等模块,IoC容器利用@Component注解管理Bean... 目录1. 应用分层2. IoC 的介绍3. IoC 容器的使用3.1. bean 的存储3.2. 方法注

MySQL 删除数据详解(最新整理)

《MySQL删除数据详解(最新整理)》:本文主要介绍MySQL删除数据的相关知识,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、前言二、mysql 中的三种删除方式1.DELETE语句✅ 基本语法: 示例:2.TRUNCATE语句✅ 基本语