leetcode-跳跃游戏&跳跃游戏Ⅱ_lecode 跳跃游戏

（代码题解来源于leetcode，非本人题解）

55. 跳跃游戏 - 力扣（LeetCode）

思路：

计算位置i可以跳的区间k，在跳的区间k中，找到可以跳到最大位置的区间Math.max(k, temp);，一直计算最远的可跳区间，如果nums.length - 1在最终的最远可跳区间内，那么return true;

public static boolean canJump(int[] nums) {
        if (nums == null) {
            return false;
        }
        //前n-1个元素能够跳到的最远距离
        int k = 0;
        for (int i = 0; i <= k; i++) {
            //第i个元素能够跳到的最远距离
            int temp = i + nums[i];
            //更新最远距离
            k = Math.max(k, temp);
            //如果最远距离已经大于或等于最后一个元素的下标,则说明能跳过去,退出. 减少循环
            if (k >= nums.length - 1) {
                return true;
            }
        }
        //最远距离k不再改变,且没有到末尾元素
        return false;
    }

c++版本

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int k = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (i > k) return false;
            k = max(k, i + nums[i]);
        }
        return true;
    }
};

45. 跳跃游戏 II - 力扣（LeetCode）

谁说这题简单！！！ (ㄒoㄒ)，下周回来再看一遍吧

回来了。。

思路：

1.第一步是必须要跳的，第一步界定了可跳的范围，start=0,end=1;

2.从第一步开始，需要判定max(maxPos, i + nums[i])，知道下一步可以跳到最远的距离；同时，将start=end; end = maxPos + 1;

3. ans++; 跳跃次数

int jump(vector<int> &nums)
{
    int ans = 0;
    int start = 0;
    int end = 1;
    while (end < nums.size())
    {
        int maxPos = 0;
        for (int i = start; i < end; i++)
        {
            // 能跳到最远的距离
            maxPos = max(maxPos, i + nums[i]);
        }
        start = end;      // 下一次起跳点范围开始的格子
        end = maxPos + 1; // 下一次起跳点范围结束的格子
        ans++;            // 跳跃次数
    }
    return ans;
}