1.跳跃游戏I
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game
思路：设置一个当前能到达的最远位置，从头开始遍历，只有当i<=maxright时，才表示可以到达i位置，这时我们更新maxright，判断其能否到达尾部，若不能，返回false，能则返回true。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int len=nums.size();
        if(len<=0) return false;
        int maxRight=0;
        for(int i=0;i<len;i++)
        {
            if(i<=maxRight)//只有maxRight大于i时，才表示可以到达i位置
            {
                maxRight=max(maxRight,i+nums[i]);//每次都更新最大向右值
                if(maxRight>=len-1)
                {
                    return true;
                }   
            }  
        }
        return false;       
    }
};

2.跳跃游戏II
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-ii
思路一：顺藤摸瓜 从开始位置开始，计算下一步所能走的最远的位置，去选择下一步。依次类推，如2,3,1,1,4，因为一开始可以走一步或两步，但明显先走一步会更远，因此我们选择从2跳到3.

class Solution {
public:
    int jump(vector<int>& nums) {
    int end = 0;//当前能跳的边界
    int maxPosition = 0; 
    int steps = 0;
    for(int i = 0; i < nums.size() - 1; i++){
        //记录能跳的最远的
        maxPosition = max(maxPosition, nums[i] + i); 
        if( i == end){ //遇到边界，就更新边界，并且步数加一
            end = maxPosition;
            steps++;
        }
    }
    return steps;
    }
};

思路二：顺瓜摸藤我们知道最终要到达最后一个位置，然后我们找前一个位置，遍历数组，找到能到达它的位置，离它最远的就是要找的位置。然后继续找上上个位置，最后到了第 0 个位置就结束了。

public int jump(int[] nums) {
    int position = nums.size() - 1; //要找的位置
    int steps = 0;
    while (position != 0) { //是否到了第 0 个位置
        for (int i = 0; i < position; i++) {
            if (nums[i]+i >= position) {
                position = i; //更新要找的位置
                steps++;
                break;
            }
        }
    }
    return steps;
}

3.跳跃游戏III
这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。请你判断自己是否能够跳到对应元素值为 0 的 任意 下标处。注意，不管是什么情况下，你都无法跳到数组之外。
示例 1：
输入：arr = [4,2,3,0,3,1,2], start = 5
输出：true
解释：
到达值为 0 的下标 3 有以下可能方案：
下标 5 -> 下标 4 -> 下标 1 -> 下标 3
下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3
示例 2：
输入：arr = [4,2,3,0,3,1,2], start = 0
输出：true
解释：
到达值为 0 的下标 3 有以下可能方案：
下标 0 -> 下标 4 -> 下标 1 -> 下标 3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jump-game-iii
思路：广度优先搜索：初始时将 start 加入队列。在每一次的搜索过程中，我们取出队首的节点 u，它可以到达的位置为 u + arr[u] 和 u - arr[u]。如果某个位置落在数组的下标范围 [0, len(arr)) 内，并且没有被搜索过，则将该位置加入队尾。只要我们搜索到一个对应元素值为 0 的位置，我们就返回 True。在搜索结束后，如果仍然没有找到符合要求的位置，我们就返回 False。

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        if (arr[start] == 0) {
            return true;
        }

        int n = arr.size();
        vector<bool> used(n);
        queue<int> q;
        q.push(start);
        used[start] = true;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            if (u + arr[u] < n && !used[u + arr[u]]) {
                if (arr[u + arr[u]] == 0) {
                    return true;
                }
                q.push(u + arr[u]);
                used[u + arr[u]] = true;
            }
            if (u - arr[u] >= 0 && !used[u - arr[u]]) {
                if (arr[u - arr[u]] == 0) {
                    return true;
                }
                q.push(u - arr[u]);
                used[u - arr[u]] = true;
            }
        }
        return false;
    }
};