README
¶
Jump Game II
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
参考
如果某一个作为起跳点的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为起跳点。
- 可以对每一个能作为起跳点的格子都尝试跳一次，把能跳到最远的距离不断更新。
如果从这个 起跳点 起跳叫做第 1 次跳跃，那么从后面 3 个格子起跳都可以叫做第 2 次跳跃。
所以，当一次跳跃结束时，从下一个格子开始，到现在能跳到最远的距离，都是下一次跳跃的起跳点。
- 对每一次跳跃用 for 循环来模拟。
- 跳完一次之后，更新下一次起跳点的范围。
- 在新的范围内跳，更新能跳到最远的距离。
记录跳跃次数，如果跳到了终点，就得到了结果。
Documentation
¶
Overview ¶
* @lc app=leetcode id=45 lang=golang * * [45] Jump Game II * * https://leetcode.com/problems/jump-game-ii/description/ * * algorithms * Hard (29.67%) * Likes: 2020 * Dislikes: 117 * Total Accepted: 231.8K * Total Submissions: 776.1K * Testcase Example: '[2,3,1,1,4]' * * Given an array of non-negative integers, 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. * * Example: * * * Input: [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. * * Note: * * You can assume that you can always reach the last index. *
Source Files