使用 Java 達到終點的最小跳躍次數

---

在本文中，我們將學習如何使用 Java 解決“達到終點的最小跳躍次數”問題。讓我們一步一步地分解它。其思路是找到從陣列開頭到結尾所需的最小跳躍次數。陣列中的每個元素表示您可以從該位置向前跳躍的最大步數。

問題陳述

給定一個數組 arr[]，其中每個元素表示您可以從該位置向前移動的最大步數，目標是從陣列的開頭開始，並以儘可能少的跳躍次數到達末尾。如果無法到達末尾，則返回 -1。

輸入

For an array arr = [2, 3, 1, 1, 2, 4, 2, 0, 1, 1]

輸出

Minimum jumps required: 4

在索引 0 處，arr[0] = 2，表示您可以跳到索引 1 或 2。
在索引 1 處，arr[1] = 3，因此從這裡，您可以跳到索引 2、3 或 4。
任務是計算到達最後一個索引所需的最小跳躍次數。

找到到達終點的最小跳躍次數的步驟

以下是使用 Java 找到到達終點的最小跳躍次數的步驟：

• 初始化 jumps 來計數跳躍次數，maxReach 來跟蹤我們可以到達的最遠索引，以及 steps 來計數當前跳躍範圍內的剩餘步數。
  
• 遍歷陣列：對於每個元素，使用可達到的最遠索引更新 maxReach，並在我們前進時遞減 steps。
  
• 如果 steps 達到零，則增加 jumps（表示需要跳躍以進一步移動）並根據新的最大可達索引重置 steps。
• 對於最終條件，如果當前位置加上 maxReach 足以到達末尾，則返回跳躍計數。如果我們耗盡 steps 或無法進一步移動，則 返回 -1。

Java 程式查詢最小跳躍次數

以下是使用 Java 進行最小跳躍次數演示的示例：

public class MinJumpsToEnd {
	public static int minJumps(int[] arr) {
		int n = arr.length;
		if (n <= 1) return 0;// Already at the end
		if (arr[0] == 0) return -1;// Cannot move anywhere
		int maxReach = arr[0]; // Farthest we can reach with initial jump
		int steps = arr[0]; // Steps we can still take in the current range
		int jumps = 1;// Start with the first jump
		for (int i = 1; i < n; i++) {
			if (i == n - 1) return jumps; // Reached end
			maxReach = Math.max(maxReach, i + arr[i]);
			steps--;
			if (steps == 0) {
				jumps++; // Need to jump again to keep moving
				if (i >= maxReach) return -1;// Cannot reach further
				steps = maxReach - i;// New steps to move further
			}
		}
		return -1;
	}
	public static void main(String[] args) {
		int[] arr = {2, 3, 1, 1, 2, 4, 2, 0, 1, 1};
		System.out.println("Minimum jumps required: " + minJumps(arr));
	}
}

輸出

Minimum jumps required: 4

時間複雜度：O(n)
空間複雜度：O(1)
這種方法確保我們使用最少的跳躍次數到達終點。

程式碼解釋

此 Java 程式透過更新 maxReach、steps 和 jumps 來計算到達陣列末尾所需的最小跳躍次數。從索引 0 開始，maxReach 由 arr[0] 設定，我們向前移動，減少每個元素的 steps。如果 steps 達到零，我們增加 jumps 並將 steps 重置為 maxReach - i 以開始下一次跳躍。
例如，從索引 0 開始，有 2 步，我們跳到索引 1 並將 maxReach 更新為 4。在索引 1 處，我們有 3 步，允許我們到達索引 4。此過程持續進行，直到我們以最少的跳躍次數到達終點。