跳跃游戏

题目

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

具体思路

• 确定当前的跳跃距离curDistance
• 当遍历到curDistance之前，要检查每一步的nextDistance取最大
• 如果能遍历到，那一定没有到达终点
  • 先做count++操作
  • 更新curDistance为nextDistance
  • 判断更新之后能否到达，能到达返回结果，因为这一步跳过了

关键点： 当前遍历到已知的最远的节点时，仍未终止循环才需要进行增加跳跃

具体代码

第一部分代码有问题：

class Solution {
public:
    int jump(vector<int>& nums) {
        int count = 1;
        int curDistance = 0;
        int allDistance = nums[0];
        if (nums.size() <= 1)
            return 0;
        for (int i = 0; i < nums.size(); i++) {
            curDistance = max(i + nums[i], allDistance);
            if (i == allDistance) {
                // 如果仍然小于，那么一定要多跳一次
                count++;
                allDistance = curDistance;
                // 更新下一步的覆盖范围时，需要再判断下一步会不会直接跳到，防止count多++
                if (allDistance >= nums.size() - 1)
                    break;
            }
        }
        return count;
    }
};

class Solution {
public:
    int jump(vector<int>& nums) {
        int count = 0;
        int curDistance = 0;
        int nextDistance = 0;
        if (nums.size() <= 1)
            return 0;
        for (int i = 0; i < nums.size() - 1; i++) {
            nextDistance = max(i + nums[i], nextDistance);
            if (i == curDistance) {
                // 如果仍然小于，那么一定要多跳一次
                count++;
                curDistance = nextDistance;
                // 更新下一步的覆盖范围时，需要再判断下一步会不会直接跳到，防止count多++
                if (curDistance >= nums.size() - 1)
                    break;
            }
        }
        return count;
    }
};

从后向前找最左端节点

反向思考： 从后向前遍历，我们只需要找第一个 n u m s [ i ] + i <= i n d e x 的位置，然后 将这个位置更新为 index ，直到 index 到达起点就可以了。

每一次的跳跃次数增加：一次寻找结束

class Solution {
    public int jump(int[] nums) {
        int res = 0;
        int index = nums.length - 1;
        while (index > 0) {
            int pre = index;
            for (int i = pre; i >= 0; i--) {
                if (i + nums[i] >= pre) {
                    index = i;
                }
            }
            res++;
        }
        return res;
    }
}