英文原文
Given an array of non-negative integers nums, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
You can assume that you can always reach the last index.
Example 1:
Input: nums = [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [2,3,0,1,4] Output: 2
Constraints:
1 <= nums.length <= 1040 <= nums[i] <= 1000
中文题目
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
示例 1:
输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是2。 从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。
示例 2:
输入: nums = [2,3,0,1,4] 输出: 2
提示:
1 <= nums.length <= 1040 <= nums[i] <= 1000
通过代码
高赞题解
思路
如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点。
- 可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新。
- 如果从这个 起跳点 起跳叫做第 1 次 跳跃，那么从后面 3 个格子起跳 都 可以叫做第 2 次 跳跃。
所以，当一次 跳跃 结束时，从下一个格子开始，到现在 能跳到最远的距离，都 是下一次 跳跃 的 起跳点。
对每一次 跳跃 用 for 循环来模拟。
跳完一次之后，更新下一次 起跳点 的范围。
在新的范围内跳，更新 能跳到最远的距离。
- 记录 跳跃 次数，如果跳到了终点，就得到了结果。
图解
代码
[]int jump(vector<int> &nums) { int ans = 0; int start = 0; int end = 1; while (end < nums.size()) { int maxPos = 0; for (int i = start; i < end; i++) { // 能跳到最远的距离 maxPos = max(maxPos, i + nums[i]); } start = end; // 下一次起跳点范围开始的格子 end = maxPos + 1; // 下一次起跳点范围结束的格子 ans++; // 跳跃次数 } return ans; }
优化
- 从上面代码观察发现，其实被 while 包含的 for 循环中，i 是从头跑到尾的。
- 只需要在一次 跳跃 完成时，更新下一次 能跳到最远的距离。
- 并以此刻作为时机来更新 跳跃 次数。
- 就可以在一次 for 循环中处理。
[]int jump(vector<int>& nums) { int ans = 0; int end = 0; int maxPos = 0; for (int i = 0; i < nums.size() - 1; i++) { maxPos = max(nums[i] + i, maxPos); if (i == end) { end = maxPos; ans++; } } return ans; }
致谢
感谢您的观看，希望对您有帮助，欢迎热烈的交流！
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 230223 | 530646 | 43.4% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 跳跃游戏 | 中等 |
