860. Limonadenwechsel

Schwierigkeit: Einfach

Themen: Array, Greedy

An einem Limonadenstand kostet jede Limonade 5 $. Kunden stehen Schlange, um bei Ihnen einzukaufen und einzeln zu bestellen (in der auf den Rechnungen angegebenen Reihenfolge). Jeder Kunde kauft nur eine Limonade und bezahlt entweder mit einem 5-Dollar-, 10-Dollar- oder 20-Dollar-Schein. Sie müssen jedem Kunden das korrekte Wechselgeld zur Verfügung stellen, damit der Kunde bei der Nettotransaktion 5 $ zahlt.

Beachten Sie, dass Sie zunächst kein Wechselgeld zur Hand haben.

Angenommen ein ganzzahliges Array bills, wobei bills[i] die Rechnung ist, die der i

te ^{Kunde bezahlt, geben Sie} true zurück, wenn Sie jedem Kunden das richtige Wechselgeld geben können, andernfalls false .

Beispiel 1:

• Eingabe: Rechnungen = [5,5,5,10,20]
• Ausgabe: wahr
• Erläuterung:
  Von den ersten drei Kunden sammeln wir der Reihe nach drei 5-Dollar-Scheine ein.
  Ab dem vierten Kunden ziehen wir einen 10-Dollar-Schein ein und geben einen 5-Dollar-Schein zurück.
  Ab dem fünften Kunden geben wir einen 10-Dollar-Schein und einen 5-Dollar-Schein.
  Da alle Kunden das richtige Wechselgeld erhalten haben, geben wir true aus.

Beispiel 2:

• Eingabe: Rechnungen = [5,5,10,10,20]
• Ausgabe: false
• Erläuterung:
  Von den ersten beiden Kunden in der Reihenfolge sammeln wir zwei 5-Dollar-Scheine ein.
  Für die nächsten beiden Kunden in der Reihenfolge ziehen wir einen 10-Dollar-Schein ein und geben einen 5-Dollar-Schein zurück.
  Für den letzten Kunden können wir das Wechselgeld von 15 $ nicht zurückgeben, da wir nur zwei 10 $-Scheine haben.
  Da nicht jeder Kunde das richtige Wechselgeld erhalten hat, ist die Antwort falsch.

Einschränkungen:

5
bills[i] ist entweder 5, 10 oder 20.

Lösung:

Wir müssen den Prozess der Bereitstellung von Wechselgeld für Kunden basierend auf den Rechnungen simulieren, mit denen sie bezahlen. Der Schlüssel besteht darin, die Anzahl Ihrer 5-Dollar- und 10-Dollar-Scheine zu verfolgen, da diese benötigt werden, um Wechselgeld für größere Scheine bereitzustellen

Lassen Sie uns diese Lösung in PHP implementieren:

860. Limonadenwechsel

Erläuterung:

1. Initialisierung: Wir beginnen mit 5-Dollar- und 10-Dollar-Scheinen, die auf 0 gesetzt sind, was die Anzahl der 5-Dollar- und 10-Dollar-Scheine darstellt, die wir haben.

2. Bearbeitung jeder Rechnung:

   • Wenn der Kunde mit einem 5-Dollar-Schein bezahlt: Wir erhöhen einfach die Anzahl der 5-Dollar-Scheine.
   • Wenn der Kunde mit einem 10-Dollar-Schein bezahlt: Wir müssen einen 5-Dollar-Schein als Wechselgeld zurückgeben, also verringern wir die Anzahl der 5-Dollar-Scheine und erhöhen die Anzahl der 10-Dollar-Scheine. Wenn wir keine 5-Dollar-Scheine haben, geben Sie false zurück.
   • Wenn der Kunde mit einem 20-Dollar-Schein bezahlt: Wir geben vorrangig einen 10-Dollar-Schein und einen 5-Dollar-Schein als Wechselgeld heraus. Wenn das nicht möglich ist, versuchen wir, drei 5-Dollar-Scheine zu geben. Wenn keine Option verfügbar ist, geben Sie false zurück.

3. Abschlussprüfung: Wenn wir alle Kunden erfolgreich bearbeitet haben, ohne dass uns das Wechselgeld ausgeht, geben Sie „true“ zurück.

Randfälle:

Die Funktion sollte Situationen bewältigen, in denen es unmöglich ist, das richtige Rückgeld zu geben, z. B. wenn Sie einen 10-Dollar- oder 20-Dollar-Schein zu früh erhalten, ohne die erforderlichen 5-Dollar-Scheine zur Hand zu haben.
Es sollte aufgrund der Einschränkungen (bis zu 100.000 Kunden) große Eingabemengen effizient verarbeiten. Die Lösung läuft in O(n)-Zeitkomplexität und ist daher optimal für dieses Problem.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem

Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub