给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。解题代码与测试
//
// Created by tannzh on 2020/7/8.
//
/*
*
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。
*/
#include <iostream>
#include <vector>
using std::vector;
class Solution {
public:
int jump(vector<int>& nums) {
auto n = nums.size();
int step = 0, max = 0;
for (int i=0, tmpMax=0; i<=max && i<n-1; i) {
tmpMax = std::max(tmpMax, nums[i] i);
if (i == max) { max = tmpMax; step; }
}
return max >= (n-1) ? step : -1;
}
};
int main(int argc, char **argv)
{
Solution s;
std::vector<int> nums = {2,3,1,1,4};
std::cout << s.jump(nums) << std::endl;
return 0;
}解题思路分析
这个题目应该属于贪心法的范畴。每次记录最远距离，即为局部最优解。确能推得整体最优解（是否能达到末尾）。
在这道题里，可能要对上次的代码做出一点修改：
- 因为只需最小的 jump，那么肯定要记录 step 数，故增加变量 step.
- 与上一道题一样，每一步都需要统计 max，但这个 max 并不一定为我所用，故改为 tmpMax
- 增加新的 max，用来记录最小步数的 max 步数，用以验证是否能够达到末尾。
然后说明一下，step 的策略肯定是越少越好，也就是能不加就不加。所以我们用 max 为限，当迭代的 i 到达了 max 时，那是不得不加了。 此时能拿到的最远距离，如果达到了末尾，表示已经用了最少的 step, 反之，则是上一次记录的 step 为最少，或也可能永远到不了末尾。
int step = 0, max = 0;
for (int i=0, tmpMax = 0; i<max && i<n-1; i) {
tmpMax = std::max(tmpMax, A[i] i);
if (i == max) { // 当 i 到达上次记录的最远位置
max = tmpMax; // 更新 max 记录
step; // 这算一步
}
}
return max >= (n-1) ? step : -1;
