跳跃游戏(Jump Game)

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

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

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

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

  • 1 <= nums.length <= 3 * 10^4
  • 0 <= nums[i] <= 10^5
bool canJump(int* nums, int numsSize){
    int start = 0;
    printf("%d\n",start);
    while(start <numsSize){
        int newIndex = -1;
        if(start+nums[start]>=numsSize-1) return true;
        for(int i =1;i<=nums[start];i++){
            if(i+nums[start+i]>nums[start]){
                if(newIndex == -1){
                    newIndex = i+start;
                }else if(i+nums[start +i]>newIndex-start+nums[newIndex]){
                    newIndex = i+start;
                }
                
            }
        }
        if(newIndex == -1) return false;
        start = newIndex;
    }
    return false;
}

yeah，写出来了，看看老师怎么写的

bool canJump (int* nums, int numsSize){
    bool canReach[numsSize];
    canReach[0] = true;
    for(int i=1; i< numsSize; i++){
        canReach[i] = false;
    }
    for(int i = 0; i < numsSize; i++){
        if(canReach[i]){
            for(int j = 1;j<=nums[i]; j++){
                int k =i+j;
                if(k<numsSize){
                    canReach[k] = true;
                }
            }
        }
    }
    return canReach[numsSize-1];
}

bool canJump(int* nums, int numsSize){
    int maxCanReach = 0;

    for(int i = 0; i <numsSize;i++){
        if( i<= maxCanReach) {
            int canReach = i + nums[i];
            if (canReach > maxCanReach) {
                maxCanReach = canReach;
            }
        }
    }
    return numsSize-1 <= maxCanReach;
}

这个思路类似，但是比我的方法更快呀