跳表算法

题意

在一个一维数组中,每个元素都是一个数字,代表从这一点能往下走几步。给定一个数组,判断这个数组从头开始能不能走到数组最后一个元素。

分析

对这个问题首先想到的是路径规划,如果我能找到一条路径从第0个元素一直走到最后一个元素,那么就可以。如果所有可能的路径都不能走到最后一个元素,那么就不可以。

于是,我给出了一个低效率的算法:

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if(len(nums) < 2):
            return True
        
        return self.innerCanJump(nums)
        
    def innerCanJump(self, nums):
        
        if(len(nums) == 0):
            return False
        
        if(len(nums) == 1):
            return True
        
        for i in range(nums[0]):
            if self.innerCanJump(nums[i+1:]):
                return True
        
        return False
            

修正

仔细分析题意可以发现,我们需要的不是找到这条路径,而是判断能不能,所以问题就变得简单的,我们不需要存储这条路径,只需要判断路径覆盖范围。

从第0个元素起,标记最大可到达位置max,如果从0到max中有一个元素的最大可到达位置大于max,那么最大可到达位置标记为max2。遍历数组并更新max的位置,如果标记到某一个元素就能覆盖到最后一个元素的位置,那么就可以。反之如果标记到一半就不能进行了,就不可以。

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        reach = 1
        for i in range(len(nums)):
            if (reach < i + 1):
                break;
            reach = max(reach, i + 1 + nums[i])
        return reach >= len(nums)