45.跳跃游戏Ⅱ python

server/2024/12/21 23:06:42/

跳跃游戏Ⅱ

  • 题目
    • 题目描述
    • 示例 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/server/152072.html

相关文章

区块链与比特币:技术革命的双子星

区块链与比特币&#xff1a;技术革命的双子星 引言 自2008年中本聪&#xff08;Satoshi Nakamoto&#xff09;提出比特币的概念以来&#xff0c;区块链技术和数字货币已经改变了我们对金融系统、网络安全和分布式计算的理解。本文将深入探讨区块链技术及其最著名的应用——比…

WebSocket vs SSE:实时通信技术的对比与选择

一、前言 Hello&#xff0c;欢迎来到流穿的AI探索之路系列专栏,作为一名AI应用工程师&#xff0c;我会在这儿更新一些前沿技术&#xff0c;欢迎关注哦。 这个问题也是前不久面试时被提问的&#xff0c;让我对比WebSocket和SSE&#xff0c;说说AI产品下处理SSE请求的方法。挺有…

模型优化和迁移学习

数据获取方法 三大要素&#xff1a;数据、算法&#xff08;神经网络&#xff09;、算力 数据集分类 分类数据&#xff1a;图像分类&#xff0c;一般以目录的形式分开标注数据&#xff1a;目标检测和图像分割&#xff0c;是有标注数据的 开源数据集 免费&#xff0c;成本低…

ARINC429和CAN

ARINC-429&#xff1a;一种用于航空电子设备之间数据通信的标准格式&#xff0c;数据格式为&#xff1a;数据速率、字长和校验方式。 数据速率&#xff1a;ARINC429传输速率通常为12.5Kbps或100Kbps; 字长&#xff1a;ARINC429数据长为32位&#xff0c;分为五个部分&#xff1a…

基于STM32的房间湿度控制系统设计与实现(论文+源码)

1.系统总体设计 根据系统的实际应用需求&#xff0c;从硬件电路以及软件程序两个方面展开房间湿度控制系统设计。如图所示为系统的整体架构图。系统采用单片机作为控制器&#xff0c;在传感器检测模块中包括DHT11温湿度检测、有害气体浓度检测&#xff0c;在系统执行模块包括加…

BigBlueButton视频会议 vs 钉钉视频会议系统的详细对比

BigBlueButton视频会议 vs 钉钉视频会议系统的详细对比 作者&#xff1a;BBBEasy中国区团队&#xff0c;Github地址&#xff1a;https://github.com/lihaiya/bbbeasy BigBlueButton和钉钉都是广泛应用的视频会议系统&#xff0c;它们在功能、适用场景、技术架构以及用户体验等…

工业大数据分析算法实战-day10

文章目录 day10机器学习其他视角负载模式、并行化计算新范式 时序算法简介 day10 今天是第10天&#xff0c;昨日主要是针对关联规则算法、深度学习算法进行阐述&#xff0c;讲解了常见的关联规则以及常见的深度学习算法&#xff0c;今日主要是针对第三章节最后一节机器学习算法…

[SZ901]JTAG高速下载设置(53Mhz)

SZ901最高支持JTAG 53MHz的时钟频率&#xff0c;下载bit文件和固化程序的速度提升非常明显。 首先设置参数 1&#xff0c;将JTAG0 分频系数修改为3 2&#xff0c;设置参数&#xff0c;更新参数。&#xff08;完成&#xff09; 打开VIVADO VIVADO 正常识别FPGA&#xff0c;速…