跳跃游戏二

• 方法一：（双指针法）此题参考跳台阶问题，题目要求求到达最后一个点的最小跳跃次数，那么我们就可以从最后一个往前推，先看谁能离得最远，并且能跳到最后一个。假设i位置是离最后一个位置最远，并且能跳到最后一个位置。下一步再看谁能离i位置最远，并且还能跳到i位置的，最后只需要记录跳跃的次数即可。

class Solution {
public:
    int jump(vector<int>& nums) {
        int sum = 0, flag = 0;
        int i = nums.size() - 2;//i是当前元素
        int j = nums.size() - 1;//j是要跳跃到的位置
        while(j > 0) {//当j==0时，说明已经从最后一个位置回溯到第一个位置了
            for(i = j - 1; i >= 0; i--) {
                if(nums[i] >= (j - i)){
                    flag = i;
                }
            }
            j = flag;
            sum++;//记录跳跃的次数
        }
        return sum;
    }
};

• 方法二：正向跳跃。核心其实就一句话：每次在上次能跳到的范围内选择一个能跳的最远的位置，将该位置作为下一次的起跳点。

       //法二：正向贪心找最小跳跃数,每次在上次能跳到的范围(end)内选择一个能跳到的最远位置(max_far)
        //作为新的范围(end)

        int max_far = 0;
        int step = 0;
        int end = 0;
        for(int i = 0; i < nums.size() - 1; i++) {
            max_far = max(i + nums[i], max_far);
            if(i == end) {
                end = max_far;
                step++;
            }
        }
        return step;