使用 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。此过程持续进行，直到我们以最少的跳跃次数到达终点。