45. 跳跃游戏 II
思路
如果某一个作为 起跳点 的格子可以跳跃的距离是 3,那么表示后面 3 个格子都可以作为 起跳点。
11. 可以对每一个能作为 起跳点 的格子都尝试跳一次,把 能跳到最远的距离 不断更新。
如果从这个 起跳点 起跳叫做第 1 次 跳跃,那么从后面 3 个格子起跳 都 可以叫做第 2 次 跳跃。
所以,当一次 跳跃 结束时,从下一个格子开始,到现在 能跳到最远的距离,都 是下一次 跳跃 的 起跳点。
31. 对每一次 跳跃 用 for 循环来模拟。
32. 跳完一次之后,更新下一次 起跳点 的范围。
33. 在新的范围内跳,更新 能跳到最远的距离。
记录 跳跃 次数,如果跳到了终点,就得到了结果。
int jump(vector<int> &nums)
{
int ans = 0;
int start = 0;
int end = 1;
while (end < nums.size())
{
int maxPos = 0;
for (int i = start; i < end; i++)
{
// 能跳到最远的距离
maxPos = max(maxPos, i + nums[i]);
}
start = end; // 下一次起跳点范围开始的格子
end = maxPos + 1; // 下一次起跳点范围结束的格子
ans++; // 跳跃次数
}
return ans;
}
优化
从上面代码观察发现,其实被 while 包含的 for 循环中,i 是从头跑到尾的。
只需要在一次 跳跃 完成时,更新下一次 能跳到最远的距离。
并以此刻作为时机来更新 跳跃 次数。
就可以在一次 for 循环中处理。
int jump(vector<int>& nums)
{
int ans = 0;
int end = 0;
int maxPos = 0;
for (int i = 0; i < nums.size() - 1; i++)
{
maxPos = max(nums[i] + i, maxPos);
if (i == end)
{
end = maxPos;
ans++;
}
}
return ans;
}
---------------------------------------------------------------------------------------------------------------------------------------------------------------
java版
解法一 :顺藤摸瓜
LeetCode 讨论里,大部分都是这个思路,贪婪算法,我们每次在可跳范围内选择可以使得跳的更远的位置。
如下图,开始的位置是 2,可跳的范围是橙色的。然后因为 3 可以跳的更远,所以跳到 3 的位置。
如下图,然后现在的位置就是 3 了,能跳的范围是橙色的,然后因为 4 可以跳的更远,所以下次跳到 4 的位置。
写代码的话,我们用 end 表示当前能跳的边界,对于上边第一个图的橙色 1,第二个图中就是橙色的 4,遍历数组的时候,到了边界,我们就重新更新新的边界。
public int jump(int[] nums) {
int end = 0;
int maxPosition = 0;
int steps = 0;
for(int i = 0; i < nums.length - 1; i++){
//找能跳的最远的
maxPosition = Math.max(maxPosition, nums[i] + i);
if( i == end){ //遇到边界,就更新边界,并且步数加一
end = maxPosition;
steps++;
}
}
return steps;
}
这里要注意一个细节,就是 for 循环中,i < nums.length - 1,少了末尾。因为开始的时候边界是第 00 个位置,steps 已经加 11 了。如下图,如果最后一步刚好跳到了末尾,此时 steps 其实不用加 11 了。如果是 i < nums.length,i 遍历到最后的时候,会进入 if 语句中,steps 会多加 11。
解法二:顺瓜摸藤
我们知道最终要到达最后一个位置,然后我们找前一个位置,遍历数组,找到能到达它的位置,离它最远的就是要找的位置。然后继续找上上个位置,最后到了第 0 个位置就结束了。
至于离它最远的位置,其实我们从左到右遍历数组,第一个满足的位置就是我们要找的。
public int jump(int[] nums) {
int position = nums.length - 1; //要找的位置
int steps = 0;
while (position != 0) { //是否到了第 0 个位置
for (int i = 0; i < position; i++) {
if (nums[i] >= position - i) {
position = i; //更新要找的位置
steps++;
break;
}
}
}
return steps;
}
这种想法看起来更简单了,为什么奏效呢?我们可以这样想。
从左到右跳的话,2 -> 3 -> 4 -> 12−>3−>4−>1。
从右到左的话,我们找能跳到 11 的最左边的位置,我们找的只能是 44 或者是 44 左边的。
找到 4 的话,不用说,刚好完美。
如果是中间范围 3 和 4 之间的第 2 个 1 变成了 3,那么这个位置也可以跳到末尾的 1,按我们的算法我们就找到了这个 3,也就是 4 左边的位置。但其实并不影响我们的 steps,因为这个数字是 3 到 4 中间范围的数,左边界 3 也可以到这个数,所以下次找的话,会找到边界 3,或者边界 3 左边的数。 会不会直接找到上个边界 2 呢?不会的,如果找到了上一个边界 2,那么意味着从 2 直接跳到 3 和 4 之间的那个数,再从这个数跳到末尾就只需 2 步了,但是其实是需要 3 步的。
上一篇: 题解-花生采摘
下一篇: 数组-最大矩形-困难