[数据结构与算法]leetcode(力扣)第五十五题&第四十五题：跳跃游戏&跳跃游戏（二）

题目

55. 跳跃游戏

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

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

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

45. 跳跃游戏 II

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

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

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

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

代码

/*-------------------------------55-------------------------------*/
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int b=0,e=0,ne=nums[0];//b,e为当前区域的起始位置与终止位置，ne为下一区域终止位置
        while(ne<nums.size()-1){
            b=e+1,e=ne;
            for(int i=b;i<=e;++i){
                if(ne<i+nums[i]) ne=i+nums[i];
            }
            if(e==ne)return false;
        }
        return true;
    }
};


/*-------------------------------45-------------------------------*/
class Solution {
public:

    int jump(vector<int>& nums) {
        if(nums.size()==1)return 0;
        int b=0,e=0,nb=1,ne=nums[0],step=1;//b,e为当前区域的起始位置与终止位置，ne为下一区域终止位置，step为步数
        while(ne<nums.size()-1){
            ++step;
            b=nb,e=ne,nb=e+1;
            for(int i=b;i<=e;++i){
                if(ne<i+nums[i]) ne=i+nums[i];
            }
        }
        return step;
    }
};

解析

两题结构完全一致，因此放到了一起。
首先说明两件事情：

• “区域”的定义

令{nums[0]}为区域X0，定义区域Xn为“从区域Xn-1中所有元素出发，能到达的元素集合与区域Xn-1的差集”。

• “区域”的性质

1. 任意区域的任意元素前，不存在不属于任何区域的元素。
2. nums[0]到任一区域内的任意元素，所需要的最短步数相同。

性质证明略。
“区域”的性质是使用贪心算法的基础，这两题的解法都是围绕着对“区域”的求解来进行的。又因为性质1，求解一个区域，只需要求解这个区域的末端元素即可，因为其起始元素必然为其上一区域末端元素的下一个元素。
在这两题中，只要在求解区域的过程中发现数组nums的末端元素落在某区域内，即可得出结果。只是在第一题中并不报证必定能到达末端，那么就需要额外判定：如果下一区域的末端元素和本区域的末端元素是同一元素，则该数组中所有的区域均已求得，后面的所有元素均不可达。如果nums的末端元素不在已得区域当中，即证明该元素不可达。