860. Смена лимонада

Сложность: Легко

Темы: Массив, Жадный

В киоске с лимонадом каждый лимонад стоит 5 долларов. Клиенты стоят в очереди, чтобы купить у вас и сделать заказ по одному (в порядке, указанном в счетах). Каждый покупатель купит только один лимонад и заплатит купюрой в 5, 10 или 20 долларов. Вы должны предоставить правильное изменение каждому клиенту, чтобы чистая транзакция заключалась в том, что клиент заплатил 5 долларов США.

Обратите внимание, что сначала у вас нет сдачи в наличии.

При наличии целочисленного массива bills, где bills[i] — это счет, который платит i^-й клиент, верните true, если вы можете предоставить каждому клиенту правильную сдачу, или false в противном случае .

Пример 1:

• Ввод: счета = [5,5,5,10,20]
• Вывод: true
• Объяснение:
  • От первых 3 клиентов мы забираем три купюры по 5 долларов по порядку.
  • От четвертого покупателя мы получаем счет на 10 долларов и возвращаем 5 долларов.
  • От пятого покупателя мы дарим купюру на 10 долларов и купюру на 5 долларов.
  • Поскольку все клиенты получили корректные изменения, мы выводим true.

Пример 2:

• Ввод: счета = [5,5,10,10,20]
• Вывод: false
• Объяснение:
  • С первых двух клиентов мы получаем две купюры по 5 долларов.
  • Для следующих двух клиентов мы получаем купюру на 10 долларов и возвращаем купюру на 5 долларов.
  • Последнему клиенту мы не можем вернуть сдачу в размере 15 долларов США, поскольку у нас есть только две купюры по 10 долларов США.
  • Поскольку не каждый клиент получил правильные изменения, ответ неверный.

Ограничения:

• 5
• купюры[i] — 5, 10 или 20.

Решение:

Нам нужно смоделировать процесс предоставления сдачи клиентам на основе счетов, которые они используют для оплаты. Главное — отслеживать количество имеющихся у вас купюр номиналом 5 и 10 долларов, поскольку они необходимы для сдачи более крупных купюр

Давайте реализуем это решение на PHP: 860. Смена лимонада

Объяснение:

1. Инициализация: мы начинаем с $five и $10, установленных на 0, что соответствует количеству имеющихся у нас купюр по 5 и 10 долларов.

2. Обработка каждого счета:

   • Если клиент платит купюрой на 5 долларов: мы просто увеличиваем количество купюр на 5 долларов.
   • Если клиент платит 10-долларовой купюрой: Нам нужно вернуть одну 5-долларовую купюру в качестве сдачи, поэтому мы уменьшаем количество 5-долларовых купюр и увеличиваем количество 10-долларовых купюр. Если у нас нет купюр по 5 долларов, верните false.
   • Если клиент платит счетом на 20 долларов: мы приоритетно выдаем в качестве сдачи одну купюру на 10 долларов и одну купюру на 5 долларов. Если это невозможно, мы стараемся подарить три купюры по 5 долларов. Если ни один из вариантов недоступен, верните false.

3. Финальная проверка: если мы успешно обработали всех клиентов, не закончив сдачу, верните true.

Краевые случаи:

• Функция должна обрабатывать сценарии, в которых невозможно дать правильную сдачу, например, когда вы получаете счет на 10 или 20 долларов слишком рано, не имея под рукой необходимых купюр на 5 долларов.
• Из-за ограничений (до 100 000 клиентов) он должен эффективно обрабатывать входные данные большого размера. Решение работает за время O(n), что делает его оптимальным для этой задачи.

Контактные ссылки

Если эта серия оказалась для вас полезной, поставьте репозиторию звездочку на GitHub или поделитесь публикацией в своих любимых социальных сетях?. Ваша поддержка очень много значит для меня!

Если вы хотите больше такого полезного контента, подписывайтесь на меня:

• LinkedIn
• GitHub