[数据结构与算法]LeetCode 55.跳跃游戏(贪心，逆向思维）

题目描述：来自LeetCode

方法一：

思路： 基于贪心的思想，我们可以计算每一个可以到达的位置所能到达的最远的距离，并不断更新这个最远距离，因为可以选择走的更远的我们当然不选择近的啦。(可以将数组长度想象成一段路程，数组上的点代表加油站，每一个值代表在该加油站加完油后可以行驶的最远距离，如果在这个加油站加完油之后可以走更远，我们就加油，如果不能，我们当然不加了，并且选择在该加油站加油的前提条件是能到达该加油站，不然....怎么加）如果最远距离大于等于数组长度，则返回true，否则返回false。

故1.判断遍历到的第i个点是否可达 i<=可以到达的最远距离? 2.第i个点可以到达的最远距离i+nums[i]

代码实现C++:

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

方法二：

从后往前遍历数组，如果该位置可以到达最后，我们就视为从当前位置到最后一个元素不存在，将当前位置看做终点，继续往前遍历，因为只要能到达当前位置，就一定能到达数组的最后一位。在第n-2这个位置开始，它能到达终点即n-1的条件就是，nums[n-2]>=1,如果不能到达我们就保留该位置到最后的元素，（即终点不变)，那么n-3能到达终点的条件是什么呢？n-3只能直接到达终点，因为n-2到n-1是不可达的，故nums[n-3]>=2,同理，当n-3也不可达n-1，在判断n-4的时候，就必须是nums[n-4]>=3,可以发现，只要第i个元素后面的元素有一个不可到达终点，我们判断第i个元素是否可达第终点的条件就要加上一，如果可达，那第i个元素就变成终点，前面的元素只要能到就能到达终点，故条件又从是否大于一开始判断。在遍历结束，如果n==1就说明可达，否则说明不可达

代码实现c++:

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int m=nums.size();
        if(m==0) return true;
        int n=1;
        for(int i=m-2;i>=0;i--){
            if(nums[i]>=n){//当该位置可以到达终点时，该位置变成终点，修改下一个元素到达终点的条件
                n=1;
            }else{//当该位置不可以到达终点时，将下一个位置到达终点的判断条件加一
                n++;
            }
            if(i==0&&n>1) return false;//如果最后到达终点的条件（其实也是元素个数）大于1，说明不可达
        }
        return true;
    }
};

今日刷题任务完成~