Leetcode经典题7--跳跃游戏

跳跃游戏

题目描述：

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

输入输出示例：

输入：nums = [2,3,1,1,4]

输出：true

解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

解决方案

方式一：贪心算法

算法思想：

通过遍历数组中的每一个位置，并实时维护 最远可以到达的位置。对于当前遍历到的位置 x，如果它在 最远可以到达的位置的范围内，那么我们就可以从起点通过若干次跳跃到达该位置，因此我们可以用 x+nums[x] 更新 最远可以到达的位置。

在遍历的过程中，如果在最远可以到达的位置大于等于数组中的最后一个位置，说明一定能够到达数组的最后一个位置

举例说明：

[2, 3, 1, 1, 4]

我们一开始在位置 0，可以跳跃的最大长度为 2，因此最远可以到达的位置被更新为 2；

我们遍历到位置 1，由于 1≤2，因此位置 1 可达。我们用 1 加上它可以跳跃的最大长度 3，将最远可以到达的位置更新为 4。由于 4 大于等于最后一个位置 4，因此我们直接返回 True。

实现代码：

public class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        //遍历数组中的每个元素，如果当前元素在能够到达范围之内，更新最远的可达范围
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                //如果数组的最后一个元素也在可大范围之内，那么就返回true
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }
}

复杂度分析

时间复杂度：O(n)

其中 n 为数组的大小。只需要访问 nums 数组一遍，共 n 个位置。

空间复杂度：O(1）

不需要额外的空间开销。

跳跃游戏进阶版

题目描述

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

输入输出示例

输入: nums = [2,3,1,1,4]

输出: 2

解释: 跳到最后一个位置的最小跳跃数是 2。

  从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

解题方案：

方式一：反向查找出发位置

算法思想

我们的目标是到达数组的最后一个位置，因此我们可以考虑最后一步跳跃前所在的位置，该位置通过跳跃能够到达最后一个位置。

本着跳跃次数最小的思想，我们可以寻找最后一步跳跃前的位置，我们选择距离最后一个位置最远的位置

不断贪心的寻找距离最远的位置，直到找到数组的开始位置，到最后一个位置的步数最少

实现代码：

class Solution {
    public int jump(int[] nums) {
        int position = nums.length - 1;//最短步数到达数组末尾所经过的数组各个位置
        int steps = 0;//步数
        while (position > 0) {//倒着找
            for (int i = 0; i < position; i++) {//如果要寻找最远的位置，从头开始遍历
            //如果当前位置能够到达position位置，位置i一定为能到达position的最远位置
                if (i + nums[i] >= position) {
                    position = i;将该位置变为positon
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
}

复杂度分析

时间复杂度：O(n2)，

其中 n 是数组长度。有两层嵌套循环，在最坏的情况下，例如数组中的所有元素都是 1，position 需要遍历数组中的每个位置，对于 position 的每个值都有一次循环。

空间复杂度：O(1)。

方式二：正向查找可到达的最大位置

算法思想 :

「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。

举例说明：

对于数组 [2,3,1,2,4,2,3]，初始位置是下标 0，从下标 0 出发，最远可到达下标 2。下标 0 可到达的位置中，下标 1 的值是 3，从下标 1 出发可以达到更远的位置，因此第一步到达下标 1。

在具体的实现中，我们维护当前能够到达的最大下标位置，记为边界。我们从左到右遍历数组，到达边界时，更新边界并将跳跃次数增加 1。

在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。

实现代码：

class Solution {
    public int jump(int[] nums) {
        int length = nums.length;
        int end = 0;//边界
        int maxPosition = 0; //可到达的最远位置
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {//遍历数组
            maxPosition = Math.max(maxPosition, i + nums[i]); //能够到达的最远位置
            if (i == end) {
                end = maxPosition;//更新边界
                system out printIn(end);
                steps++;
            }
        }
        return steps;
    }
}

深度解析：

如下图，开始的位置是 2，可跳的范围是橙色的。然后因为 3 可以跳的更远，所以跳到 3 的位置。

如下图，然后现在的位置就是 3 了，能跳的范围是橙色的，然后因为 4 可以跳的更远，所以下次跳到 4 的位置。

写代码的话，我们用 end 表示当前能跳的边界，对于上边第一个图的橙色 1，第二个图中就是橙色的 4，遍历数组的时候，到了边界，我们就重新更新新的边界。

原文地址：https://blog.csdn.net/2301_81453175/article/details/144396080

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！