. Limonadenwechsel

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
• Erklärung:
  • Von den ersten 3 Kunden sammeln wir der Reihe nach drei 5-Dollar-Scheine ein.
  • Ab dem vierten Kunden kassieren wir einen 10-Dollar-Schein 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
• Erklärung:
  • Von den ersten beiden Kunden in der Reihenfolge sammeln wir zwei 5-Dollar-Scheine.
  • Für die nächsten beiden Kunden in der Reihenfolge kassieren wir einen 10-Dollar-Schein 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 auf der Grundlage der von ihnen zum Bezahlen verwendeten Rechnungen simulieren. 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 der Optionen verfügbar ist, geben Sie false zurück.

3. Abschlussprüfung: Wenn wir alle Kunden erfolgreich bearbeitet haben, ohne dass 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 herauszugeben, 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 können. Die Lösung läuft in O(n)-Zeitkomplexität und ist daher für dieses Problem optimal.

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

Das obige ist der detaillierte Inhalt von. Limonadenwechsel. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!