55. 跳跃游戏

题目描述

解题思路

本题的贪心思路，就是每一步都跳最大，如果跳跃的位置等于或者覆盖最后，表示能够跳到终点。
每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

i每次移动只能在cover的范围内移动，每移动一个元素，cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。
而cover每次只取 max(该元素数值补充后的范围, cover本身范围)。
如果cover大于等于了终点下标，直接return true就可以了。

public boolean canJump(int[] nums) {
    // 覆盖范围, 初始覆盖范围应该是0，因为下面的迭代是从下标0开始的
    int cover = 0;
    if (nums.length == 0) return true;
    // 在覆盖范围内更新最大的覆盖范围
    for (int i = 0; i <= cover; i++) {
        // 贪心贪的地方：每次取步数中的最大条约步数，转化为最大跳跃步数能否覆盖整个数组
        cover = Math.max(cover, i + nums[i]);   // 注意是使用 i + nums[i]，当遇到大的值后前面的步数就被算作i
        if (cover >= nums.length - 1) return true;  // 能够覆盖，能跳跃到终点
    }
    return false;
}

45.跳跃游戏II

题目描述

解题思路

本题和上一题不一样的地方，就是选择跳到终点的最小步数。
贪心的思路：局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最小步数。
思路虽然是这样，但在写代码的时候还不能真的就能跳多远跳远，那样就不知道下一步最远能跳到哪里了。
所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数！
这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。
如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

方法一

从图中可以看出来，就是移动下标达到了当前覆盖的最远距离下标时，步数就要加一，来增加覆盖距离。最后的步数就是最少步数。
这里还是有个特殊情况需要考虑，当移动下标达到了当前覆盖的最远距离下标时

如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。

如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。

public int jump(int[] nums) {
  if (nums.length == 1) return 0;
  int curDistance = 0; // 当前覆盖的最大距离
  int nextDistance = 0;  // 下一步覆盖的最大距离
  int ans = 0;  // 步数
  for (int i = 0; i < nums.length; i++) {
      // 更新下一步最远距离的下标
      nextDistance = Math.max(nextDistance, i + nums[i]);
      if (i == curDistance) { // 当遇到最远距离的下标
          if (curDistance != nums.length - 1) {   // 此时最远距离不等于长度（小于也可以）
              ans++;  // 需要在走一步
              curDistance = nextDistance; // 更新当前覆盖最远距离的下标
              if (nextDistance >= nums.length - 1) break; // 下一步覆盖已经包括终点
          } else break;   // 此时最远距离等于长度，直接返回
      }
  }
  return ans;
}

方法二

针对于方法一的特殊情况，可以统一处理，即：移动下标只要遇到当前覆盖最远距离的下标，直接步数加一，不考虑是不是终点的情况。
想要达到这样的效果，只要让移动下标，最大只能移动到nums.size - 2的地方就可以了。
因为当移动下标指向nums.size - 2时：

如果移动下标等于当前覆盖最大距离下标，需要再走一步（即ans++），因为最后一步一定是可以到的终点。（题目假设总是可以到达数组的最后一个位置），如图：

如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了，不需要再走一步。如图：

public int jump(int[] nums) {
    if (nums.length == 0) return 0;
    int curDistance = 0; // 当前覆盖的最大距离
    int nextDistance = 0;  // 下一步覆盖的最大距离
    int ans = 0;  // 步数
    for (int i = 0; i < nums.length - 1; i++) { // 注意这里是小于nums.size() - 1，这是关键所在
        nextDistance = Math.max(nextDistance, nums[i] + i);// 更新下一步覆盖的最远距离下标
        if (curDistance == i) {   // 遇到当前覆盖的最远距离下标
            curDistance = nextDistance;  // 更新当前覆盖的最远距离下标
            ans++;
        }
    }
    return ans;
}