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;
}