Problem: 55. 跳跃游戏
记录自己解答的思路和代码

文章目录

• 问题
• 思路
• 复杂度
• Code

问题

思路

这个题的主要思路就是先找到0对应的位置，然后标记起来对应left，如果只有一个零，只需要left后面的数中有>=1的数就能跳过去，如果是00，则left后面的数中要有至少>=2,所以至少跳多少步是个重点，这个可以再用一个标记right记录有多少连续的0，只要left后面的数有ums[j] >= right - j,就可以跳过去，然后把right赋值给left，接着遍历就行，这个就是解答这个题的中心思想

复杂度

时间复杂度:

$o(n^2)$

空间复杂度:

$o(1)$

Code

bool canJump(int* nums, int numsSize) {

    int left, right;
    left = right = 0;
    //特殊情况判断
    if (numsSize <= 1)
        return true;
    if (nums[0] == 0)
        return false;
    //循环遍历
    for (left = 0; left < numsSize; left++) {
        if (nums[left] > 0) {
            if (nums[left] >= numsSize-1-left)//循环剪枝，如果中间能能一步跳到位则直接跳出
                return true;
            continue;
        }
        if (nums[left] == 0) {
            right = left;
            //注意这里面的right<numSize-1,这里是让right最大取到numsSize-1，这里面是while循环，不是for循环
            while (right < numsSize - 1 && nums[right] == 0) {
                right++;
            }
            //判断left后面的数中有没有能跳跃到right位置
            for (int j = left - 1; j >= 0; j--) {
                if (nums[j] >= right - j) {
                      //判断left后面的数中有有nums[j]对应的数能跳跃到right的位置
                        left = right;   //跳到目的地right 例如：1 1 2 0 0 3 5 
                        break;
                    }
                if (j == 0) {//left后面的数都不能跳到right，则永远跳不到目的地，返回假
                    return false;
                }
            }
        }
    }
    return true;
}