leetcode 45. 跳跃游戏 II

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++。

        下面看代码：

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;}
};