原文題目

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

題目摘要

1. 問題描述：給定一個整數陣列 nums，其中每個元素代表你從該位置最多可以跳的步數。起始位置是陣列的第一個位置，目標是判斷能否跳到陣列的最後一個位置。
2. 輸入：一個整數陣列 nums，每個元素 nums[i] 表示在位置 i 可以跳的最大距離。
3. 輸出：回傳 true 或 false，true 表示可以跳到最後一個位置，false 表示無法到達。

Example 1:

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [2,3,0,1,4]
Output: 2

解題思路

1. 追蹤當前跳躍範圍和最遠可達位置：

   使用變數 currentEnd 來追蹤當前跳躍能到達的最遠範圍，並使用 farthest 來記錄可以達到的最遠位置。每次當遍歷到當前範圍的結束點時，必須進行一次跳躍，並將下一次跳躍的範圍更新為 farthest。如果 farthest 超過了或達到數組的最後一個位置，則表示可以完成跳躍。

2. 逐一檢查每個位置並更新最遠可達範圍：

   • 從陣列的第 0 個位置開始遍歷，直到倒數第二個位置。
   • 在每個位置 i，更新 farthest 為 i + nums[i] 和當前 farthest 中的較大值，這代表從位置 i 能夠跳到的最遠距離。
   • 如果遍歷的索引 i 到達 currentEnd，表示必須跳躍一次，增加跳躍次數，並將 currentEnd 更新為 farthest，代表下一次跳躍的範圍。

3. 回傳結果：

   • 當遍歷過程中，若 farthest 能夠到達或超過最後一個位置，則直接結束迴圈，並回傳最終的最少跳躍次數 jumps。

程式碼

public class Solution {
    public int jump(int[] nums) {
        //如果陣列的長度為1，表示已經在最後一個位置，不需要跳躍，因此直接回傳0
        if (nums.length == 1) {
            return 0;
        }
        int jumps = 0; //記錄跳躍的次數
        int currentEnd = 0; //表示目前這次跳躍的最遠範圍
        int farthest = 0; //記錄從當前位置可以跳躍到的最遠位置
        //遍歷陣列的倒數第二個位置，因為到最後一個位置時不需要再跳躍
        for (int i = 0; i < nums.length - 1; i++) {
            //更新從當前位置能跳到的最遠位置
            farthest = Math.max(farthest, i + nums[i]);
            //如果當前索引達到目前這次跳躍的最遠範圍就增加一次跳躍，並將當前跳躍範圍更新為能跳到的最遠位置
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
                // 如果currentEnd已經可以到達或超過最後一個位置，則結束迴圈
                if (currentEnd >= nums.length - 1) {
                    break;
                }
            }
        }
        return jumps; //回傳最終跳躍次數
    }
}

結論： 在「Jump Game II」這題中，我們的挑戰從單純的「能不能跳到終點」升級為「用最少的跳躍次數到達終點」。就像是生活中的旅程，我們不僅要到達目的地，還得考慮如何最有效率地完成。這裡的每個步驟都代表我們的決策點，你可以想像在旅行中選擇最佳的交通工具，以最快的方式到達終點。相比於「Jump Game」，只需確認能否抵達，這題要求我們更精確地規劃「跳躍」次數。我們用貪婪策略，每次選擇當前能跳到的最遠距離，並在需要時更新跳躍次數，最終以最少的步驟到達目標。這反映了生活中的規劃與優化過程——不只是到達，還要盡量節省時間和資源。