教做高级料理的网站河南今日重大新闻

Problem: 45. 跳跃游戏 II

问题

思路

核心思路，例如nums[i]=5，那么最远能跳五步；
//那么在这接下来1-5范围内，哪个能让我跳的最远，这个最远指的是
----------------------------------------------------------超过5的范围最远：而不是1-5步内哪个数最大!!!!
//例如: 5 4 1 1 3 1；
//下标: 0 1 2 3 4 5
下一步是跳到nums[4]显然能下一步能跳的更远(注意这个更远的含义，指超出5的范围）
而不是跳到nums[1]，即下一步的步数最大。

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(1)$

Code

int jump(int* nums, int numsSize) {int flag = 0;int feet = 0;int temp, max;temp = max = 0;//核心思路就是例如nums[i]=5，那么最远能跳五步；//那么在这接下来1-5范围内，哪个能让我跳的最远，这个最远指的是//超过5的范围最远：而不是1-5步内哪个数最大：//例如: 5 4 1 1 3 1；//下标: 0 1 2 3 4 5//下一步是跳到nums[4]显然能下一步能跳的更远，而不是跳到nums[1]if (numsSize <= 1)return 0;for (int i = 0; i < numsSize; i++) {if (nums[i] >= numsSize - i - 1)return (feet + 1);//直接一步跳出去for (int j = 1; j <= nums[i]; j++) {if (nums[i + j] >= numsSize - i - j - 1) {return feet + 2;//直接两步跳出去}temp = nums[i + j] - (nums[i] - j);//判断这一步接下来能跳多远，temp//temp<0代表跳不出nums[i]的范围，没有意义if (max < temp) {                max = temp;              //temp>0代表能跳出nums[i]的范围，可以作为候选flag = i + j;}}if (flag != 0) {i = flag - 1;//注意这里要-1，因为for循环会进行一次i++；feet++;flag = 0;//清空标志位max = 0;//清空标志位} else {i = i + nums[i] - 1;feet++;}}return feet;
}