Nombre minimum de sauts pour atteindre la fin à l'aide de Java

Ce code Java calcule les sauts minimaux nécessaires pour traverser un tableau, où chaque élément représente la distance de saut maximale de cette position. Explorons l'algorithme et le code étape par étape. L'objectif est de trouver le moins de sauts nécessaires pour atteindre la fin du tableau, à partir de l'indice 0. Si la fin est inaccessible, la fonction renvoie -1.

Définition du problème:

étant donné un tableau arr[], où chaque élément arr[i] indique le nombre maximum de mesures que vous pouvez faire de cette position, déterminer le nombre minimum de sauts pour atteindre le dernier index.

Algorithme:

L'algorithme utilise une approche gourmand, itérant à travers le tableau et suivant l'index le plus éloigné (maxReach) à chaque étape. Il maintient un compteur jumps et steps pour suivre les progrès dans chaque saut.

1. Initialisation:

   • jumps: compte le nombre total de sauts. Initialisé à 0.
   • maxReach: L'indice le plus éloigné accessible de la position actuelle. Initialisé à arr[0].
   • steps: Le nombre d'étapes restant dans le saut actuel. Initialisé à arr[0].

2. itération:

   • Le code itère dans le tableau.
   • pour chaque élément arr[i]:
     • Mise à jour maxReach au maximum de maxReach et i arr[i] (l'indice le plus éloigné de la position actuelle).
     • décrément steps (nous avons fait une étape).
     • Si steps devient 0, cela signifie que nous avons épuisé les étapes du saut actuel. Par conséquent:
       • Incrément jumps.
       • Si maxReach est inférieur ou égal à i, cela signifie que nous sommes coincés et ne pouvons pas atteindre plus loin. Retour -1.
       • réinitialiser steps à maxReach - i (les étapes restantes dans le saut suivant).

3. terminaison:

   • Si la boucle se termine sans retourner -1, cela signifie que la fin est accessible. La fonction renvoie jumps.

Code java:

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
    }
}

Complexité du temps et de l'espace:

• Complexité temporelle: o (n), où n est la longueur du tableau. Le code itère une fois dans le tableau.
• Complexité de l'espace: o (1), car l'algorithme utilise une quantité constante d'espace supplémentaire.

Cette explication et le code améliorés fournissent une compréhension plus claire de l'algorithme et de son implémentation. Les commentaires ajoutés améliorent la lisibilité et la manipulation des boîtiers de bord (tableau vide ou à élément unique) rend le code plus robuste.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!