文章目錄

• 1. 題目
• • 1.1 示例
  • 1.2 說明
  • 1.3 提示
  • 1.4 進階
• 2. 解法一（動態規劃）
• • 2.1 分析
  • • 2.1.1 定義狀態
    • 2.1.2 狀態轉移
  • 2.2 解答
  • 2.3 復雜度
• 3. 解法二（貪心）
• • 3.1 分析
  • 3.2 解答
  • 3.3 復雜度

1. 題目

給定一個非負整數陣列 nums ，你最初位于陣列第一個下標 ，陣列中的每個元素代表你在該位置可以跳躍的最大長度，判斷你是否能夠到達最后一個下標，

1.1 示例

• 示例 1 1 1：

  • 輸入： nums = [2, 3, 1, 1, 4]
  • 輸出： true
  • 解釋： 可以先跳 1 1 1 步，從下標 0 0 0 到達下標 1 1 1 ，然后再從下標 1 1 1 跳 3 3 3 步到達最后一個下標，

• 示例 2 2 2：

  • 輸入： nums = [3, 2, 1, 0, 4]
  • 輸出： false
  • 解釋： 無論怎樣，總會到達下標為 3 3 3 的位置，但該下標的最大跳躍長度是 0 0 0 ， 所以永遠不可能到達最后一個下標，

1.2 說明

• 來源： 力扣（LeetCode）
• 鏈接： https://leetcode-cn.com/problems/jump-game

1.3 提示

• 1 ≤ nums.length ≤ 3 ? 1 0 4 1 \le \text{nums.length} \le 3 * 10^4 1≤nums.length≤3?104
• 0 ≤ nums [ i ] ≤ 1 0 5 0 \le \text{nums}[i] \le 10^5 0≤nums[i]≤105

1.4 進階

在陣列最后一個下標可達時，你可以進一步輸出具體的跳躍情況么？

2. 解法一（動態規劃）

2.1 分析

2.1.1 定義狀態

這里使用 dp[i] 表示下標 i 的位置是否可達，

2.1.2 狀態轉移

在已經下標 i 之前位置的可達情況 dp[0] 、 dp[1] 一直到 dp[i - 1] 的前提下，想要確定 dp[i] 的取值時，只要判斷 dp[0] 、 dp[1] 一直到 dp[i - 1] 中是否有某位置 j 可達且從該位置可繼續到達下標為 i 的位置，即是否有 dp[j] is True and dp[j] + j >= i ，

2.2 解答

根據上述分析，可以得到下列解答：

from typing import List


class Solution:
    def can_jump(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return True
        dp = [False for _ in range(len(nums))]
        dp[0] = True
        if nums[0] >= 1:
            dp[1] = True
        for i in range(2, len(nums)):
            for j in range(i):
                if dp[j] is True and nums[j] >= i - j:
                    dp[i] = True
                    break
        return dp[-1]


def main():
    # nums = [2, 3, 1, 1, 4]
    nums = [3, 2, 1, 0, 4]
    sln = Solution()
    print(sln.can_jump(nums))


if __name__ == '__main__':
    main()

2.3 復雜度

• 時間復雜度： O ( n 2 ) O(n^2) O(n2)，其中 n n n 是陣列 nums 的長度；
• 空間復雜度： O ( n ) O(n) O(n)，

3. 解法二（貪心）

實際上，上述解法雖理論上可行，但由于時間復雜度為 O ( n 2 ) O(n^2) O(n2) ，因而直接提交會超時，

3.1 分析

• 作者： LeetCode-Solution

設想一下，對于陣列中的任意一個位置 i，我們如何判斷它是否可以到達？根據題目的描述，只要存在一個位置 j，它本身可以到達，并且它跳躍的最大長度為 j + nums[j] ，這個值大于等于 i，即 j + nums[j] >= i，那么位置 i 也可以到達，

換句話說，對于每一個可以到達的位置 j，它使得 j + 1 、 j + 2 一直到 j + nums[j] 這些連續的位置都可以到達，

這樣一來，我們依次遍歷陣列中的每一個位置，并實時維護最遠可以到達的位置，對于當前遍歷到的位置 j，如果它在最遠可以到達的位置的范圍內，那么我們就可以從起點通過若干次跳躍到達該位置，同時可能需要用 j + nums[j] 更新最遠可以到達的位置，

在遍歷的程序中，如果最遠可以到達的位置大于等于陣列中的最后一個位置，那就說明最后一個位置可達，此時就可以直接回傳 True 作為答案，反之，如果在遍歷結束后，最后一個位置仍然不可達，就需要回傳 False 作為答案，

3.2 解答

from typing import List


class Solution:
    def greedy_can_jump(self, nums: List[int]) -> bool:
        right_most = nums[0]
        for i in range(len(nums)):
            if i <= right_most:  # Position i is reachable
                right_most = max(i + nums[i], right_most)  # right_most may need update under this condition
            if right_most >= len(nums) - 1:  # Last position is at least reachable from position i
                return True
        return False


def main():
    # nums = [2, 3, 1, 1, 4]
    nums = [3, 2, 1, 0, 4]
    sln = Solution()
    print(sln.greedy_can_jump(nums))


if __name__ == '__main__':
    main()

實際上，根據上述思路，上述核心代碼還可以寫成如下兩種形式：

def also_greedy_can_jump(self, nums: List[int]) -> bool:
    right_most = nums[0]
    for i in range(len(nums)):
        if i > right_most:
            return False
        right_most = max(i + nums[i], right_most)
    return True

def optimized_can_jump(self, nums: List[int]) -> bool:
    right_most = nums[0]
    i = 0
    while i <= right_most and right_most < len(nums) - 1:
        right_most = max(i + nums[i], right_most)
        i += 1
    return right_most >= len(nums) - 1

3.3 復雜度

• 時間復雜度： O ( n ) O(n) O(n)，其中 n n n 為陣列的大小，只需要訪問 nums 陣列一遍，共 n n n 個位置，
• 空間復雜度： O ( 1 ) O(1) O(1)，不需要額外的空間開銷，

實際上，這題還可以通過逆向的思維來解答，即從最后一個位置開始遍歷，一次判斷從其前面的位置是否可以跳至該位置，在遍歷結束后判斷當前位置是否為第一個位置：

from typing import List


class Solution:
    def backwards_can_jump(self, nums: List[int]) -> bool:
        pos = len(nums) - 1
        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= pos:
                pos = i
        return pos == 0


def main():
    # nums = [2, 3, 1, 1, 4]
    nums = [3, 2, 1, 0, 4]
    sln = Solution()
    print(sln.backwards_can_jump(nums))


if __name__ == '__main__':
    main()