Добро пожаловать в третий выпуск нашей серии по технической подготовке к собеседованию, наша цель - помочь вам с легкостью получить работу своей мечты, предоставив вам реальные навыки решения проблем, охватывающие множество тем.
Готовый? Давайте прямо сейчас!
День 3: Лодки для спасения людей.
Я предполагаю, что вы не читали описание задачи, поэтому вот краткое изложение:
Имея массив w, где w [i] - вес i-го человека, у вас есть бесконечное количество лодок, каждая лодка имеет вместимость L и может вместить до двух человек.
какое минимальное количество лодок вам нужно, чтобы перевезти всех людей?
Хороший способ подойти к этой проблеме - разбить ее на более мелкие подзадачи, давайте сделаем это!
Взгляните на следующую немного более простую задачу:
Допустим, вы назначили какого-то человека на первую лодку, и еще есть место R, каков лучший выбор, который вы можете сделать в отношении этого дополнительного места.
Подсказка: представьте, что у вас есть только два неназначенных человека (разного веса), которые могут поместиться в этом дополнительном пространстве. Кого из них вы должны выбрать?
Очевидно, что если нам нужно разместить только одного человека и у нас есть пространство R, то всегда лучше выбрать самый большой, который может поместиться, самый простой способ рассуждать об этом заключается в следующем:
Выбирая человека самого крупного размера, который может поместиться в R, вы теряете меньше места, чем размещаете человека с меньшим весом.
Более строго, если вы не выберете самого крупного человека, который может поместиться (назовем его X), и не выберете другого человека с меньшим весом (назовем его Y), то вы сможете найти решение, которое, по крайней мере, так же хорошо, поменяв местами места X и Y.
Теперь вернемся к нашей исходной проблеме: теперь у нас есть стратегия выбора второго человека на каждой лодке, но как нам выбрать первого ?!
Это решение оказывается немного сложнее, но мы все еще можем применить ту же логику, но нам все еще нужно простое наблюдение.
Простое наблюдение: порядок, в котором мы распределяем людей по лодкам, не имеет значения, и в конце концов каждый будет на какой-то лодке.
Вы можете подумать, что это слишком очевидно и это наблюдение нам мало помогает, но давайте углубимся в это направление и получим более ценные наблюдения.
1- каждый человек будет назначен на лодку.
2 - это означает, что за какой-то лодкой закреплен самый тяжелый человек.
3. Каким-то образом самый тяжелый человек является самым требовательным и не дает нам слишком много вариантов, поэтому имеет смысл начать с его назначения.
Эта логика мышления называется жадным мышлением, которое гласит: если вам нужно принять решение, выберите вариант, который кажется наиболее удобным в данный момент, не беспокоясь о будущих решениях, я знаю, что это может быть не лучший жизненный урок, но он пригодится при решении алгоритмических задач;)
Вспомните, как мы начали с выбора самого тяжелого человека, и когда у нас есть лодка с одним человеком, мы назначаем другого, выбирая самый тяжелый, который может поместиться, мы как бы думаем о том, что лучше всего делать с этой лодкой, не задумываясь о другие лодки будущего, которые нам могут понадобиться.
Давайте подробно рассмотрим псевдокод:
answer = 0 sort the people by weights repeat until all people are assigned to boats :- 1-pick the heaviest person and assign it to some boat. 2-calculate the remaining space R on that boat. 3-if there is some people with weight <= R who are not assigned. 4-then pick the heaviest one of them and assign it to that boat. We have found a strategy for the task, let's write some code!
Моя реализация на C ++:
Как мы подошли к сегодняшней задаче и как подойти к другим задачам?
- Разбейте проблему на более мелкие подзадачи: этот метод очень полезен, поскольку более мелкие проблемы, как правило, имеют более простые, а иногда и хорошо известные решения.
- Подумайте, как эффективно решать более мелкие подзадачи и объединить их в одно окончательное счастливое решение.
- Измените постановку задачи и сделайте предположения, которые помогут вам лучше интерпретировать стоящую перед вами проблему: обратите внимание, что мы отсортировали исходный массив, чтобы запустить наш жадный алгоритм.
- Перечитывайте эту статью много раз, пока не оцените ее полностью, особенно если вы впервые видите жадный подход в действии.
Твоя очередь:
Поздравляю, если вы добрались сюда за один присест, я знал, что вы справитесь.
Теперь, когда вы, надеюсь, приобрели некоторые новые навыки, не останавливайтесь на достигнутом, вы должны применить их на практике.
Поиграйте с кодом и напишите его самостоятельно с нуля, и поставьте перед собой задачу придумать примеры проблем, которые можно было бы решить с помощью жадного подхода.
Дополнительные задачи для практики:
Минимум операций для увеличения массива
"Планировщик заданий"
Если у вас есть ко мне какие-либо вопросы, не стесняйтесь обращаться ко мне в LinkedIn и подписывайтесь на меня в Medium, чтобы увидеть больше интересных статей.
На сегодня все. Спасибо за прочтение!
