45 跳跃游戏II
普通版
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
int start = 0, end = start + 1;
int ans = 0;
while(end < n){
int nextStep;
for(int i = start; i < end; i++){
nextStep = max(nextStep, i + nums[i]);
}
ans++;
start = end;
end = nextStep + 1;
}
return ans;
}
};
优化版
在跳跃游戏中,我们的思路是:
- 我们不确定给定nums[i] 需要走多少步才能到达最后一个元素
- 为此,我们进行了问题转换,我们不需要知道走多少步,只需要更新最大到达范围maxPos,如果maxPos大于等于n - 1,说明能够到达n - 1
在跳跃游戏II中,我们仍然能仿照这个思路:
- 如果当前maxPos没有覆盖n - 1,那我们跳跃一次
- 如果maxPos大于等于n - 1,说明能够到达n - 1,不需要再跳跃
不同之处在于:跳跃游戏II默认我们能够到达最后一个元素,求跳跃次数
如何能让跳跃次数最大,我们只需要走到maxPos的时候再跳跃即可 -> 我们维护两个maxPos,一个表示当前能够到达的最大位置,另一个表示下一次能够到达的最大位置
这里需要特别注意的一点:跳跃游戏II默认我们能够到达最后一个元素,因此我们不需要遍历到 n -1个元素,因为在那之前,我们一定能让maxPos覆盖n - 1
如果包含了n - 1反而有可能让结果多加一次(end 刚好等于n - 1)
class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
int end = 0;
int maxNextStep = 0;
int step = 0;
// 注意:i < n - 1 而不是i < n
for (int i = 0; i < n - 1; i++) {
// 这里不需要if判断了,因为题目说一定能到达n - 1
maxNextStep = max(maxNextStep, i + nums[i]);
if (i == end) {
++step;
end = maxNextStep;
}
// 与跳跃游戏不同,这里不需要maxNextStep >= n - 1判断,因为我们知道一定能到达n - 1
// 如果加了这个判断,表明我们已经知道覆盖范围大于n - 1了
// 但是这时候i还没走到更新后的end,我们需要让i走到end之后让step加一
}
return step;
}
};