当前位置: 首页> 文旅> 旅游 > 网站制作工具_怎么制作二维码并自己编辑内容_百度云网盘免费资源_企业邮箱账号

网站制作工具_怎么制作二维码并自己编辑内容_百度云网盘免费资源_企业邮箱账号

时间:2025/7/11 10:34:43来源:https://blog.csdn.net/qq_14815605/article/details/143687106 浏览次数:0次
网站制作工具_怎么制作二维码并自己编辑内容_百度云网盘免费资源_企业邮箱账号

LeetCode 45.跳跃游戏 II

题目描述

给定一个非负整数数组 nums,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是跳到最后一个位置(数组的最后一个索引)。你可以选择跳过某些步骤,也可以跳负数。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 从位置 0 跳到 1(跳 1 步),然后从位置 1 跳到 3(跳 3 步)。总共跳了 2 步。

示例 2:

输入: nums = [3,2,1,0,4]
输出: 2
解释: 从位置 0 跳到 1(跳 1 步),然后从位置 1 跳到 3(跳 3 步)。总共跳了 2 步。

提示:

  • 1 <= nums.length <= 10^4
  • 0 <= nums[i] <= 1000

Java 实现代码

class Solution {public int jump(int[] nums) {int step = 0; // 记录跳跃次数int maxReach = 0; // 最远可以到达的位置int end = 0; // 当前可以跳到的最远位置for (int i = 0; i < nums.length - 1; i++) {// 更新最远可以跳到的位置end = Math.max(end, i + nums[i]);// 如果已经到达或超过当前步的终点,则开始下一步if (i == maxReach) {step++;maxReach = end;}}return step;}
}

解题思路

  1. 贪心算法:使用贪心算法,从左到右遍历数组,每次尝试跳到最远的位置。
  2. 维护最远位置:使用变量 maxReach 记录当前步可以到达的最远位置,end 记录当前可以跳到的最远位置。
  3. 边界条件:在每次循环中,只有当索引 i 等于 maxReach 时,表示已经到达或超过当前步的终点,开始计算下一步。
  4. 终止条件:当遍历到数组的最后一个索引时,返回总的跳跃步数。

复杂度分析

  • 时间复杂度:O(n),其中 n 是数组 nums 的长度。最坏情况下需要遍历整个数组。
  • 空间复杂度:O(1),只需要常数级别的额外空间来存储跳跃次数、最远可以到达的位置和当前可以跳到的最远位置。
关键字:网站制作工具_怎么制作二维码并自己编辑内容_百度云网盘免费资源_企业邮箱账号

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: