860. Changement de limonade

Difficulté : Facile

Sujets : Array, Greedy

Dans un stand de limonade, chaque limonade coûte 5 $. Les clients font la queue pour acheter chez vous et commander un par un (dans l'ordre spécifié par les factures). Chaque client n'achètera qu'une seule limonade et paiera avec un billet de 5 $, 10 $ ou 20 $. Vous devez fournir la monnaie correcte à chaque client afin que la transaction nette corresponde à ce que le client paie 5 $.

Notez que vous n'avez d'abord aucune monnaie en main.

Étant donné un tableau d'entiers bills où bills[i] est la facture payée par le i^ème client, renvoyez true si vous pouvez fournir à chaque client la monnaie correcte, ou false sinon .

Exemple 1 :

• Entrée : factures = [5,5,5,10,20]
• Sortie : vrai
• Explication:
  • Sur les 3 premiers clients, nous collectons trois billets de 5 $ dans l'ordre.
  • Du quatrième client, nous collectons une facture de 10 $ et lui rendons 5 $.
  • À partir du cinquième client, nous remettons une facture de 10 $ et une facture de 5 $.
  • Puisque tous les clients ont obtenu la bonne monnaie, nous produisons vrai.

Exemple 2 :

• Entrée : factures = [5,5,10,10,20]
• Sortie : faux
• Explication:
  • Dès les deux premiers clients commandés, nous encaissons deux billets de 5 $.
  • Pour les deux prochains clients en commande, nous collectons une facture de 10 $ et rendons une facture de 5 $.
  • Pour le dernier client, nous ne pouvons pas rendre la monnaie de 15$ car nous n'avons que deux billets de 10$.
  • Étant donné que tous les clients n'ont pas reçu la bonne monnaie, la réponse est fausse.

Contraintes :

• 5
• bills[i] vaut 5, 10 ou 20.

Solution:

Nous devons simuler le processus de fourniture de monnaie aux clients en fonction des factures qu'ils utilisent pour payer. La clé est de suivre le nombre de billets de 5 $ et de 10 $ que vous possédez, car ils sont nécessaires pour rendre la monnaie aux billets plus gros

Implémentons cette solution en PHP : 860. Changement de limonade

Explication:

1. Initialisation : Nous commençons avec cinq $ et dix $ définis sur 0, ce qui représente le nombre de billets de 5 $ et 10 $ dont nous disposons.

2. Traitement de chaque facture :

   • Si le client paie avec une facture de 5 $ : nous incrémentons simplement le nombre de factures de 5 $.
   • Si le client paie avec une facture de 10 $ : nous devons rendre une facture de 5 $ en guise de monnaie, nous décrémentons donc le nombre de billets de 5 $ et incrémentons le nombre de billets de 10 $. Si nous n'avons pas de billets de 5 $, renvoyez false.
   • Si le client paie avec une facture de 20 $ : Nous accordons la priorité à la remise d'une facture de 10 $ et d'une facture de 5 $ en guise de monnaie. Si ce n'est pas possible, nous essayons de donner trois billets de 5 $. Si aucune des deux options n'est disponible, renvoyez false.

3. Vérification finale : si nous avons traité avec succès tous les clients sans manquer de monnaie, renvoie true.

Cas extrêmes :

• La fonction doit gérer les scénarios dans lesquels il est impossible de rendre la monnaie correcte, par exemple lorsque vous recevez une facture de 10 $ ou de 20 $ trop tôt sans disposer des factures de 5 $ nécessaires.
• Il devrait gérer efficacement des entrées de grande taille en raison des contraintes (jusqu'à 100 000 clients). La solution s'exécute dans une complexité temporelle O(n), ce qui la rend optimale pour ce problème.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub