45.跳跃游戏Ⅱ python

devtools/2024/12/23 22:27:08/

跳跃游戏Ⅱ

  • 题目
    • 题目描述
    • 示例 1:
    • 示例 2:
    • 提示:
  • 题解
    • 解决方案:贪心算法
    • 提交结果

题目

题目描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:

0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

1 <= nums.length <= 10^4
0 <= nums[i] <= 1000
题目保证可以到达 nums[n-1]

题解

这个问题是经典的“跳跃游戏 II”,其目标是在给定数组中找到从第一个元素跳到最后一个元素所需的最小跳跃次数。可以使用贪心算法来解决此问题,具体步骤如下:

解决方案:贪心算法

  1. 初始化变量

    • jumps 用来记录跳跃次数。
    • currentJumpEnd 表示当前跳跃所能达到的最远位置的索引。
    • farthest 表示在所有可能的跳跃范围内能到达的最远位置。
  2. 遍历数组(除了最后一个元素):

    • 对于每个元素,更新 farthest 为当前位置加该位置的值和 farthest 的较大者。
    • 如果当前位置等于 currentJumpEnd,意味着我们已经到达了上一次跳跃所能到达的最远位置,则需要再进行一次跳跃,并将 currentJumpEnd 更新为 farthest
  3. 结束条件:当 currentJumpEnd 达到或超过最后一个位置时,停止循环,此时 jumps 就是最小跳跃次数。

  4. 返回结果:最终返回 jumps

下面是 Python 实现代码:

python">def jump(nums):jumps = 0currentJumpEnd = 0farthest = 0for i in range(len(nums) - 1):# 更新可以达到的最远位置farthest = max(farthest, i + nums[i])# 如果达到了当前跳跃的边界,则需要增加跳跃次数if i == currentJumpEnd:jumps += 1currentJumpEnd = farthest# 提前结束条件:如果当前跳跃的边界已经达到或超过了最后一个位置if currentJumpEnd >= len(nums) - 1:breakreturn jumps

这段代码实现了上述逻辑,并且可以在 O(n) 时间复杂度内解决问题,其中 n 是数组的长度。这是因为我们只需遍历数组一次。空间复杂度为 O(1),因为我们只使用了常数级的额外空间。

提交结果

在这里插入图片描述


http://www.ppmy.cn/devtools/144815.html

相关文章

黑客如何找到App中的源IP:原理与防范

在移动互联网时代&#xff0c;应用程序&#xff08;App&#xff09;已经成为人们生活中不可或缺的一部分。然而&#xff0c;随着App的广泛应用&#xff0c;安全问题也日益受到关注。其中&#xff0c;源IP泄露是一个潜在的安全风险&#xff0c;可能导致服务器遭受攻击、敏感信息…

线程安全与线程不安全

线程安全的概念 线程安全&#xff1a;指当多个线程并发访问某个对象时&#xff0c;不会因为线程调度导致数据的不一致或数据污染&#xff0c;即能保证数据的完整性和正确性。实现线程安全的方式&#xff1a; 使用同步机制&#xff08;如 synchronized 关键字或显式锁 Reentran…

机器学习之偏差

机器学习中的偏差&#xff08;Bias&#xff09;是指模型的预测值与真实值之间的系统性误差&#xff0c;或者说模型无法准确捕捉数据中复杂模式的能力。偏差通常与模型的假设或学习能力有关&#xff0c;过高的偏差会导致模型的性能不佳&#xff0c;表现为欠拟合。 偏差的来源 模…

前端跨越方式有哪些

发现宝藏 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。【宝藏入口】。 前端跨域&#xff08;Cross-Origin Resource Sharing&#xff0c;CORS&#xff09;是指在不同源&#xff08;protocol、domain、…

共创共建!葡萄城 SpreadJS 完成 HarmonyOS NEXT 操作系统兼容认证

最新技术资源&#xff08;建议收藏&#xff09; https://www.grapecity.com.cn/resources/ 近日&#xff0c;华为“企业工作必备应用鸿蒙化论坛”在北京圆满落幕&#xff0c;论坛汇聚了众多行业精英和合作伙伴&#xff0c;聚焦讨论企业数字化转型与原生鸿蒙生态融合等话题。葡萄…

Linux入门攻坚——42、Nginx及web站点架构模式

对于lvs集群&#xff0c;是一个四层路由的集群&#xff0c;Director无需启用对端口的监控&#xff0c;直接将报文转发给后端业务服务器RealServer。 使用Nginx也可以实现集群功能&#xff0c;Nginx实现反向代理&#xff0c;实现的是七层上的转发&#xff0c;要求Nginx本身就是…

初学stm32 ——— 串口通信

目录 STM32的串口通信接口 UART异步通信方式特点&#xff1a; 串口通信过程 STM32串口异步通信需要定义的参数: USART框图&#xff1a; 常用的串口相关寄存器 串口操作相关库函数 ​编辑 串口配置的一般步骤 STM32的串口通信接口 UART&#xff1a;通用异步收发器USART&am…

MySQL 中的 MVCC:实现高效并发控制

1 引言 在高并发环境中&#xff0c;数据库必须确保多个事务可以同时安全地读取和写入数据&#xff0c;而不会导致数据不一致的问题。为了达到这一目标&#xff0c;MySQL 的 InnoDB 存储引擎引入了多版本并发控制&#xff08;MVCC&#xff09;。本文将探讨MVCC的工作原理、它如何…