【華為機試】55. 跳躍游戲

文章目錄

55. 跳躍游戲
- 題目描述
- 示例 1：
- 示例 2：
- 提示：
- 解題思路
- - 一、問題本質與建模
  - 二、方法總覽與選擇
  - 三、貪心算法的正確性（直觀解釋 + 循環不變式）
  - 四、反向貪心：等價但有啟發的視角
  - 五、與動態規劃的對比與誤區澄清
  - 六、過程可視化（示例一）
  - 七、邊界與坑點匯總
  - 八、復雜度與工程實踐
  - 九、相關變體與延伸
  - 十、常見面試追問（簡答）
- 代碼實現
- 測試用例設計
- 小結
- 完整題解代碼

55. 跳躍游戲

題目描述

給你一個非負整數數組 nums ，你最初位于數組的第一個下標。數組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最后一個下標，如果可以，返回 true ；否則，返回 false 。

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 10^4
0 <= nums[i] <= 10^5

解題思路

一、問題本質與建模

將每個位置 i 看作一“跳板”，可直接把你送到區間 [i+1, i+nums[i]] 中的任意位置（含邊界）。問題轉化為：從起點 0 出發，是否存在一條“跳板鏈”使得你可以覆蓋到 n-1。這天然是一個“可達性”問題。

直覺上，只要我們始終維護“從已訪問過的所有位置出發，能到達的最遠下標”，就能判斷是否觸達終點。這便是貪心策略的核心：每前進一步，就盡力擴展我們能到達的“最遠邊界”。

二、方法總覽與選擇

graph TDA[跳躍游戲 方法選擇] --> B[貪心: 維護最遠可達]A --> C[反向貪心: 收縮 lastGood]A --> D[DP: 從后往前可達性]B --> E[O(n)時間 O(1)空間 最優]C --> F[O(n)時間 O(1)空間 等價視角]D --> G[O(n^2)時間 O(n)空間 僅教學]

貪心（正向）：迭代 i 并維護 farthest = max(farthest, i + nums[i])
反向貪心：維護“必須到達”的最右位置 lastGood，若 i + nums[i] >= lastGood 則 lastGood = i
DP：dp[i] = OR(dp[j]) for j in (i, i+nums[i]]，直觀但最壞 O(n2)

三、貪心算法的正確性（直觀解釋 + 循環不變式）

直觀解釋（區間擴展模型）

在第 i 步之前，我們已經保證所有 <= i 的點都“被訪問過”（即可達）。
訪問 i 時，i 能貢獻的新可達區間為 [i+1, i+nums[i]]，因此最遠可達位置應被更新為 max(farthest, i+nums[i])。
一旦 farthest >= n-1，說明終點被區間覆蓋，立即返回 true。

循環不變式（關鍵性質）

不變式：在進入第 i 次循環時，[0, i] 中所有點均可達，且 farthest 是這些點能共同“覆蓋”的最遠下標。
維持：若 i <= farthest，則 i 可達；更新 farthest = max(farthest, i+nums[i]) 后，不變式對 i+1 繼續成立。
違例檢測：若出現 i > farthest，說明 i 不可達，不變式被打破，也就不可能再擴展任何區間，直接返回 false。

最優性與“局部最優 -> 全局最優”

我們在每一步都“盡可能把可達區間向右擴展”，這是天然的局部最優。
對于可達性問題，是否能到達終點僅依賴“區間最右端”。局部最優的持續累積，直接決定全局可達性，因此貪心是最優解。

四、反向貪心：等價但有啟發的視角

從右向左設定 lastGood = n-1，若 i + nums[i] >= lastGood，則從 i 出發可以到達 lastGood，因此把“必須到達”的點收縮為更靠左的 i。最后若 lastGood == 0，說明起點可達。這與正向貪心等價，但從“目標回溯”的角度更易讓人信服。

五、與動態規劃的對比與誤區澄清

DP 的狀態非常自然，但轉移需要枚舉可跳范圍，導致最壞 O(n2)。在 n=10^4 的上限下會超時或性能很差。
有同學會嘗試 BFS/最短路，但本題不問“最少步數”，只問“能否到達”，貪心一次掃描即可。
另一些做法會“實際模擬每一次跳躍”，容易漏掉“從更靠后的位置起跳能跳得更遠”的可能性；貪心用區間端點統一管理，避免了這種陷阱。

六、過程可視化（示例一）

以 nums = [2,3,1,1,4] 為例：

i	nums[i]	farthest(更新前)	能覆蓋的新右端	farthest(更新后)	結論
0	2	0	0+2=2	2	可達
1	3	2	1+3=4	4	可達，已>=4 返回true

在 i=1 時即可確定答案，早停是工程實現的重要優化點。

七、邊界與坑點匯總

n=1（單元素）：必定 true
出現長串 0：只要 0 左邊的某個位置能一次“跨越”它們即可；否則在 i > farthest 時返回 false
大數值：無需擔心溢出，i + nums[i] 在 int 范圍內，且只與數組長度比較
早停：一旦 farthest >= n-1，即可直接返回 true

八、復雜度與工程實踐

時間復雜度：O(n)。每個位置只訪問一次，且僅進行 O(1) 更新
空間復雜度：O(1)。只維護少量標量變量
工程建議：
- 使用早停減少不必要的循環
- 保持變量語義清晰（如 farthest、lastGood），利于代碼可讀性與維護

九、相關變體與延伸

Jump Game II（最少跳躍次數）：層次 BFS/貪心分層更新可解，注意與本題“可達性判斷”的區別
Jump Game III（含負數與圖可達性）：需要訪問標記避免重復，更多是圖搜索問題
帶代價/概率的跳躍：演化為最短路/期望優化等問題

十、常見面試追問（簡答）

為什么貪心正確？因為“能否到達”只與區間最右端相關，持續取最大右端的策略能完整保留一切潛在可達路徑的信息（循環不變式保證）。
為什么不用 DP？DP 的最壞時間 O(n2)，本題可用 O(n) 解法，工程上應優先選貪心。
有反例嗎？對于“只問可達性”的版本，貪心沒有反例；但若問“最少步數”，需要不同策略（分層貪心/ BFS）。

代碼實現

完整可運行代碼見 main.go，包含三種方法（貪心、反向貪心、DP）和測試/小型性能對比。

示例片段（貪心）：

func canJumpGreedy(nums []int) bool {farthest := 0for i := 0; i < len(nums); i++ {if i > farthest {return false}if i+nums[i] > farthest {farthest = i + nums[i]}if farthest >= len(nums)-1 {return true}}return true
}

測試用例設計

建議覆蓋：

基礎示例（題目給定）
被 0 阻斷導致不可達
單元素 0、全 1、首位一次大跳

小結

本質是“區間可達性”問題，維護“最遠可達端點”即可一次掃描判定
貪心與反向貪心等價，前者便于實現，后者便于論證
DP 直觀但性能差，保留為思路對比和單元測試的參照

完整題解代碼

package mainimport ("fmt""strings""time"
)// 解法一：貪心（最優解，時間O(n)，空間O(1)）
// 維護最遠可達下標 farthest，可以在遍歷過程中動態擴展可達范圍。
// 若某一時刻 i > farthest，說明當前位置不可達，直接返回 false。
// 最終只要 farthest >= n-1 即可到達終點。
func canJumpGreedy(nums []int) bool {farthest := 0for i := 0; i < len(nums); i++ {if i > farthest {return false}if i+nums[i] > farthest {farthest = i + nums[i]}if farthest >= len(nums)-1 {return true}}return true
}// 解法二：動態規劃（從后往前，時間O(n^2)，空間O(n)）
// dp[i] 表示從 i 出發是否能到達終點。枚舉 i 能跳到的每個 j，看是否有 dp[j] 為真。
// 僅用于教學對比，實際大數據會超時；可加剪枝或二分優化思路，但貪心更優雅。
func canJumpDP(nums []int) bool {n := len(nums)dp := make([]bool, n)dp[n-1] = truefor i := n - 2; i >= 0; i-- {maxJ := min(i+nums[i], n-1)for j := i + 1; j <= maxJ; j++ {if dp[j] {dp[i] = truebreak}}}return dp[0]
}// 解法三：反向貪心（從右往左收縮目標，時間O(n)，空間O(1)）
// 維護一個 lastGood 作為“必須到達”的最右位置；如果 i + nums[i] >= lastGood，
// 則把 lastGood 更新為 i。最終判斷 lastGood == 0。
func canJumpReverseGreedy(nums []int) bool {lastGood := len(nums) - 1for i := len(nums) - 2; i >= 0; i-- {if i+nums[i] >= lastGood {lastGood = i}}return lastGood == 0
}// 測試與簡單性能對比
func runTests() {type testCase struct {nums     []intexpected booldesc     string}tests := []testCase{{[]int{2, 3, 1, 1, 4}, true, "示例1 可達"},{[]int{3, 2, 1, 0, 4}, false, "示例2 不可達"},{[]int{0}, true, "單元素 0"},{[]int{1, 0, 1, 0}, false, "被 0 阻斷"},{[]int{2, 0, 0}, true, "邊界跳過"},{[]int{1, 1, 1, 1}, true, "全 1"},{[]int{4, 0, 0, 0, 0}, true, "首位大跳"},}fmt.Println("=== 55. 跳躍游戲 - 測試 ===")for i, tc := range tests {g := canJumpGreedy(tc.nums)r := canJumpReverseGreedy(tc.nums)d := canJumpDP(tc.nums)ok := (g == tc.expected) && (r == tc.expected) && (d == tc.expected)status := "?"if !ok {status = "?"}fmt.Printf("用例 %d: %s\n", i+1, tc.desc)fmt.Printf("輸入: %v\n期望: %v\n貪心: %v, 反向貪心: %v, DP: %v\n", tc.nums, tc.expected, g, r, d)fmt.Printf("結果: %s\n", status)fmt.Println(strings.Repeat("-", 40))}
}func benchmark() {fmt.Println("\n=== 簡單性能對比（粗略） ===")// 構造較大用例：長度 100000，前面給出足夠跳力n := 100000nums := make([]int, n)for i := 0; i < n-1; i++ {nums[i] = 2}nums[n-1] = 0start := time.Now()_ = canJumpGreedy(nums)d1 := time.Since(start)start = time.Now()_ = canJumpReverseGreedy(nums)d2 := time.Since(start)// 警告：O(n^2) DP 在大輸入上會非常慢，這里僅做一次小規模對比small := []int{2, 3, 1, 1, 4, 0, 0, 3, 1, 2, 0}start = time.Now()_ = canJumpDP(small)d3 := time.Since(start)fmt.Printf("貪心: %v\n", d1)fmt.Printf("反向貪心: %v\n", d2)fmt.Printf("DP(小規模): %v\n", d3)
}func min(a, b int) int {if a < b {return a}return b
}func main() {fmt.Println("55. 跳躍游戲")fmt.Println(strings.Repeat("=", 40))runTests()benchmark()
}