如何优化网站导航,龙岩做网站公司有哪些,首都之窗政务服务平台,怎么做房地产网站Problem: 45. 跳跃游戏 II 文章目录 问题思路复杂度Code 问题 思路
核心思路#xff0c;例如nums[i]5#xff0c;那么最远能跳五步#xff1b;
//那么在这接下来1-5范围内#xff0c;哪个能让我跳的最远#xff0c;这个最远指的是
-------------------------------------… Problem: 45. 跳跃游戏 II 文章目录 问题思路复杂度Code 问题 思路
核心思路例如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//temp0代表跳不出nums[i]的范围没有意义if (max temp) { max temp; //temp0代表能跳出nums[i]的范围可以作为候选flag i j;}}if (flag ! 0) {i flag - 1;//注意这里要-1因为for循环会进行一次ifeet;flag 0;//清空标志位max 0;//清空标志位} else {i i nums[i] - 1;feet;}}return feet;
}
