首页 > 代码库 > [LeetCode]Jump GameII
[LeetCode]Jump GameII
题目：Jump GameII
如果要求找最小的调数，考虑扩张的思路。
思路如下：
1.首先找起始位能到达的范围是否覆盖了最终位置，并记录下搜索中的最远能到达的位置值，即max{nums[i] + i};
2.如果无法到达最终位置，则跳数加一，并从上一次搜索的最后位置开始，向后搜索到上一次记录的最大值所在的位置。
3.重复上面两步，直到找到最终跳数。
注意：
当数组元素只有1个时，跳数是0；
跳数的初值应该是1。
int jump(vector<int>& nums){
if (nums.size() < 2)return 0;//数组长度小于2
int start = 0, next = nums.at(0),end = nums.size() - 1;
int jump = 1,cur = next;//jump记录跳数，cur记录当前的最大范围
while (cur < end){
jump++;
for (int i = start + 1; i <= next; i++)
{
if (nums.at(i) + i >= end)return jump;
else if (nums.at(i) + i > cur)cur = nums.at(i) + i;
}
start = next;//start是搜索的开始位置
next = cur;//next是搜索的结束位置
}
return jump;
}
[LeetCode]Jump GameII
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。