Всем привет! Мне стало скучно тупить одному, и я решил тупить публично! А чего мне стесняться? Правильно, нечего! А вот фиксировать ход своих собственных рассуждений при решении задач должно быть интересной практикой.
В первую очередь, задачи я буду брать с Leetcode. Пока с уровнем easy и medium. Конечно, буду пытаться решать и сложные задачи, но все постепенно, да и времени на все не хватает.
Прошу не забрасывать меня тапками, ну только если прям очень захочется, так как я буду начинать с наивных решений, а уже потом буду искать решения более оптимальные и публиковать их отдельно.
Как говорится, ни пуха ни пера!
![На сером фоне надпись: связные списки Python. Ниже приведен пример связного списка: [1]->[4]->[12]->None](https://touch-it.ru/wp-content/uploads/2023/11/photostudio_1700052571693-1024x1024.jpg)
Условия задачи:
Даны два связных списка, представляющих два неотрицательных целых числа. Цифры хранятся в обратном порядке.
Что нужно сделать?
Сложить два числа и вернуть сумму в виде связного списка.
Пример:
На вход получаем связные списки:
linked_list_one = [2, 4, 3] # это число 342
linked_list_two = [5, 6, 4] # это число 465
На выходе мы должны получить также связный список:
result = [7, 0, 8] # 342 + 465 = 807
Завершая описание условий задачи, приведу заготовку кода, которая представлена на Leetcode:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
pass
Рассуждения
В первую очередь, в задаче речь идет о такой структуре данных в Python, как связные списки (LinkedList). Предлагаю вспомнить, что из себя представляет данная структура данных.
Каждый элемент связного списка представляет собой узел, который содержит, кроме непосредственно самого значения, ссылку на предыдущий элемент и на следующий, в зависимости от вида связного списка.
Тут следует отметить, что в самом языке на базовом уровне такая структура данных, как связный список, отсутствует.
Связные списки в Python реализуются с помощью классов. Впрочем, давайте пока не будем углубляться в эту тему, ссылки на материалы по связным спискам я приведу в конце статьи.
А сейчас расскажу о проблемах, с которыми я столкнулся при решении данной задачи.
Проблема невнимательности чтения условий
Сначала я никак не мог понять, что все же приходит на вход в метод addTwoNumbers(). Меня смущали примеры входных данных, которые выглядят как стандартный питоновский список, но это, конечно же, оказалось не так.
В какой-то момент, когда, проверяя свое решение, я получал ошибку, связанную с типом данных, я понял, что с моим подходом что-то не так. Самым простым решением было с помощью функции print() посмотреть, так что же мы получаем на вход и с чем нужно работать.
ListNode{val: 2, next: ListNode{val: 4, next: ListNode{val: 3, next: None}}}
ListNode{val: 5, next: ListNode{val: 6, next: ListNode{val: 4, next: None}}}
<class 'precompiled.listnode.ListNode'>
Чудес не случилось. На вход мы получаем два односвязных списка. Собственно именно об этом сказано в условии задачи, а также это следует из аннотации аргументов метода addTwoNumbers():
l1: Optional[ListNode], l2: Optional[ListNode]
Вывод: нужно внимательно читать условия задачи и обращать внимание на аннотацию типов.
Разобравшись с типами аргументов метода addTwoNumbers(), я начал решение заново, так как код, который я уже написал, работал с другими типами данных.
Как следует из условий задачи, каждый из связных списков представляет собой число, которое к тому же записано в обратном порядке.
Следовательно, для того чтобы эти числа сложить, их нужно трансформировать из связного списка в числовой тип данных, то есть в int.
Трансформация связных списков в числа
Для решения поставленной задачи я создал переменные l1_str и l2_str со значением ». То есть я создал пустые строки, чтобы впоследствии добавлять в них элементы из узлов связных списков.
Далее с использованием цикла while я прохожусь по узлам каждого связного списка. На каждой итерации цикла я преобразую значение узла в строковое, чтобы с помощью конкатенации строк собрать все цифры из списка в одну строку.
Вот пример кода целиком применительно к одному из связных списков:
l1_str = ''
while l1:
l1_str += str(l1.val)
l1 = l1.next
В результате работы этого куска кода, при l1 = [2, 4, 3] переменная l1_str получит следующее значение: 243.
Аналогично работаю и со вторым связным списком.
Тут стоит оговориться, что мы получили строку, а не число. Кроме того, строку нужно еще будет развернуть.
Получаем результат сложения
Как я отметил выше, я получил строковый тип данных, сложение которых приведет к результату, который нам не нужен. Соответственно, нам нужно:
- развернуть строку;
- преобразовать строку в числовой тип данных.
Моя реализация, возможно, не самая элегантная, но она работает:
int(l1_str[::-1])
Думаю, что тут все очевидно, но, в первую очередь для себя, поясню. Сначала мы развернули строку, используя срезы — [::-1], а потом с помощью функции int() преобразовали строковый тип данных в числовой.
Аналогичным образом поступаю и со второй строкой.
Но и это еще не все! Результат сложения я вновь преобразую в строковый тип данных, а затем разворачиваю. Это нужно для того, чтобы на последнем этапе создать связный список, который, по условию задачи, мы и должны вернуть. В итоге все вышесказанное на языке Python будет выглядеть так:
result_str = str(int(l1_str[::-1]) + int(l2_str[::-1]))[::-1]
Создаем новый связный список и возвращаем его
На последнем этапе создаю новый связный список из получившегося результата сложения и последующего преобразования его в строковый тип данных и возвращаю его, как результат работы метода addTwoNumbers() класса Solution.
Для этого я использую метод append_node(), который я добавил в класс ListNode:
# Создаю первый узел связного списка
ll_result = ListNode(int(result_str[0]))
# Прохожусь по оставшимся элементам строки,
# чтобы поочередно добавить их в связный список
for element in result_str[1:]:
ll_result.append_node(int(element))
Собственно, а вот и сам метод append_node() класса ListNode:
def append_node(self, val):
node = ListNode(val)
n = self
while (n.next):
n = n.next
n.next = node
return node
Вот полный код решения задачи:
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def append_node(self, val):
node = ListNode(val)
n = self
while (n.next):
n = n.next
n.next = node
return node
class Solution:
def addTwoNumbers(
self,
l1: Optional[ListNode],
l2: Optional[ListNode]
) -> Optional[ListNode]:
l1_str = ''
while l1:
l1_str += str(l1.val)
l1 = l1.next
l2_str = ''
while l2:
l2_str += str(l2.val)
l2 = l2.next
result_str = str(int(l1_str[::-1]) + int(l2_str[::-1]))[::-1]
ll_result = ListNode(int(result_str[0]))
for element in result_str[1:]:
ll_result.append_node(int(element))
return ll_result
А вот и результат его работы:
Runtime – 68 ms — обгоняет 38,73% пользователей Python
Memory – 16.36 mb — обгоняет 31,27% пользователей Python
Согласен, не самые лучшие результаты, зато свои, без подсказок. Ладно, это лирика. Пока готовил эту публикацию, созрело еще одно решение, которое немного быстрее, но памяти требует больше.
Add two numbers. Подход 2.0
Основным отличием в версии решения, которую я оптимистично обозвал версией 2.0, состоит в том, что я сократил количество разворотов строк срезами. Вместо этого я развернул сами связные списки. По всей видимости, именно это и оказало влияние на скорость работы программы.
Вот код, который решает задачу по развороту связного списка:
tail_2 = None
head_2 = l2
while head_2:
head_2.next, tail_2, head_2 = tail_2, head_2, head_2.next
В остальной части код остался примерно таким же. Единственное, что при переносе значений узлов связных списков в строку значение первого узла переносится вне цикла while. Хотя ничто не мешает, немного изменив код, перенести «сборку» строки из значений узлов в цикл while целиком. Но, как я проверил, сильно на показатели решения это не влияет.
Соответственно, немного изменилось и получение результата сложения двух чисел. Выглядит теперь это читабельнее:
addition_result_str = str(int(l2_str) + int(l1_str))[::-1]
Как и в первом варианте решения, в конце я создаю новый связный список и возвращаю его в качестве результата работы метода addTwoNumbers().
Давайте посмотрим на результаты
Runtime – 65 ms — обгоняет 55,52 % пользователей Python
Memory – 16.36 mb — обгоняет 6,27 % пользователей Python
Вот полный код решения задачи:
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def append_node(self, val):
node = ListNode(val)
n = self
while (n.next):
n = n.next
n.next = node
return node
class Solution:
def addTwoNumbers(
self,
l1: Optional[ListNode],
l2: Optional[ListNode]
) -> Optional[ListNode]:
tail_1 = None
head_1 = l1
while head_1:
head_1.next, tail_1, head_1 = tail_1, head_1, head_1.next
l1_str = ''
node = tail_1
l1_str += str(node.val)
while node.next:
node = node.next
l1_str += str(node.val)
tail_2 = None
head_2 = l2
while head_2:
head_2.next, tail_2, head_2 = tail_2, head_2, head_2.next
l2_str = ''
node = tail_2
l2_str += str(node.val)
while node.next:
node = node.next
l2_str += str(node.val)
addition_result_str = str(int(l2_str) + int(l1_str))[::-1]
ll_result = ListNode(int(addition_result_str[0]))
for number in addition_result_str[1:]:
ll_result.append_node(int(number))
return ll_result
Собственно на этом и все! Хотел написать, что вы можете оставить свои комментарии, но потом вспомнил, что я еще на сайт не добавил возможность комментировать. Но вы можете написать мне в Telegram, вот так меня можно найти там: @Kirill_Barabanshchikov или перейдя прямо по вот этой ссылке
Буду дальше изучать связные списки, чтобы переработать решение этой задачи, а также решать остальные. Ну и искать варианты применения связных списков на практике.