python 贪心算法 动态规划实现 跳跃游戏ll【力扣题45】

简介: python 贪心算法 动态规划实现 跳跃游戏ll【力扣题45】

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

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

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

作者专栏每日更新:

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

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

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

题目描述

LeetCode 题目 45:跳跃游戏 II

题目描述

给定一个非负整数数组 nums,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度(如果值是2则可以选择0、1、2进行跳跃 最大不超过2)。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

输入格式
  • nums:一个非负整数数组。
输出格式
  • 返回到达数组最后一个位置的最小跳跃次数。

示例

示例 1
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从索引 0 跳到索引 1 的位置,跳1步,然后从索引 1 跳到索引 4,跳3步。
示例 2
输入: nums = [2,3,0,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从索引 0 跳到索引 1 的位置,跳1步,然后从索引 1 跳到索引 4,跳3步。

功能和约束

  • 数组 nums 的长度不超过 10^4。
  • 每个元素的大小不超过 1000。
  • 你可以假设总是可以到达数组的最后一个位置。

这个问题要求找到一个高效的方法来确定达到数组末尾的最少跳跃次数。我们可以通过不同的策略来解决这个问题,包括动态规划、贪心算法等,来尽可能地减少计算时间和空间消耗。

方法一:贪心算法(正向)

解题步骤
  1. 初始化变量
  • end 表示当前能跳到的最远边界。
  • farthest 表示所有可选择跳的位置中,能跳到的最远位置。
  • jumps 记录跳跃次数。
  1. 遍历数组:除了最后一个元素,因为一旦到达最后一个元素,不需要再跳跃。
  • 更新能跳到的最远位置 farthest
  • 如果到达了当前的 end,即边界,更新边界并增加跳跃次数。
  1. 返回跳跃次数
完整代码
def jump(nums):
    """
    使用贪心算法从前向后计算最少的跳跃次数
    :param nums: List[int], 每个位置可以跳跃的最大长度
    :return: int, 最少跳跃次数
    """
    n = len(nums)
    end = farthest = jumps = 0
    
    for i in range(n - 1):  # 最后一个元素不需要访问
        farthest = max(farthest, i + nums[i])  # 更新能到达的最远位置
        if i == end:  # 到达上一跳能到的边界了
            jumps += 1  # 增加跳跃次数
            end = farthest  # 更新边界为当前能到达的最远位置
            if end >= n - 1:  # 如果已经能跳到最后位置
                break
    
    return jumps
# 示例调用
print(jump([2, 3, 1, 1, 4]))  # 输出: 2
算法分析
  • 时间复杂度:(O(N)),其中 (N) 是数组长度。
  • 空间复杂度:(O(1)),使用了有限的额外空间。

方法二:动态规划

解题步骤
  1. 初始化数组:创建一个数组 dp,其中 dp[i] 表示到达第 i 个位置的最少跳跃次数。
  2. 填充数组:初始化一个非常大的数表示无法到达的位置。
  3. 逐步更新:对于每个位置,尝试通过之前的所有位置跳到当前位置,更新 dp[i]
  4. 返回结果dp[n-1] 即为到达最后位置的最少跳跃次数。
完整代码
def jump(nums):
    """
    使用动态规划计算到达最后位置的最少跳跃次数
    :param nums: List[int], 每个位置可以跳跃的最大长度
    :return: int, 最少跳跃次数
    """
    n = len(nums)
    dp = [float('inf')] * n
    dp[0] = 0
    
    for i in range(1, n):
        for j in range(i):
            if j + nums[j] >= i:
                dp[i] = min(dp[i], dp[j] + 1)
    
    return dp[-1]
# 示例调用
print(jump([2, 3, 1, 1, 4]))  # 输出: 2
算法分析
  • 时间复杂度:(O(N^2)),其中 (N) 是数组长度,每个元素需被重复访问和比较。
  • 空间复杂度:(O(N)),使用了一个与输入数组等长的 dp 数组。

方法三:贪心算法(反向)

解题步骤
  1. 初始化指针:从数组最后一个位置开始。
  2. 逆向查找:寻找最远可以一步跳到当前位置的起点。
  3. 更新位置:更新当前位置到找到的位置,增加跳跃次数。
  4. 重复执行:直到到达数组的开始位置。
完整代码
def jump(nums):
    """
    使用贪心算法从后向前计算最少的跳跃次数
    :param nums: List[int], 每个位置可以跳跃的最大长度
    :return: int, 最少跳跃次数
    """
    position = len(nums) - 1
    steps = 0
    
    while position > 0:
        for i in range(position):
            if i + nums[i] >= position:
                position = i
                steps += 1
                break
    
    return steps
# 示例调用
print(jump([2, 3, 1, 1, 4]))  # 输出: 2
算法分析
  • 时间复杂度:(O(N^2)),虽然是贪心算法,但在最坏情况下退化成平方级别的时间复杂度。
  • 空间复杂度:(O(1)),只使用了常数空间。

总结

下面的表格将展示它们在不同技术维度的性能和特点,包括时间复杂度、空间复杂度以及各自的优势和劣势。

特征 方法一:正向贪心算法 方法二:动态规划 方法三:反向贪心算法
时间复杂度 (O(N)) (O(N^2)) (O(N^2))
空间复杂度 (O(1)) (O(N)) (O(1))
优势 - 高效且直接
- 实现简单
- 理论上全面
- 易于理解和实现
- 无需预先知道全局信息
- 实现简单
劣势 - 需要合理选择跳跃策略 - 空间和时间消耗大
- 不适合大规模数据
- 时间复杂度高
- 可能多次迭代寻找最优点
适用场景 - 大规模数据
- 需要最优时间性能
- 数据规模较小
- 对执行时间要求不高
- 理解问题的另一种方式
- 数据规模较小

综合分析

方法一(正向贪心算法)

  • 这种方法通过从前往后贪心地选择每一跳的最远可达点,以最小化跳跃次数。其时间复杂度为线性,是解决此问题的最高效方法。适用于大规模数据,因为其空间复杂度极低。

方法二(动态规划)

  • 动态规划提供了一种全面检查所有可能性的方法,通过构建一个状态转移表来决定最少的跳跃次数。虽然这种方法在小规模数据上表现良好,但在大规模数据处理上由于其平方级时间复杂度表现不佳。

方法三(反向贪心算法)

  • 反向贪心算法从数组的末端开始向前搜索,寻找能到达末端的最远起点,然后逐步逆向缩减问题规模。这种方法的优点是实现简单,但与正向贪心算法相比,其效率较低,因为它在最坏情况下的时间复杂度也是平方级。

在选择合适的算法时,应根据具体的应用需求和问题规模做出决策。对于大规模的实际应用,正向贪心算法通常是最优的选择,因为它提供了最好的时间和空间效率。对于教学或者问题规模较小的场合,可以考虑动态规划或反向贪心算法,以便更好地理解问题的结构。


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

相关文章
|
11天前
|
机器学习/深度学习 数据采集 搜索推荐
Python基于深度学习算法实现图书推荐系统项目实战
Python基于深度学习算法实现图书推荐系统项目实战
|
3天前
|
算法 测试技术 Python
python中算法无限循环(Infinite Loops)
【7月更文挑战第18天】
20 4
|
4天前
|
算法 IDE 测试技术
Python中算法错误
【7月更文挑战第17天】
14 4
|
3天前
|
大数据 UED 开发者
实战演练:利用Python的Trie树优化搜索算法,性能飙升不是梦!
【7月更文挑战第19天】Trie树,又称前缀树,是优化字符串搜索的高效数据结构。通过利用公共前缀,Trie树能快速插入、删除和查找字符串。
17 2
|
3天前
|
算法 搜索推荐 测试技术
python中算法逻辑错误(Logic Errors)
【7月更文挑战第18天】
7 2
|
3天前
|
算法 Python
python中算法递归错误(Recursion Errors)
【7月更文挑战第18天】
9 1
|
4天前
|
算法 计算机视觉 Python
Python并查集大揭秘:让你在算法界呼风唤雨,秒杀一切复杂场景!
【7月更文挑战第18天】并查集是Python中解决集合动态合并与查询的利器,常用于复杂问题。例如,在社交网络中快速判断用户是否在同一朋友圈,通过路径压缩优化的`UnionFind`类实现。另外,计算图像中岛屿数量也可借助并查集,将相邻像素合并成集合。并查集的应用显示了其在算法中的高效和灵活性,是提升编程技能的关键工具。
12 2
|
5天前
|
并行计算 算法 Python
Dantzig-Wolfe分解算法解释与Python代码示例
Dantzig-Wolfe分解算法解释与Python代码示例
|
5天前
|
存储 算法 Python
火箭般的提升!学会Python并查集,让你的算法能力飞跃新高度!
【7月更文挑战第17天】并查集,高效解决集合合并查询问题,常用于图的连通性判断。Python实现关键包含查找和合并操作。初始化时,元素各自为集合。查找使用路径压缩优化,合并则可选按秩策略保持平衡。例如,检测无向图环路,遍历边,若并查集发现边两端已在同一集合,则存在环。掌握并查集,提升算法能力,助你在问题解决中一飞冲天!动手实践,成为算法达人!
13 2
|
11天前
|
机器学习/深度学习 数据采集 算法
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战
Python实现ISSA融合反向学习与Levy飞行策略的改进麻雀优化算法优化支持向量机回归模型(SVR算法)项目实战