День 44 — Минимальная стоимость соединения веревок

100 дней до Амазонки

100 дней до Amazon — 44-й день — минимальная стоимость подключения

Закончились бесплатные истории? Вот моя Ссылка на друзья.

Введение🛹

Привет, ребята! Сегодня 44-й день испытания, которое я принял. При этом я буду каждый день в течение 100 дней решать вопросы по программированию, которые были заданы в предыдущих интервью.

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

Все эти задачи взяты из следующей электронной книги. 🎓

Это совершенно бесплатно 🆓, если у вас есть подписка Amazon Kindle.

Эта электронная книга содержит 100 задач кодирования, которые были заданы в вопросах для интервью с ведущими специалистами. В нем также есть руководство по решению всех проблем более чем 200 способами. Эти проблемы, уверяю вас, уже задавали в предыдущих интервью.

Вы должны решить, хотите ли вы пойти неподготовленным на техинтервью или продолжить быстрый поиск этого руководства, чтобы решить 100 проблем.

Начни свое восхождение к величию🚀

Примечание. эта электронная книга содержит только ссылки на решения.

День 44 — Минимальная стоимость соединения веревок🏁

ЦЕЛЬ🏹

Имея n веревок разной длины, нам нужно соединить эти веревки в одну веревку. Мы можем соединить только 2 веревки одновременно.

Стоимость соединения двух веревок равна сумме их длин.

Длина этой соединенной веревки также равна сумме их длин. Этот процесс повторяется до тех пор, пока n веревки не будут соединены в одну веревку.

Найдите минимальную возможную стоимость соединения всех веревок.

Пример🕶

Input: ropes = [8, 4, 6, 12]
Output: 58
Explanation: The optimal way to connect ropes is as follows
1. Connect the ropes of length 4 and 6 (cost is 10). Ropes after connecting: [8, 10, 12]
2. Connect the ropes of length 8 and 10 (cost is 18). Ropes after connecting: [18, 12]
3. Connect the ropes of length 18 and 12 (cost is 30).
Total cost to connect the ropes is 10 + 18 + 30 = 58

Код👇

Алгоритм👨‍🎓

1. Создайте очередь с приоритетом. В очереди с приоритетом любой элемент массива будет храниться в отсортированном порядке.
2. Повторить данный список и добавить их в приоритетную очередь.
3. Пока размер очереди не уменьшится до одного запуска цикла.
4. Каждая итерация опрашивает (удаляет) первые два элемента очереди, добавляет их и снова добавляет в очередь.
5. При добавлении этих двух элементов также добавьте их в значение результата.
6. Вернуть значение результата.🔚

Заключение🐱‍🏍

Приходилось ли вам раньше задавать этот вопрос в ходе интервью? Поделитесь им в разделе комментариев ниже. 🤝

Не забудьте нажать кнопку подписаться✅, чтобы получать обновления, когда мы публикуем новые задачи по программированию. Расскажите нам, как вы решили эту проблему. 🔥 Мы будем рады их прочитать. ❤ Мы можем рассказать о вашем методе в одном из постов блога.

Хотите стать выдающимся в программировании Java?

Нажмите ЗДЕСЬ 🧨🎊🎃

Я опубликовал электронную книгу. Подборка 100 задач программирования на Java (интервью), которые были решены.(HackerRank) 🐱‍💻

Это совершенно бесплатно 🆓, если у вас есть подписка Amazon Kindle.

Компании

1. Google 2) Pocket Gems 3) Capital One 4) Amazon

Предыдущие записи в блоге