[LeetCode 55 题 – 跳跃游戏] | 刷题打卡-一一网

掘金团队号上线，助你 Offer 临门！点击查看详情

前言

今天刷到的题主要是采用 贪心算法 实现。所谓贪心算法，就是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。

题目描述

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1：

输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
复制代码

示例 2：

输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
复制代码

提示：

1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/im…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

这题最典型的做法应该就是采用 贪心 策略，对于着腿，我们首先可以得出一个结论：假设当前跳跃到 i 坐标。那么在 i 之前的所有坐标肯定都是可以到达的。所以我们只需要维护对于数组的每个元素，可以跳到的最远距离即可。那么对于第 i-1 个元素，他可以到达的最远距离为 i-1+num[i-1] 。假设此时我们维护的最大跳远距离为 k 。那么，那么在这个点能够跳到的最远距离就是 max(i-1+num[i-1],k) （因为对于 i-1 可能在他之前就有比他能够到达更远的距离 k）。我们再把这个最远距离维护到变量 k 中，根据刚刚得到的结论，只需要比较 k 和 i 的大小即可。

其他解法

我又看了一下 LeetCode 上面其他人的解法，有一些用到了回溯。大致的思路就是从终点（末位置）开始试探回溯。不只是终点，对于任意的一个点i，我们可以遍历[0,i-1]中的点j，如果有nums[j] >= i-j，那么就能够从点i到达点j，随之进一步考察j能否被[0,j-1]中的点到达。如果中途出现不可到达点，则回溯到上一层（离终点较近）的点。

class Solution {
public:
    //本质上是DFS：试探回溯
    bool trace_back(vector<int> & nums, int target)
    {   //判断能否从src到达target
        if (target==0)
            return true;//递归基

        for (int src = target-1; src >= 0; src--)
        {
            if (nums[src] >= target - src)
                return trace_back(nums, src);//继续沿着这个src往前找
        }

        return false;
    }

    bool canJump(vector<int>& nums) {
        int target = nums.size()-1;
        
        return trace_back(nums, target);
    }
};
复制代码

DFS解法转自作者：zongy17
链接：leetcode-cn.com/problems/ju…

最终代码

class Solution {
    public boolean canJump(int[] nums) {
        int k = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > k) return false;
            k = Math.max(k, i + nums[i]);
        }
        return true;
    }
}
复制代码