107. 跳完数组的最少跳数

https://algocasts.io/episodes/AEpo1vmQ

我用python写第一种写法,leetcode显示超时
通过不了的case是[25000,24999,24998…,1]。
是因为第二个for(last,i,-1)使得时间复杂度接近O(n^2)的原因吗?

@Yifu_Chen

不是,都是 O(n) 的时间复杂度。我把第一种解法翻译到 Python 是可以 Pass 的,所以应该是你哪里没写对。下面是代码:

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums is None or len(nums) == 0:
            return -1
        n, max = len(nums), 0
        d = [0] * n
        for i in xrange(n):
            if max >= n-1:
                return d[n-1]
            if i > max:
                return -1
            max = i+nums[i] if i+nums[i] > max else max
            last = max if max < n-1 else n-1
            for j in xrange(last, i, -1):
                if d[j] != 0:
                    break
                d[j] = d[i] + 1
        return -1
1赞

hello。我发现是什么问题了,我使用python3的语法,但是用python2的compiler提交。主要问题是出在在range()和xrange()上,导致超时:sweat: