P107 跳完数组的最少跳数

描述#

这个题目说的是，给你一个非负整数数组，数组中的每个数字表示那个位置上可以向后跳的最大步数。一开始你站在下标为 0 的位置，你要计算出最少需要跳几次才能到达数组最后位置。如果无法到达数组最后位置，则返回 -1。

比如说，给你的数组 a 是：
2, 4, 0, 1, 2
一开始站在下标为 0 的位置，最多能向后跳 2 步。你先跳 1 步，来到 4，再跳 3 步就到达最后的位置。需要的最少跳数是 2。
再比如说，给你的数组是：
2, 1, 0, 4
一开始如果跳 2 步，到达 0，不能再跳。一开始如果跳 1 步，到达 1，可以向后再跳 1 步。但跳 1 步后仍然到达 0，不能再跳。因此对于这个数组，你没办法跳到最后的位置，返回 -1。

代码#

public class AlgoCasts {

  // Time: O(n), Space: O(n)
  public int numOfJumpToLast(int[] nums) {
    if (nums == null || nums.length == 0) return -1;
    int n = nums.length, max = 0;
    int[] d = new int[n];
    for (int i = 0; i < n; ++i) {
      if (max >= n-1) return d[n-1];
      if (i > max) return -1;
      max = Math.max(max, i+nums[i]);
      int last = Math.min(max, n-1);
      for (int j = last; j > i && d[j] == 0; --j)
        d[j] = d[i] + 1;
    }
    return -1;
  }

  // Time: O(n), Space: O(1)
  public int numOfJumpToLastO1(int[] nums) {
    if (nums == null || nums.length == 0) return -1;
    if (nums.length == 1) return 0;
    int n = nums.length, max = 0, jumps = 0, curEnd = 0;
    for (int i = 0; i < n; ++i) {
      if (max >= n-1) return jumps + 1;
      if (i > max) return -1;
      if (i > curEnd) {
        ++jumps;
        curEnd = max;
      }
      max = Math.max(max, i+nums[i]);
    }
    return -1;
  }

}