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

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)，只需要常数级别的额外空间来存储跳跃次数、最远可以到达的位置和当前可以跳到的最远位置。