Jump Game II

题目描述

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example: Given array A = [2,3,1,1,4]

解题方法

方法1，DP

就是用一个array记录目前的最小jump数，然后不断往前更新

• 时间复杂度 O(n^2)
• 空间复杂度 O(n)

方法2

因为这里是从头开始，并且要求的是最小的jump次数，所以在上面的DP中其实有 很多的重复运算，如果已经求出最小的jump次数，那么后面的其实就不用算了。

我们可以将思路换为，每次进一个step，计算出这个step能够达到的范围，如果这个范围 不包含结尾，就之后再前进一个step,再计算。 这样不断从最小step推进，就可以省去重复计算的 过程。

Solution

DP, 超时

class Solution:
    # @param A, a list of integers
    # @return an integer
    def jump(self, A):
        # write your code here
        nums = A

        if not nums:
            return 0

        length = len(nums)
        minJumps = [sys.maxint for i in range(length)]
        minJumps[0] = 0
        for i in range(length):
            jumpNum = nums[i]
            farest = min(length - 1, i + jumpNum)
            for j in range(i+1, farest + 1):
                if minJumps[j] > minJumps[i] + 1:
                    minJumps[j] = minJumps[i] + 1

        return minJumps[length - 1]

O(n)的方法

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        if length <= 1:
            return 0

        curStart = 0
        end = 0
        curStep = 0

        while curStart <= end:
            curEnd = end
            for i in range(curStart, curEnd + 1):
                if i + nums[i] >= length - 1:
                    return curStep + 1
                end = max(end, i + nums[i]) # 更新下一个step能达到的end
            curStep += 1
            curStart = curEnd + 1 # 下一个step的开头

        return sys.maxint

Reference