我要评论题目链接：45. 跳跃游戏 ii - 力扣（leetcode）
数组的元素表示可以跳的最大长度，保证可以跳到最后，求跳的最少的次数
不断更新当前可以跳跃到达的最远距离farthest，记录上次跳跃可以到达的位置foothold，当到这个位置的时候，跳跃计数，更新foothold为farthest
逻辑就是如果我到达了可以到达的最远位置，说明我跳了一次，可以理解为上一次跳跃完成，但是由于最后一次跳跃也是跳最远距离可能超过了最后一个位置，无法计数，所以一开始00的时候就计数了一次，并且最后一次不计数
class solution {
public:
int jump(vector<int> &nums) {
int farthest = 0, foothold = 0, ans = 0;
for (int i = 0; i < nums.size() - 1; ++i) {
farthest = max(farthest, i + nums[i]);
if (i == foothold) {
++ans;
foothold = farthest;
}
}
return ans;
}
};
发表评论