題目

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Example 1

1
2
3
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2

1
2
3
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

解釋題目

給你一個 array，叫做 nums，可以把 nums 想像成一個樓梯，每一層樓都是用 index 來表示，起始位置會是第 0 層，而樓梯上的數字代表可以前進的最大步數。題目要問的是: 給你任意一個 nums ( 樓梯 )，是否能爬到最上層，最後要回傳 true 或 false。

思路 (1)

  1. 以 [ 3, 0, 2, 0, 0 ] 為例，想像成爬樓梯的概念，有 0 , 1 , 2 , 3 樓，樓層是 index 的概念，樓梯上的數字，是指可以走的最大層數

  2. 這題要從頂樓往回推算比較容易想，要爬到頂樓的條件是:

    前一層的樓數 ( index ) + 可以爬的最大步數 ≥ 頂樓樓數 ( goal )

  3. 可以使用雙指針解題，右指針 ( goal ) 是 nums 的最後一個數字，左指針 ( index ) 是 nums 的倒數第二個數字，條件設定是「左指針」走到第 0 層結束，代表確實可以從頭走到尾。

  4. 從目標樓層 ( 4 樓 ) 往回推算，如果要達到目標樓層，左指針的 index ( 3 樓 ) + 層數 ≥ 目標樓層的 index ( 4 樓 )。

    1. 若條件成立 ⇒ 代表一定能從 3 樓走到 4 樓，那我們要繼續檢查，有沒有辦法從下一樓層 ( 2樓 ) 走到 3 樓，因為只要能走到 3 樓，就能走到目標樓層 4 樓。
      • 此時目標樓層 ( goal ) = 左指針樓層 ( index )
      • 接著，繼續檢查左指針樓層 + 層數 ≥ 目標樓層。，左指針樓層會往下走一層 ( 2 樓 )，也就是左指針樓層 = 左指針樓層 - 1。
    2. 若條件不成立 ⇒ 代表沒辦法從左指針樓層 ( 3 樓 ) 走到目標樓層 ( 4 樓 ) ，所以就要往下一層樓檢查，檢查下一層 ( 2 樓 ) + 層數有沒有辦法走到目標樓層。
      • 此時左指針樓層 = 左指針樓層 - 1

  5. 每次迴圈，左指針 ( index ) 樓層都要往下走一層。

  6. 最後，若右指針 ( goal ) 可以抵達第 0 層，就代表可以從 0 層一直到頂樓，return True，不行則返回 False

  7. 此解法，時間複雜度為 O(n)，空間複雜度為 O(1)。

程式碼 (1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        goal = n - 1
        idx = n - 2
        while idx >= 0:
            if idx + nums[idx] >= goal:
                goal = idx
            idx = idx - 1
    
        if goal == 0:
            return True
        else:
            return False

思路 (2)

  1. 另外也可用 「動態規劃」(Dynamic Programming) 的解法，因為前一題有用過動態規劃的解法，所以可以嘗試用不一樣的思維解題。

  2. 動態規劃的方法，就是要去記錄每次走到當前位置時 ( 假設當前位置為第 0 層 ，第 0 層標記為 true )，下個位置可以抵達的最遠樓層，並標記為 true。

    • 假設下個位置可以抵達的最遠樓層為第 3 層 ，那麼第 0, 1, 2 層標記為 true。
    • 每走一步都要重新標記，因為有可能第三層在第一步被標記為 True，但在第二步被標記為 False。

  3. dp[i] 是布林值，代表是否能到達第 i 個位置。

  4. 最後要回傳 dp[n - 1]，是否能到達最後一個位置。

  5. 以 [ 3, 0, 2, 0, 0 ] 為例，在第 0 層時，可以標記的層數是 3 ，最多可以走 3 步 ( 走 1 步到 index 1，走 2 步到 index 2，走 3 步到 index 3 )，所以是 range (1, 4)。

    特別注意: 走的步數必須小於 len(nums)，所以取 min

  6. 此解法，時間複雜度為 O(n^2)，空間複雜度為 O(n)。

程式碼 (2)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def canJump(self, nums):
        n = len(nums)
        dp = [False] * n  # 初始化 dp 陣列為 False
        dp[0] = True  # 起點設為 True
        
        for i in range(n - 1):
            if dp[i]:  # 如果可到達當前位置
                for j in range(i + 1, min(i + 1 + nums[i], n)): # 計算當前位置可以抵達的範圍，從下個位置開始標記 
                    dp[j] = True
        
        return dp[n - 1]  # 回傳是否能到達最後一個位置