LeetCode - Jump Game（跳躍遊戲）

題目描述

給定一個由非負整數組成的數組 nums，其中 nums[i] 表示在位置 i 可以跳躍的最遠距離。你的目標是判斷是否可以從數組的起始位置跳到最後一個位置。如果可以到達，返回 True；否則，返回 False。

範例：

輸入：nums = [2,3,1,1,4]
輸出：True
解釋：從位置 0 開始跳 1 步到達位置 1，然後跳 3 步到達最後位置。

輸入：nums = [3,2,1,0,4]
輸出：False
解釋：無論如何都無法跳到最後一個位置。

解法思路

我們可以使用貪心算法來解決這個問題，即不斷更新能夠跳躍到的最遠位置。具體步驟如下：

1. 初始化最遠可達位置：設置變量 max_reachable 表示當前能跳到的最遠位置，初始化為 0。

2. 遍歷陣列：從起始位置開始遍歷數組，每次都檢查當前位置 i 是否在 max_reachable 的範圍內（即 i <= max_reachable）。
   • 如果可以達到該位置，則更新 max_reachable 為 max(max_reachable, i + nums[i])。
   • 如果在遍歷過程中 max_reachable 超過或等於最後一個位置，則說明可以到達終點，返回 True。
3. 檢查是否無法到達：如果遍歷結束後 max_reachable 仍然小於最後一個位置，則返回 False。

範例代碼

以下是 Python 的實現：

def canJump(nums):
    max_reachable = 0  # 初始化最遠可達位置

    for i in range(len(nums)):
        if i > max_reachable:  # 如果當前位置超出可達範圍，返回 False
            return False
        max_reachable = max(max_reachable, i + nums[i])  # 更新最遠可達位置
        if max_reachable >= len(nums) - 1:  # 如果可以到達或超過最後位置，返回 True
            return True

    return False

代碼解析

1. 初始化 max_reachable：從位置 0 開始跳，初始化 max_reachable 為 0。
2. 更新可達範圍：遍歷數組，每當遇到新位置 i 時，如果 i 在 max_reachable 範圍內，則更新 max_reachable，使其等於 max(max_reachable, i + nums[i])。
3. 提前返回：若在遍歷過程中，max_reachable 超過或達到最後位置，則返回 True，表示可以跳到終點。
4. 無法到達的情況：如果遍歷結束後 max_reachable 無法到達最後位置，則返回 False。

時間和空間複雜度

• 時間複雜度：O(n)，其中 n 是數組的長度，我們只需遍歷數組一次。
• 空間複雜度：O(1)，只使用了常數空間來存儲變量。