題目描述
給定一個非負整數陣列 nums，其中每個元素代表你在該位置最多可以跳躍的步數，目標是從陣列的第一個位置跳到最後一個位置。請找出你所需要的最小跳躍次數。
- 假設總是可以到達最後一個位置。
範例
範例 1：
輸入: nums = [2, 3, 1, 1, 4]
輸出: 2
解釋: 第一次跳 1 步，從位置 0 到位置 1，然後跳 3 步到達最後一個位置。
範例 2：
輸入: nums = [2, 3, 0, 1, 4]
輸出: 2
解釋: 第一次跳 1 步，從位置 0 到位置 1，然後跳 3 步到達最後一個位置。
解題思路
這是一個典型的最短路徑問題，但不需要真正構建圖。我們需要以最少的跳躍次數到達終點。
解法一：貪心演算法 (Greedy)
思路
- 使用貪心的方式，從左到右遍歷陣列。
- 維護兩個變數：
- current_end：當前步數所能到達的最遠位置。
- farthest：從當前位置出發能到達的最遠位置。
- 當遍歷到
current_end時，增加一步，並將current_end更新為farthest。 - 當到達或超過陣列的最後一個位置時，停止遍歷。
程式碼
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return 0 # 如果只有一個元素，不需要跳躍
jumps = 0 # 跳躍次數
current_end = 0 # 當前步數能到達的最遠距離
farthest = 0 # 目前能到達的最遠距離
for i in range(n - 1): # 不需遍歷最後一個位置
farthest = max(farthest, i + nums[i]) # 更新最遠距離
if i == current_end: # 到達當前步數能到達的最遠距離
jumps += 1
current_end = farthest # 更新下一步能到達的最遠距離
if current_end >= n - 1: # 如果能到達終點，提前結束
break
return jumps
時間與空間複雜度
- 時間複雜度：O(n)，遍歷一次陣列即可。
- 空間複雜度：O(1)，只使用常數額外空間。
解法二：動態規劃 (Dynamic Programming)
思路
- 建立一個一維陣列
dp，其中dp[i]表示到達位置i所需的最小跳躍次數。 - 初始化
dp[0] = 0（起點需要 0 次跳躍）。 - 從位置 1 開始，對於每個位置
i，找到所有能跳到該位置的前一個位置j，更新dp[i] = min(dp[i], dp[j] + 1)。 - 最終返回
dp[n-1]。
程式碼
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
dp = [float('inf')] * n
dp[0] = 0 # 起點不需要跳躍
for i in range(1, n):
for j in range(i):
if j + nums[j] >= i: # 如果從位置 j 可以跳到位置 i
dp[i] = min(dp[i], dp[j] + 1) # 更新到位置 i 的最小跳躍次數
return dp[-1]
時間與空間複雜度
- 時間複雜度：O(n^2)，雙重迴圈。
- 空間複雜度：O(n)，需要額外的 DP 陣列。
結論
- 貪心演算法是最佳解法，適合大數據量，且邏輯清晰。
- 動態規劃更適合初學者理解，但時間複雜度較高。
希望這篇解題教學幫助到大家！
