問題描述

1. 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.
   Determine if you are able to reach the last index.
   For example:
   A = [2,3,1,1,4], return true.
   A = [3,2,1,0,4], return false.

2. 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]
   The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
   Note:You can assume that you can always reach the last index.

問題分析

1. 看到55題目我想到了動規(guī)、帶記憶搜索，然而這兩種做法都非常慢，即使加入了數(shù)組的預(yù)處理。參考了九章算法中的代碼，解題思路為：遍歷數(shù)組，維護(hù)當(dāng)前可達(dá)最遠(yuǎn)的位置，當(dāng)這個位置大于等于最后一個位置時，說明jump成功；當(dāng)遍歷的數(shù)組下標(biāo)超過這個位置，說明當(dāng)前位置已經(jīng)不可達(dá)，jump失敗。
   我咋這么蠢π_π
2. 接著我做了45題，題的設(shè)定基本與55相同，不同的是此題要求的是最少跳數(shù)。我以為這下該用到動規(guī)/帶記憶搜索了，結(jié)果還是慢成狗……參考了九章算法中的代碼，解題思路為：記錄一個p數(shù)組，p[i]代表的是到達(dá)i位置的最少跳數(shù)（p是非減的），其得到的方法為遍歷nums數(shù)組，遍歷到位置i時，將p數(shù)組中第一個未賦值位置到i+nums[i]之間的位置都賦為p[i]+1。這么做的依據(jù)在于，如果p[j]位置沒有賦值，說明在前面i-1個位置都無法到達(dá)j位置，當(dāng)下一個位置i可以到達(dá)j時，到達(dá)i的最小跳數(shù)p[i]加上從i到j(luò)的一跳，即為到j(luò)的最小跳數(shù)。

AC代碼

55. Jump Game

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

只要辣么短！Runtime: 60 ms, which beats 76.43% of Python submissions.
45. Jump Game II

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        p = [0]
        lp = 1
        for i in range(n-1):
            while i + nums[i] >= lp and lp < n:
                p.append(p[i] + 1)
                lp += 1
        return p[-1]

只要辣！么！短！Runtime: 68 ms, which beats 74.32% of Python submissions.