Leetcode-55解题思路及总结

✨第55题跳跃游戏，题目如下：
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

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

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

解题思路1

很容易想到的一种解法是，从后往前遍历数组，依次标记每个位置是否可以到达最后一个位置，最后返回标记数组的第一个元素即可。对于数组中任意一个元素，要得到对应的标记，需要先判断自身所在位置+元素大小是否超过数组大小，若大于则为True，若小于则需要遍历自身所在位置后元素大小个数的标记数组。因此最坏情况的是时间复杂度为O(N^2)，空间复杂度O(N)

对于示例1来说，标记数组为[True, True, True, True]，对于示例2来说，标记数组为[False, False, False, False, True]

代码示例如下：

    def canJump(self, nums):
        if len(nums) < 2:
            return True
        num = len(nums)
        bool_list = [False] * num
        for index in range(num):
            i = num - index - 1
            if (i + nums[i]) >= (num - 1):
                bool_list[i] = True
            else:
                for j in range(1, nums[i]+1):
                    if bool_list[i+j]:
                        bool_list[i] = True
                        continue
        # print bool_list
        return bool_list[0]

解题思路2

由于题设只需要判断从第一个位置开始能否跳跃到最后一个位置，因此可以简化为判断从第一位置开始能否跳到“可以跳到最后位置的”倒数第二个位置，依次类推，可以简化为判断是否可以跳到倒数第三个位置，倒数第四个、第五个......直至到数组的开始。若从第一位置可以跳到找到的“倒数第N个位置”，即 a[0] >= end，则返回True，否则返回False。

因此问题简化为，从后遍历找最小end的问题，由于只需要遍历数组1遍，因此时间复杂度为O(N)。

对于示例1来说，从后遍历数组，end的值依次为，4，3，2，1，最后2>1的，因此返回True。

对于示例2来说，从后遍历数组，由于没有能够1次到达最后位置的元素，因此end值依旧是4，而3<4，因此返回False。

示例代码如下：

    def canJump(self, nums):
        if len(nums) < 2:
            return True
        num = len(nums)
        end = num - 1
        start = end - 1
        while start > 0:
            if nums[start] + start >= end:
                end = start
            start -= 1
        return nums[start] + start >= end