Сложность: easy
На лимонадной стойке каждый лимонад стоит $5. Покупатели стоят в очереди, чтобы купить лимонад, и заказывают по одному (в порядке, указанном в массиве bills). Каждый покупатель покупает только один лимонад и платит либо $5, $10, либо $20. Вы должны предоставить правильную сдачу каждому покупателю, чтобы чистая сделка была такой, что покупатель платит $5.
Обратите внимание, что изначально у вас нет никакой сдачи.
Дан целочисленный массив bills, где bills[i] — купюра, которой платит i-й покупатель. Верните true, если вы можете предоставить каждому покупателю правильную сдачу, или false в противном случае.
Пример:
Input: bills = [5,5,5,10,20]
Output: true
Explanation:
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.
👨💻 Алгоритм:
1⃣Инициализируем переменные для хранения количества пятерок и десяток. Если покупатель платит $5, добавляем эту купюру в наш запас.
2⃣Если покупатель платит $10, проверяем наличие пятерки для сдачи. Если пятерки нет, возвращаем false. В противном случае, уменьшаем количество пятерок и увеличиваем количество десяток.
3⃣Если покупатель платит $20, сначала пытаемся дать сдачу десяткой и пятеркой. Если это невозможно, проверяем наличие трех пятерок. Если не можем дать сдачу, возвращаем false. После обработки всех покупателей, возвращаем true.
😎 Решение:
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
five = ten = 0
for bill in bills:
if bill == 5:
five += 1
elif bill == 10:
if five == 0: return False
five -= 1
ten += 1
else:
if five > 0 and ten > 0:
five -= 1
ten -= 1
elif five >= 3:
five -= 3
else:
return False
return True
Ставь 👍 и забирай 📚 Базу знаний