2023.7.30
class Solution {
public:
int jump(vector<int>& nums) {
int step = 0;
int cover = 0;
int largest = 0;
if(nums.size() == 1) return step;
for(int i=0; i<nums.size(); i++)
{
cover = max(cover , i+nums[i]); //最大覆盖范围
if(cover >= nums.size()-1) return step+1;
if(largest == i) //需要开始新的一步
{
step++;
largest = cover;
}
}
step++;
return step;
}
};本题为 跳跃游戏I 的升级版，保证可以到达终点的情况下，要求出最短的跳跃次数。
还是仿照 跳跃游戏I 的思路，定义一个cover用于记录最大覆盖范围，终止条件是： cover >= nums.size()-1 ，还要定义一个变量largest用于记录当前最远覆盖范围的下标，当i遍历到largest时，就要开始新的一步，即step++。文章来源：https://www.toymoban.com/news/detail-621162.html
下面看代码：文章来源地址https://www.toymoban.com/news/detail-621162.html
class Solution {
public:
int jump(vector<int>& nums) {
int step = 0;
int cover = 0;
int largest = 0;
if(nums.size() == 1) return step;
for(int i=0; i<nums.size(); i++)
{
cover = max(cover , i+nums[i]); //最大覆盖范围
if(cover >= nums.size()-1) return step+1; //终止条件
if(largest == i) //需要开始新的一步
{
step++;
largest = cover;
}
}
step++;
return step;
}
};到了这里，关于leetcode 45. 跳跃游戏 II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
