欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

45. 跳跃游戏 II

程序员文章站 2022-07-07 15:54:42
...

思路
如果某一个作为 起跳点 的格子可以跳跃的距离是 3,那么表示后面 3 个格子都可以作为 起跳点。
11. 可以对每一个能作为 起跳点 的格子都尝试跳一次,把 能跳到最远的距离 不断更新。

如果从这个 起跳点 起跳叫做第 1 次 跳跃,那么从后面 3 个格子起跳 都 可以叫做第 2 次 跳跃。

所以,当一次 跳跃 结束时,从下一个格子开始,到现在 能跳到最远的距离,都 是下一次 跳跃 的 起跳点。
31. 对每一次 跳跃 用 for 循环来模拟。
32. 跳完一次之后,更新下一次 起跳点 的范围。
33. 在新的范围内跳,更新 能跳到最远的距离。

记录 跳跃 次数,如果跳到了终点,就得到了结果。

45. 跳跃游戏 II

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 的位置。
45. 跳跃游戏 II
如下图,然后现在的位置就是 3 了,能跳的范围是橙色的,然后因为 4 可以跳的更远,所以下次跳到 4 的位置。

45. 跳跃游戏 II
写代码的话,我们用 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。

45. 跳跃游戏 II

解法二:顺瓜摸藤

我们知道最终要到达最后一个位置,然后我们找前一个位置,遍历数组,找到能到达它的位置,离它最远的就是要找的位置。然后继续找上上个位置,最后到了第 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;
}

这种想法看起来更简单了,为什么奏效呢?我们可以这样想。
45. 跳跃游戏 II
从左到右跳的话,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 步的。