网站维护托管公司_山东泰安人才网_谷歌推广怎么做_新闻20条摘抄大全

题目如下

数据范围

示例

假设现有一数组的下标 abcdefgh。
其中 c d e 都能到达h由题目可知c + num[c] > e即从c出发能到达d和e。
显然由于c d e都能到达h那么我们只需要判断从a出发能不能到达c d e就行。
因为c + num[c] > e故只要能到达c就能到达d e。
所以我们可以简化需要判断的下标也就是说我们只需要判断从a是否能到c。
同理现在这个问题就变成起点为a终点为c的跳跃问题，以此类推我们只需要每次搜索能到达target的最小下标(只要从后往前搜索就行)然后把target更新成这个下标直到整个下标序列全部遍历完成最后判断target是否在0即可。

通过代码

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