跳跃游戏1&2跳跃游戏2

LeetCode 55. Jump Game 一个数组存储了非负整型数据，数组中的第i个元素nums[i]，代表了可以从数组第i 个位置最多向前跳跃nums[i]步;已知数组各元素的情况下，求是否可以从数组的第0个位置跳跃到数组的最后一个元素的位置? 例如: nums = [2, 3, 1, 1, 4] ，可以从nums[0] = 2 跳跃至 nums[4] = 4; nums = [3, 2, 1, 0, 4] ，不可以从nums[0] = 3 跳跃至 nums[4] = 4。

贪心规律

若此时处在第i位置，该位置最远可以跳至第j位置(index[i])，故第i位置还可跳至: 第i+1、i+2、...、j-1、j位置; 从第i位应跳至第i+1、i+2、...、j-1、j位中可以跳的更远位置的位置，即 index[i+1]、index[i+2]、...、index[j-1]、index[j]最大的那个! 原因: 假设该位置为x，index[x]最大，故从位置x出发，可以跳至i+1、i+2、...、j-1、j所有 位置可以达到的位置;所以跳至位置x最理想。

算法思路

1.求从第i位置最远可跳至第index[i]位置: 根据从第i位置最远可跳nums[i]步: index[i] = nums[i] + i; 2.初始化: 1)设置变量jump代表当前所处的位置，初始化为0; 2)设置变量max_index代表从第0位置至第jump位置这个过程中，最远可到达的位置，初始化为index[0]。 3.利用jump扫描index数组，直到jump达到index数组尾部或jump超过max_index，扫描过程中， 更新max_index。 4.若最终jump 为数组长度，则返回true，否则返回false。

#include<vector>
class Solution{
public:
    bool canJump(std::vector<int> & nums){
    std::vector<int> index; //最远可以跳至的位置
    for(int i = 0;i<nums.size();i++){
        index.push_back(i+ nums[i]);
    }
    int jump = 0;
    int max_index =index[0];
    while(jump < index.size && jump <= max_index){
        if(max_index < index[jump]){
            max_index = index[jump];
        }
        jump ++;
    }
      if(max_index == index.size()){
          return true;
      }
      return false;
    }
};

跳跃游戏2

LeetCode 45. Jump Game II 一个数组存储了非负整型数据，数组中的第i个元素nums[i]，代表了可以从数组第i 个位置最多向前跳跃nums[i]步;已知数组各元素的情况下，确认可以从第0位置跳跃到数组最后一个位置，求最少需要跳跃几次? 例如: nums = [2, 3, 1, 1, 4] ，从第0位置跳到第1位置，从第1位置跳至最后一个位置。

贪心规律

在到达某点前若一直不跳跃，发现从该点不能跳到更远的地方了，在这之前肯定 有次必要的跳跃! 结论:只有在无法到达更远的位置时，我们才应该选择跳跃，而选择从这之间的哪个位置跳跃?应选择一个可以到达更远位置的位置，跳到这个位置后，再往前跳。

算法思路

1.设置current_max_index为当前可达到的最远位置; 2.设置pre_max_max_index为在遍历各个位置的过程中，各个位置可达到的最远位置; 3.设置jump_min为最少跳跃的次数。 4.利用i遍历nums数组，若i超过current_max_index，jump_min加1，current_max_index = pre_max_max_index 5.遍历过程中，若nums[i]+i (index[i])更大，则更新pre_max_max_index = nums[i] + i。

#include<vetor>
class Solution{
public:
    int jump(std::vector<int> &nums){
        if(nums.size() < 2){
            return 0;
        }
        int current_max_index = nums[0];// 当前可达到的最远位置
        int pre_max_max_index = nums[0];//遍历各个位置过程中，可达到的最远位置
        int jump_min =1 ; 
        for(int i = 1; i< nums.size();i++){
            if(i > current_max_index){ // 若无法再向前移动，才进行跳跃
                jump_min++;
                curren_max_max_index = pre_max_max_index;
            }
            if(pre_max_max_index < num[i] + 1){
                pre_max_max_index = nums[i]+i;
            }
            return jump_min;
        
        }
    }
};