134. La station-service

Vous disposez de n stations-service sur un circuit circulaire. À la station i, le réservoir peut recevoir gas[i] litres de carburant, et le coût pour se rendre de la station i à la station i+1 est de cost[i] litres. Vous commencez avec un réservoir vide au départ d'une des stations. L'objectif est de trouver l'index de la station de départ à partir de laquelle vous pouvez faire un tour complet du circuit, ou de retourner -1 si c'est impossible.

Approche Gloutonne

Ce problème peut être résolu efficacement en utilisant une approche gloutonne. Nous commençons par calculer la différence nette de carburant (gas[i] - cost[i]) pour chaque segment du trajet. Si la somme totale de ces différences sur l'ensemble du circuit est négative, il est impossible de terminer le tour, car la quantité totale de carburant disponible est inférieure à la quantité totale nécessaire. Dans ce cas, nous retournons -1.

Si la somme totale est non négative, une solution existe. Nous parcourons les stations, en maintenant une somme_courante de carburant. Si à tout moment cette somme_courante devient négative, cela signifie que le point de départ actuel ne nous permet pas d'atteindre la station actuelle. Nous devons alors choisir la station suivante comme nouveau point de départ, et réinitialiser notre somme_courante à zéro. Le dernier point de départ enregistré avant la fin du parcours sera la solution valide.

class Solution {
public:
    int canCompleteCircuit(std::vector<int>& gas, std::vector<int>& cost) {
        int carburantActuel = 0; // Carburant accumulé depuis le dernier point de départ potentiel
        int carburantTotal = 0;  // Somme totale des différences de carburant pour tout le circuit
        int indexDepart = 0;     // Point de départ potentiel

        for (int i = 0; i < gas.size(); ++i) {
            int differenceCarburant = gas[i] - cost[i];
            carburantActuel += differenceCarburant;
            carburantTotal += differenceCarburant;

            // Si le carburant actuel devient négatif, le point de départ actuel n'est pas viable.
            // Nous devons commencer à la station suivante.
            if (carburantActuel < 0) {
                indexDepart = i + 1;
                carburantActuel = 0; // Réinitialiser le compteur de carburant pour le nouveau départ
            }
        }

        // Si le carburant total est négatif, il est impossible de faire le tour.
        if (carburantTotal < 0) {
            return -1;
        }
        // Sinon, le dernier index de départ enregistré est la solution.
        return indexDepart;
    }
};
</int></int>

135. Distribuer des bonbons

Vous avez n enfants alignés, et chacun a une note (rating). Vous devez leur distribuer des bonbons en respectant les règles suivantes :

1. Chaque enfant doit avoir au moins un bonbon.
2. Les enfants avec une note plus élevée que leurs voisins doivent recevoir plus de bonbons que leurs voisins.

Votre tâche est de calculer le nombre minimum total de bonbons nécessaires.

Stratégie à Double Parcours

Ce problème est un excellent exemple de l'application d'une stratégie gloutonne en deux passes pour satisfaire des conditions bidirectionnelles. Nous initialisons d'abord chaque enfant avec un bonbon.

1. Passage de gauche à droite : Nous parcourons les enfants du premier au dernier. Si l'enfant i a une note supérieure à l'enfant i-1 (son voisin de gauche), alors l'enfant i doit avoir plus de bonbons que i-1. Nous lui attribuons donc bonbons[i-1] + 1 bonbons. Ce passage garantit que la condiiton "plus de bonbons que le voisin de gauche si note supérieure" est satisfaite.
2. Passage de droite à gauche : Ensuite, nous parcourons les enfants du dernier au premier. Si l'enfant i a une note supérieure à l'enfant i+1 (son voisin de droite), il doit également avoir plus de bonbons que i+1. Cependant, l'enfant i a peut-être déjà reçu des bonbons lors du premier passage. Pour satisfaire les deux conditions (par rapport à gauche et par rapport à droite), nous prenons le maximum entre son nombre actuel de bonbons et bonbons[i+1] + 1.

Après ces deux passages, chaque enfant aura le nombre minimum de bonbons respectant les deux règles.

class Solution {
public:
    int candy(std::vector<int>& ratings) {
        int nombreEnfants = ratings.size();
        if (nombreEnfants == 0) return 0;

        std::vector<int> bonbons(nombreEnfants, 1); // Chaque enfant reçoit au moins 1 bonbon

        // Premier passage : de gauche à droite
        // S'assurer qu'un enfant avec une meilleure note que son voisin de gauche
        // reçoit plus de bonbons que ce voisin.
        for (int i = 1; i < nombreEnfants; ++i) {
            if (ratings[i] > ratings[i - 1]) {
                bonbons[i] = bonbons[i - 1] + 1;
            }
        }

        // Deuxième passage : de droite à gauche
        // S'assurer qu'un enfant avec une meilleure note que son voisin de droite
        // reçoit plus de bonbons que ce voisin. On prend le maximum pour ne pas régresser.
        for (int i = nombreEnfants - 2; i >= 0; --i) {
            if (ratings[i] > ratings[i + 1]) {
                bonbons[i] = std::max(bonbons[i], bonbons[i + 1] + 1);
            }
        }

        // Calculer la somme totale des bonbons distribués
        int totalBonbons = 0;
        for (int b : bonbons) {
            totalBonbons += b;
        }
        return totalBonbons;
    }
};
</int></int>

860. Monnaie pour la limonade

Vous tenez un stand de limonade et chaque limonade coûte 5 dollars. Les clients paient avec des billets de 5, 10 ou 20 dollars. Vous devez toujousr rendre la monnaie exacte. Votre objectif est de déterminer si vous pouvez rendre la monnaie à tous les clients dans l'ordre où ils se présentent.

Gestion des Billets de Monnaie

C'est un problème glouton où la clé est de toujours essayer de rendre la monnaie de la manière la plus "utile" pour le futur. Nous maintenons un compte du nombre de billets de 5 et 10 dollars que nous avons en caisse.

• Client paie avec 5 dollars : Nous prenons le billet, notre stock de billets de 5 dollars augmente.
• Client paie avec 10 dollars : Nous devons rendre 5 dollars. Si nous n'avons pas de billet de 5 dollars, c'est impossible (retourner false). Sinon, nous utilisons un billet de 5 dollars et notre stock de billets de 10 dollars augmente.
• Client paie avec 20 dollars : Nous devons rendre 15 dollars. La stratégie gloutonne ici est cruciale :
  • Nous préférons utiliser un billet de 10 dollars et un billet de 5 dollars pour rendre la monnaie, car les billets de 5 dollars sont plus polyvalents (ils peuvent être utilisés seuls pour rendre la monnaie sur 10 dollars, ou combinés pour rendre la monnaie sur 20 dollars). Si nous avons les deux, nous les utilisons.
  • Si nous n'avons pas de billet de 10 dollars, ou pas de billet de 5 dollars en plus, nous devons alors essayer d'utiliser trois billets de 5 dollars. Si nous en avons au moins trois, nous les utilisons.
  • Si aucune de ces options n'est possible, il est impossible de rendre la monnaie (retourner false).

Si nous parvenons à servir tous les clients, nous retournons true.

class Solution {
public:
    bool lemonadeChange(std::vector<int>& bills) {
        int billetsDeCinq = 0;  // Nombre de billets de 5 dollars en caisse
        int billetsDeDix = 0;   // Nombre de billets de 10 dollars en caisse

        for (int montantRecu : bills) {
            if (montantRecu == 5) {
                billetsDeCinq++;
            } else if (montantRecu == 10) {
                if (billetsDeCinq == 0) {
                    return false; // Impossible de rendre 5 dollars
                }
                billetsDeCinq--;
                billetsDeDix++;
            } else { // montantRecu == 20
                // Priorité : utiliser un billet de 10 et un de 5
                if (billetsDeDix > 0 && billetsDeCinq > 0) {
                    billetsDeDix--;
                    billetsDeCinq--;
                } else if (billetsDeCinq >= 3) {
                    // Alternative : utiliser trois billets de 5
                    billetsDeCinq -= 3;
                } else {
                    return false; // Impossible de rendre 15 dollars
                }
            }
        }
        return true; // Tous les clients ont pu être servis
    }
};
</int>

406. Reconstruire la file d'attente par taille

Vous avez une liste de personnes, chacune décrite par une paire (h, k) où h est la taille de la personne et k est le nombre de personnes ayant une taille supérieure ou égale à h qui se trouvent devant cette personne dans la file d'attente. Votre tâche est de reconstruire la file d'attente.

Tri et Insertion Intelligente

La clé de ce problème est de trier les personnes d'une manière qui simplifie l'insertion. La stratégie gloutonne est la suivante :

1. Tri des personnes : Triez les personnes par taille en ordre décroissant. Si deux personnes ont la même taille, triez-les par leur valeur k en ordre croissant.
2. Insertion dans la file : Une fois triées, parcourez la liste des personnes. Pour chaque personne (h, k), insérez-la à l'index k de votre file d'attente résultante.

Pourquoi cette stratégie fonctionne-t-elle ? Lorsque nous traitons les personnes de la plus grande à la plus petite, toute personne déjà placée dans la file d'attente est soit plus grande, soit de même taille que la personne que nous sommes sur le point d'insérer. Par conséquent, la valeur k de la personne actuelle indique précisément sa position finale dans la file d'attente par rapport aux personnes déjà placées (qui sont toutes "comptées" par k).

Implémentation avec std::vector

L'utilisation de std::vector est simple, mais l'opération insert est coûteuse (complexité temporelle en O(N) car elle nécessite de décaler les éléments). Pour un grand nombre de personnes, cela peut entraîner une complexité totale de O(N^2).

class Solution {
public:
    // Fonction de comparaison personnalisée pour le tri
    static bool comparerPersonnes(const std::vector<int>& p1, const std::vector<int>& p2) {
        // Trier par taille (h) en ordre décroissant
        if (p1[0] != p2[0]) {
            return p1[0] > p2[0];
        }
        // Si les tailles sont égales, trier par k en ordre croissant
        return p1[1] < p2[1];
    }

    std::vector<:vector>> reconstructQueue(std::vector<:vector>>& people) {
        // Trier les personnes selon la règle définie
        std::sort(people.begin(), people.end(), comparerPersonnes);

        std::vector<:vector>> fileReconstruite;
        // Insérer chaque personne à son index k spécifié
        for (const auto& personne : people) {
            int position = personne[1]; // L'index où insérer la personne
            // L'insertion dans un vecteur est coûteuse (décalage d'éléments)
            fileReconstruite.insert(fileReconstruite.begin() + position, personne);
        }

        return fileReconstruite;
    }
};
</:vector></:vector></:vector></int></int>

Optimisation avec une Liste Chaînée (std::list)

Pour des performances potentiellement meilleures, notamment si les insertions sont fréquemment au début ou au milieu et que les décalages d'éléments sont un goulot d'étranglement, une structure de données basée sur une liste chaînée comme std::list peut être utilisée. L'insertion dans une std::list est en O(1) si l'itérateur est déjà à la bonne position. Le déplacement de l'itérateur prend O(k) temps, résultant également en une complexité totale de O(N^2) dans le pire des cas (si k est toujours N/2), mais avec une meilleure constante et sans les coûts de réallocation de mémoire associés à std::vector.

class Solution {
public:
    // Fonction de comparaison personnalisée (identique à celle du vecteur)
    static bool comparerPersonnes(const std::vector<int>& p1, const std::vector<int>& p2) {
        if (p1[0] != p2[0]) {
            return p1[0] > p2[0];
        }
        return p1[1] < p2[1];
    }

    std::vector<:vector>> reconstructQueue(std::vector<:vector>>& people) {
        // Trier les personnes de la même manière
        std::sort(people.begin(), people.end(), comparerPersonnes);

        std::list<:vector>> fileTemp; // Utilisation de std::list pour des insertions efficaces

        // Insérer chaque personne dans la liste
        for (const auto& personne : people) {
            int position = personne[1];
            auto it = fileTemp.begin();
            // Déplacer l'itérateur à la position d'insertion
            std::advance(it, position);
            fileTemp.insert(it, personne);
        }

        // Convertir la liste en vecteur pour le résultat final
        return std::vector<:vector>>(fileTemp.begin(), fileTemp.end());
    }
};
</:vector></:vector></:vector></:vector></int></int>