Mindestanzahl von Sprüngen, um mit Java das Ende zu erreichen

Dieser Java -Code berechnet die minimalen Sprünge, die zum Überqueren eines Arrays erforderlich sind, wobei jedes Element den maximalen Sprungabstand von dieser Position darstellt. Lassen Sie uns Schritt für Schritt den Algorithmus und den Code untersuchen. Das Ziel ist es, die wenigsten Sprünge zu finden, die erforderlich sind, um das Ende des Arrays zu erreichen, beginnend mit Index 0. Wenn das Ende nicht erreichbar ist, gibt die Funktion -1

zurück.

Problemdefinition:

arr[] Bei einem Array arr[i] gegeben, wobei jedes Element

die maximale Anzahl von Schritten angibt, die Sie aus dieser Position ausführen können, bestimmen Sie die minimale Anzahl von Sprüngen, um den letzten Index zu erreichen.

Algorithmus:

maxReach Der Algorithmus verwendet einen gierigen Ansatz, der in jedem Schritt durch das Array iteriert und den am weitesten erreichbaren Index (jumps) verfolgt. Es behält einen Zähler und steps bei, um den Fortschritt in jedem Sprung zu verfolgen.

1. Initialisierung:

   • jumps: zählt die Gesamtzahl der Sprünge. Initialisiert auf 0.
   • maxReach: Der am weitesten erreichbare Index aus der aktuellen Position. Initialisiert zu arr[0].
   • steps: Die Anzahl der im aktuellen Sprung verbleibenden Schritte. Initialisiert zu arr[0].

2. Iteration:

   • Der Code iteriert das Array.
   • für jedes Element arr[i]:
     • update maxReach bis zum Maximum von maxReach und i arr[i] (dem am weitesten erreichbaren Index aus der aktuellen Position).
     .
     • steps Abnahme
     (Wir haben einen Schritt gemacht).
     • steps Wenn
       0 wird, bedeutet dies, dass wir die Schritte des aktuellen Sprung erschöpft haben. Deshalb:
       • jumps Inkrement
       .
       • maxReach Wenn i kleiner oder gleich
       ist, bedeutet dies, dass wir festsitzen und nicht weiter erreichen können. Return -1.
       • steps auf maxReach - i zurücksetzen (die verbleibenden Schritte im nächsten Sprung).

3. terminierung:

   • Wenn die Schleife ohne Rückkehr -1 abgeschlossen ist, bedeutet dies, dass das Ende erreichbar ist. Die Funktion gibt jumps.
   zurück

Java -Code:

public class MinJumpsToEnd {
    public static int minJumps(int[] arr) {
        int n = arr.length;
        if (n <= 1) return 0; // Already at the end or empty array

        int jumps = 0;
        int maxReach = arr[0];
        int steps = arr[0];

        for (int i = 1; i < n; i++) {
            maxReach = Math.max(maxReach, i + arr[i]); // Update maxReach
            steps--; // Decrement steps

            if (steps == 0) { // Jump needed
                jumps++;
                if (maxReach <= i) return -1; // Unreachable
                steps = maxReach - i; // Reset steps for next jump
            }
            if (i == n-1) return jumps; // Reached the end

        }
        return jumps;
    }

    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)); // Output: 4
    }
}

Zeit- und Raumkomplexität:

• Zeitkomplexität: o (n), wobei n die Länge des Arrays ist. Der Code iteriert das Array einmal.
• Raumkomplexität: o (1), da der Algorithmus eine konstante Menge zusätzlicher Speicherplatz verwendet.

Diese verbesserte Erklärung und Code liefern ein klareres Verständnis des Algorithmus und seiner Implementierung. Die hinzugefügten Kommentare verbessern die Lesbarkeit und das Rand-Fallhandling (leeres oder einzelnes Elementarray) macht den Code robuster.

Das obige ist der detaillierte Inhalt vonMindestanzahl von Sprüngen, um mit Java das Ende zu erreichen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!