LeetCode55-跳跃游戏

昨天晚上，竟然做了一个脱单的梦

现在想想还觉得有些可笑

梦境太真实了

我梦到她突然发了一条朋友圈公布恋情

里面的配图是她爸爸说的一句话

这句话里面的几个字都是拼凑在一起的

现在已经记得不太清楚了

但是这个主要情节还是历历在目

早上被闹钟闹醒了

我还躺在床上恍惚了好一会儿

并且掏出了手机翻看朋友圈看看是不是有这条朋友圈

哈哈哈哈哈

其实想想要是昨天晚上没设那个闹钟

好像也不错的样子

---

55-跳跃游戏

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

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

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]
输出: true
解释: 从位置 0 到 1 跳 1 步, 然后跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

思路：

其实本题有点借鉴了贪心算法的思想，即：每一次遍历都取前面所有遍历元素所能到达最远位置的最大值，如果该最大值大于或等于给定数组nums的长度，则说明游戏成功，反之则失败。这一题其实是要比之前的跳跃游戏II要简单许多，因为你不要求出具体的跳跃步骤，只需要给出答案即可，这一题的难点就是对于0元素的处理，因为出现了0说明这一步是不跳的，那么0出现在哪个位置就要好好考虑了。

代码如下：

class Solution:
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) <= 1:
            return True
        max_num = 0
        for index in range(len(nums)-1):
            # 如果跳跃过程中出现了0元素，刚好该元素对应得下标值大于之前元素所能到达的最远值，
            # 说明该0元素位置是目前所能到达的最远位置。如果该位置的元素是0，则无法前进了，说明游戏失败
            if nums[index] == 0 and index >= max_num:
                return False
            max_num = max(max_num, index+nums[index])
            # 如果该最大值大于或等于给定数组nums的长度，则说明游戏成功
            if max_num >= len(nums)-1:
                return True
        return False


if __name__ == "__main__":
    nums = [3, 2, 1, 1, 4]
    final_result = Solution().canJump(nums)
    print(final_result)

执行效率还属中上吧，在60%左右。