Connect with us

GitHub

Задачи с собеседований: размен

Фото аватара

Опубликовано

/

     
     

Проблема размена часто встречается в интервью Facebook и Amazon. Вам даются номиналы монет и желаемую сумму денег. Исходя из этого, вам нужно написать функцию для вычисления наименьшего количества монет, которое вам нужно, чтобы собрать эту сумму. Если вы не можете получить указанную сумму денег ни с одной комбинацией монет, вы возвращаете -1.

Вот три способа решить эту проблему:

Давайте посмотрим на решение, использующее восходящее динамическое программирование с табуляризацией на C++:

Для каждой итерации внутреннего цикла мы получаем решение с denoms[j] и сохраняем его в x. Мы также получаем решение без denoms[j] и сохраняем его в y. Таким образом мы можем ссылаться на более ранние решения, чтобы избежать дублирования вычислений.

Для каждой монеты номинала может быть только две возможности: включить ее или исключить. Мы знаем, что если монета denom[j] больше, чем amount, то x устанавливается в 0, так как включение ее в рассмотрение невозможно.

Временная сложность равна *O (amount * denomsLength), что является количеством итераций цикла for.

Примечание. Каждый из этих трех методов оценивается через временную сложность, а это означает, что временная сложность является важным понятием, которое необходимо понимать, чтобы добиться успеха в проблеме обмена монет.

← Еще задачи с собеседований

Если вы нашли опечатку - выделите ее и нажмите Ctrl + Enter! Для связи с нами вы можете использовать info@apptractor.ru.
Advertisement

Наши партнеры:

LEGALBET

Мобильные приложения для ставок на спорт
Telegram

Популярное

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: