【力扣】45. 跳跃游戏 II
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(n) O(n)
空间复杂度:
O ( 1 ) O(1) 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;
}
原文地址:https://blog.csdn.net/w384829981/article/details/137746099
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!