Как объединить два отсортированных списка на Python: задача LeetCode.
HTML-код
- Опубликовано: 17 май 2023
- Альбина раскрывает секреты решения задачи, которую она дает на собеседованиях. Суть задачи заключается в том, что нужно объединить два отсортированных списка. На удивление, не все справляются с этим заданием.
Ссылка на задачу: leetcode.com/problems/merge-t...
GitHub репозиторий github.com/valeryvpetrov-dev/AK
Актуальные вакансии: career.technokratos.com/
Telegram: t.me/technokratos
ВКонтакте: technokratos
#LeetCode #python #АлгоритмическаяКачалка #Программирование #Алгоритмы
Ничего не понял, но очень интересно
Чем будет отличаться результат при слиянии списков и сортировке?
Привет, у меня такой вопрос, коммерческого опыта нет, знаю C, Python, люблю Computer Science. Хочу в backend, выбираю между Java, C#, Golang что посоветуешь, и почему? интересно твое мнение.
Если ты еще не пошел в дворники, то выбор очень прост. Посмотри и проанализируй рынок
А разве не нужно делать проверку на то что и последующие элементы второго списка не больше(не меньше) чем текущее значения первого списка? Прим.:
1, 2, 4
1, 7, 9.
Ведь при то реализации, что показана на видео не будет сортировки, и запишется 1, 2 ,7, 4, 9?
Не досмотрел ещё видос, но по-сути нормальный алгоритм должен двигать курсор дальше и опять проверять меньше ли первый элемент чем второй
Было бы интересно посмотреть на то, как можно улучшить алгоритм, не обязательно даже самому думать, просто посмотреть решения, и объяснить почему это так работает. А то уже в двух роликах вы рассматриваете не самые эффективные алгоритмы.
Это учебные алгоритмы для совсем зеленых.
Если интересно посмотреть что-то посложнее, то поищите в интернете алгоритм timsort например.
@@user-lr6kg3ej6k кста, именно timsort работает под капотом у sorted() в Python
Что за собесы где можно обычные питонячьи списки?
Мы и сами в шоке, как так получается. Обычно в качестве ответа мы видим вот это:
return sorted(list1 + list2)
🤷♂️🤷♂️
ну наверно если ты проходишь собеседование на позицию питониста, то задачки будешь решать на питоне и пользоваться структурами и алгоритмами которые тебе предоставил язык?
@@hey-rg9lk
Никто щас на собесах не спрашивает за списки и даже за deque , потому, что подразумевается что кандидат уже освоил это всё. Спрашивают односвязный список, бинарные деревья, графы и тому подобные вещи. Если приходится использовать встроенные списки, то задача про что-то более сложное (матрица, треугольник паскаля) и подразумевает что ты умеешь работать со списками на уровне сортировки значений.
@@technokratosTV может меня на собес позовёте? ;) я правда только 4 месяца учусь и не освоил такие вещи как докер, рэббит и т.п., но в базовые алгоритмы типа сортировки слиянием и пузырьком, просчёта бинарных деревьев умею :)
@@plathardstuck28 в том то и дело что linked list кроме как алгоритмических задач нигде не будет использоваться в боевых решениях) а если обходить те же деревья или графы, мы снова приходим к тому что нужно использовать очереди
код проще если начальный result - сделать пустым элементом (any,None) тогда при выводе выдаем result.Next
а вообще через условные выражение решается в одну строку:
return list1 if not list2 else list2 if not list1 else ListNode(list1.val,self.mergeTwoLists(list1.next,list2)) if list1.val
Это решается намного проще
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
head = ListNode()
current = head
while list1 and list2:
if list1.val < list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
current.next = list1 or list2
return head.next
так же решил, только при проверке на наличие элементов в списке после цикла, использовал тернарник.