题目链接：55.跳跃游戏I

题目详情：

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

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

判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

• 1 <= nums.length <= 3 * 10^4
• 0 <= nums[i] <= 10^5

题目还是很简单的，通过简单的分析得出在这个非负整数数组nums中只要一个0都没有一定能从数组的第一个下标到达最后一个下标，有0的话则不一定能够到达最后一个下标。 

还要注意的是当数组只有一位时无论初始下标的元素为多少都一定为true，因为此时数组的第一个下标同时也是数组的最后一个下标，如果数组大于一位时且初始下标的元素为0则一定为false，因为根本无法进行下一步跳跃因此无法到达最后一个下标。

初始我写的代码仅仅只是判断了能否到达终点，虽说也体现出了贪心的思想但不太明显，因此我打算继续优化一下。（代码就不放出来了）

我们用示例一来简单分析一下怎么用贪心思想来分析优化一下：

示例一给出的数组nums = [2,3,1,1,4]；

初始我们能跳两格，我们能够跳的范围为[2,3,1,1,4]；(黑色加粗为当前位置，红色加粗为可跳跃到的最大范围)，在这时我们选择所跳跃的位置：1.如果跳到1的位置（数组下标为二），我们接下来能跳到的最大范围为[2,3,1,1,4]，然后再经过上述步骤就能跳到4的位置（数组最后一个下标）；2.但如果我们选择跳到3的位置（数组下标为一），我们接下来能跳到的最大范围则为[2,3,1,1,4]，这时我们发现我们经过两步就到达了终点，这就是我们所优化的方向：每次跳跃后，在当前所能跳跃到的最大范围内去寻找下一次跳跃时能够到达最远范围的点，这个点就是我们在当前位置所选择的要跳跃的位置，然后重复上述操作直至在跳跃范围内能够到达终点（数组最后一个下标的位置）。

修改后的代码（c++）：

class Solution {
public :
    bool canJump(vector<int>& nums) {
        int length=nums.size();
        if(length==1)//如果只有一个元素则一定成功
        {
            return true;
        }
        if(nums[0]==0)//如果不止一个元素且初始元素为0则一定失败
        {
            return false;
        }
        int max=nums[0],jmax;//max为当前能跳到的最远距离，jmax为在当前能跳到的距离内所能跳跃到的最远距离
        for(int i=0;i<max;)//在当前所能跳到的最远距离查找下一次跳跃能够到达的最远距离
        {
            if(i+nums[i]>=length-1)//如果当前能够跳跃到数组最后一个下标则成功
            {
                return true;
            }
            jmax=max;
            for(int j=i+1;j<=max;j++)//在当前所能到达的范围内寻找能够使下一次跳跃范围最远的点
            {
                if(j+nums[j]>=jmax)//该点的下一次跳跃范围如果小于当前能够跳跃的最大范围则不选择跳跃到该点
                {
                    jmax=j+nums[j];
                    i=j;
                }
            }
            max=jmax;//当前所能跳跃到的最大范围更新
        }
        return false;
    }
};

做完这题后发现还有第二部，发现和这题代码差不多于是就继续做了下去。

题目链接：45.跳跃游戏II

题目详情：

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

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

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

假设你总是可以到达数组的最后一个位置。

示例 1:

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

输入: nums = [2,3,0,1,4]
输出: 2

提示:

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 1000

和上一题差不多，而且前面已经对跳跃最少步数分析过了，所以代码小小的改一下就行了。（前面分析过因此注释就不写了）

class Solution {
public:
    int jump(vector<int>& nums) {
        int length=nums.size();
        int max=nums[0],jmax;
        int count=0;
        if(nums[0]==0 || length==1)//初始位置的元素为0或者只有一个元素时最少跳跃为0步
        {
            return 0;
        }
        for(int i=0;i<max;)
        {
            jmax=max;
            if(i+nums[i]>=length-1)
            {
                count++;
                return count;
            }
            for(int j=i+1;j<=max;j++)
            {
                if(j+nums[j]>=jmax)
                {
                    jmax=j+nums[j];
                    i=j;
                }
            }
            count++;
            max=jmax;
        }
        return count;
    }
};