Проверяем двоичные деревья на симметричность, вычисляем расстояние Дамерау-Левенштейна и оцениваем сложность алгоритмов.

Задание 1

Напишите программу, которая принимает на вход целое число, и возвращает целое число, цифры в котором переставлены в обратном порядке. Например, если введено число 561, программа должна вернуть 165, а если -578, то -875. Решите задачу двумя способами – с использованием методов строк и без. Какое решение более эффективно?

Решение

При использовании методов строк задача решается максимально просто:

         def reverse_integer(num):     num_str = str(num)     if num_str[0] == "-":         reverse_str = "-" + num_str[:0:-1]      else:         reverse_str = num_str[::-1]      

Для решения без использования строк нужно запустить цикл while, который будет выполняться до тех пор, пока num_remaining не станет равным нулю. В каждой итерации цикла происходит следующее:

• Умножаем result на 10 и прибавляем к нему остаток от деления num_remaining на 10 (таким образом, последняя цифра числа num_remaining становится первой цифрой числа result).
• Затем num_remaining делится нацело на 10, чтобы удалить последнюю цифру.
• После окончания цикла возвращается значение result, причем если исходное число num было отрицательным, то возвращается -result.

Например, если num равно 123, то в первой итерации цикла result станет равным 3, а num_remaining станет равным 12. Во второй итерации result станет равным 32, а num_remaining станет равным 1. В третьей итерации result станет равным 321, а num_remaining станет равным 0, что приведет к завершению цикла. В итоге функция вернет число 321. Временная сложность этого решения – O(n), где n равно числу цифр в числе:

         def reverse_integer(num):     result, num_remaining = 0, abs(num)     while num_remaining:         result = result * 10 + num_remaining % 10         num_remaining //= 10     return -result if num < 0 else result      

Сравним быстродействие решений:

         import timeit  def reverse_integer_1(num):     result, num_remaining = 0, abs(num)     while num_remaining:         result = result * 10 + num_remaining % 10         num_remaining //= 10     return -result if num < 0 else result  def reverse_integer_2(num):     num_str = str(num)     if num_str[0] == "-":         reverse_str = "-" + num_str[:0:-1]      else:         reverse_str = num_str[::-1]     return int(reverse_str)  # Тестируем на случайном числе из 10000 цифр num = int("".join(str(i % 10) for i in range(10000)))  # Сравниваем время выполнения двух функций t1 = timeit.timeit(lambda: reverse_integer_1(num), number=100) t2 = timeit.timeit(lambda: reverse_integer_2(num), number=100) print(f"Время выполнения решения с циклом: {t1:.6f} секунд") print(f"Время выполнения с методом строк: {t2:.6f} секунд")      

Решение, использующее методы строк, работает заметно быстрее:

         Время выполнения решения с циклом: 9.354593 секунд Время выполнения с методом строк: 0.213387 секунд      

Это связано с тем, что встроенная функция [::-1] для инвертирования строки в Python реализована на C-уровне и оптимизирована для работы с символами.

🐍 Библиотека питониста Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека питониста» 🐍💼 Библиотека собеса по Python Подтянуть свои знания по Python вы можете на нашем телеграм-канале «Библиотека собеса по Python» 🧩🐍 Библиотека задач по Python Интересные задачи по Python для практики можно найти на нашем телеграм-канале «Библиотека задач по Python»

Задание 2

Вычислите частное от деления x на y, где х и y – целые положительные числа. Допустимые операции – сложение, вычитание и побитовый сдвиг.

Решение

Это задачка с подвохом – простейшее решение, при котором y в цикле вычитается из x до тех пор, пока остаток не станет меньше, чем y, окажется самым затратным. Например, если y = 1, a x = 231 –1, для вычисления потребуется 231 – 1 итераций:

         def divide(x, y):     quotient = 0     remainder = x     while remainder >= y:         remainder -= y         quotient += 1     return quotient     

Более оптимальный подход:

• Найти наибольшее число k, при котором 2k y <= x.
• Вычесть 2k y из x.
• Добавить 2k к частному.

К примеру, если х = (1011)2 и y = (10)2, то k = 2, поскольку 2 * 22 <= 11 и 2 * 23 > 11. Мы вычитаем (1000)2 из (1011)2, получаем (11)2, добавляем 2k = 22 = (100)2 к частному, и обновляем значение x = (11)2.

Главные преимущества при использовании 2k y – это значение очень эффективно вычисляется с помощью битового сдвига, а значение x уменьшается по крайней мере вдвое с каждой итерацией. Однако наш алгоритм все еще далек от совершенства: если для представления частного от деления x на y потребуется n битов, вычисление будет завершено за O(n) итераций. Если наибольшее k, при котором 2k y <= x, вычисляется итеративно через k, каждая итерация имеет временную сложность O(n), что в итоге приведет к O(n2) алгоритму.

Более эффективный способ найти k в каждой итерации – учесть, что k последовательно уменьшается. То есть вместо того, чтобы каждый раз проверять, что 20y, 21y, 22y меньше либо равно x, после первого обнаружения k, при котором 2k y <= x, в последующих итерациях с x нужно сравнивать 2k-1y, 2k-2, 2k-3y и так далее.

В приведенном выше примере после обнаружения первого k значение частного равно (100)2 к, а x = (11)2. Теперь наибольшее число k, при котором 2k y <= (11)2 равно 0, поэтому мы добавляем 20 = (1)2 к частному, которое после этого будет равно (101)2. Продолжаем цикл с (11)2 – (10)2 = (1)2. Поскольку (1)2 < y, вычисление завершается – частное равно (101)2, остаток равен (1)2. По сути, оптимальное решение применяет деление путем вычитания к двоичным числам и обрабатывает дополнительный бит с каждой новой итерацией. Мы используем сдвиг влево на power разрядов, так как это соответствует умножению на 2**power. Предполагая, что сдвиг и операция сложения занимают О(1), получим решение с временной сложностью O(n):

         def divide (x, y):     result, power = 0, 32     y_power = y << power     while x >= y:         while y_power > x:             y_power >>= 1             power -= 1         result += 1 << power         x -= y_power     return result       

Сравним время выполнения брутфорсного и оптимизированного алгоритмов:

         import timeit  def divide_1(x, y):     quotient = 0     remainder = x     while remainder >= y:         remainder -= y         quotient += 1     return quotient  def divide_2(x, y):     result, power = 0, 32     y_power = y << power     while x >= y:         while y_power > x:             y_power >>= 1             power -= 1         result += 1 << power         x -= y_power     return result  x, y = 1000000, 7 time_1 = timeit.timeit(lambda: divide_1(x, y), number=1000) time_2 = timeit.timeit(lambda: divide_2(x, y), number=1000) print(f"Время выполнения брутфорсного алгоритма: {time_1}") print(f"Время выполнения оптимизированного алгоритма: {time_2}")      

Результат:

         Время выполнения брутфорсного алгоритма: 9.041366940829903 Время выполнения оптимизированного алгоритма: 0.003612866159528494      

💼 Вакансии по Python, Django, Flask Лучшие вакансии из мира Python @pydevjob

Задание 3

Имеются текст text и подстрока st. Напишите программу, которая находит индекс первого вхождения st в text.

Решение

Брутфорсный подход – создать вложенный цикл:

         def find_st(text, st):     n = len(text)     m = len(st)     for i in range(n - m + 1):         j = 0         while j < m and text[i+j] == st[j]:             j += 1         if j == m:             return i     return -1      

Временная сложность этого алгоритма O(nm), где n – длина текста, а m – длина подстроки. Эффективнее использовать один из специальных алгоритмов поиска подстроки – Бойера-Мура, Рабина-Карпа или Кнута-Морриса-Пратта. Воспользуемся алгоритмом Рабина-Карпа – его преимущество в том, что хеши вычисляются очень быстро, а сравнивать строки приходится только при совпадении хешей. Это значительно ускоряет поиск по сравнению с перебором всех срезов подряд:

         import functools  def rabin_karp(text, st):     if len(st) > len(text):         return -1      BASE = 33     text_hash = functools.reduce(lambda h, c: h * BASE + ord(c), text[:len(st)], 0)     st_hash = functools.reduce(lambda h, c: h * BASE + ord(c), st, 0)     power_st = BASE**max(len(st) - 1, 0)      for i in range(len(st), len(text)):         if text_hash == st_hash and text[i - len(st):i] == st:             return i - len(st)          text_hash -= ord(text[i - len(st)]) * power_st         text_hash = text_hash * BASE + ord(text[i])     if text_hash == st_hash and text[-len(st):] == st:         return len(text) - len(st)     return -1   text = "В роще-чаще рыщет ящер, ищет пищи подходящей" st = "ще" print(rabin_karp(text, st))     

Вывод:

         4     

При условии правильного выбора хеш-функции временная сложность этого решения равна O(n+m).

Задание 4

Напишите функцию для проверки симметричности двоичного дерева. Примеры деревьев:

         Дерево 1:         1        /        /         2     2     /    /     3   4 4   3  Дерево 2:         1        /        /         2     2     /    /     3   5 6   3  Дерево 3:         1        /        /         2     2     /           5         5      

Первое и третье деревья симметричны, а второе – нет.

Решение

В соответствии с условием симметричным деревом считается дерево, которое симметрично и с точки зрения структуры, и с точки зрения значений узлов. Чтобы проверить дерево на симметричность, можно создать его зеркальное отражение и сравнить его с оригиналом. Временная и пространственная сложность такого алгоритма – O(n), где n – число узлов. Проверку можно оптимизировать, если вместо создания отражения целого дерева сравнивать пары поддеревьев – временная сложность такого подхода O(n), а пространственная – O(h), где h – высота дерева:

         def is_tree_symmetric(tree):     def check_symmetric(subtree_0, subtree_1):         if not subtree_0 and not subtree_1:             return True         elif subtree_0 and subtree_1:             return (subtree_0.data == subtree_1.data                     and check_symmetric(subtree_0.left, subtree_1.right)                     and check_symmetric(subtree_0.right, subtree_1.left))         return False     return not tree or check_symmetric(tree.left, tree.right)      

Пример использования с заданными в условии деревьями:

         from collections import namedtuple Node = namedtuple('Node', ['data', 'left', 'right'])  tree1 = Node(1, Node(2, Node(3, None, None), Node(4, None, None)), Node(2, Node(4, None, None), Node(3, None, None))) tree2 = Node(1, Node(2, Node(3, None, None), Node(5, None, None)), Node(2, Node(6, None, None), Node(3, None, None))) tree3 = Node(1, Node(2, Node(5, None, None), None), Node(2, None, Node(5, None, None)))             for t in [tree1, tree2, tree3]:   print(is_tree_symmetric(t))      

Вывод:

         True False True      

Задание 5

Напишите программу для подсчета количества правок, которые нужно выполнить, чтобы преобразовать строку S1 в строку S2. Например, для преобразования слова «лимузин» в «лимонад» нужно сделать 4 правки, а для приведения слова «кошка» к слову «кофта» достаточно 2 изменений.

Решение

Брутфорсный подход – перечислить все строки, отличающиеся на 1, 2, 3 и так далее символов от первой строки, пока не получим вторую строку. В худшем случае нужно будет перебрать 2n вариантов. Более оптимальный подход – воспользоваться алгоритмом вычисления расстояния Дамерау-Левенштейна.

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

Принцип вычисления расстояния Левенштейна выглядит так:

1. Допустим, у нас есть две строки S1 и S2, которые мы хотим сравнить. Мы создаем матрицу M размером (len(S1) + 1) x (len(S2) + 1). Каждая ячейка матрицы M[i][j] будет представлять минимальное расстояние между подстроками S1[0:i] и S2[0:j].

2. На первом этапе инициализируются первая строка и первый столбец матрицы M: в ячейку M[i][0] помещаем значение i, а в ячейку M[0][j] помещаем значение j, так как для превращения пустой строки в S1 или S2 необходимо выполнить i или j операций вставки или удаления соответственно.

3. Затем заполняем оставшуюся часть матрицы M. Для этого рассматриваем каждую пару символов S1[i-1] и S2[j-1]. Если они совпадают, то M[i][j] просто равно M[i-1][j-1], и ничего менять не нужно. В противном случае, M[i][j] равно минимуму из следующих трех значений:

• M[i-1][j] + 1 (удаление символа из S1)
• M[i][j-1] + 1 (вставка символа в S1)
• M[i-1][j-1] + 1 (замена символа в S1 на символ из S2)

Результат – в нижем правом углу матрицы M (M[len(S1)][len(S2)]) окажется минимальное расстояние между строками S1 и S2. Это значение равно минимальному количеству операций вставки, удаления и замены, необходимых для преобразования S1 в S2. Вот так выглядит матрица вычисления расстояния Левенштейна для слов «кошка» и «кофта»:

                | к | о | ф | т | а |    --------------------------    | 0 | 1 | 2 | 3 | 4 | 5 | -----------------------------  к | 1 | 0 | 1 | 2 | 3 | 4 | -----------------------------  о | 2 | 1 | 0 | 1 | 2 | 3 | -----------------------------  ш | 3 | 2 | 1 | 1 | 2 | 3 | -----------------------------  к | 4 | 3 | 2 | 2 | 2 | 3 | -----------------------------  а | 5 | 4 | 3 | 3 | 3 | 2 | -----------------------------      

Временная сложность этого решения – O(len(s1)*len(s2)):

         def levenshtein_distance(S1, S2):     def fill_matrix(S1_idx, S2_idx):         if S1_idx < 0:             return S2_idx + 1         elif S2_idx < 0:             return S1_idx + 1         if M[S1_idx][S2_idx] == -1:             if S1[S1_idx] == S2[S2_idx]:                 M[S1_idx][S2_idx] = (fill_matrix(S1_idx - 1, S2_idx - 1))             else:                 substitute_last = fill_matrix(S1_idx - 1, S2_idx - 1)                 add_last = fill_matrix(S1_idx - 1, S2_idx)                 delete_last = fill_matrix(S1_idx, S2_idx - 1)                 M[S1_idx][S2_idx] = (1 + min(substitute_last, add_last, delete_last))         return M[S1_idx][S2_idx ]     M = [[-1] * len(S2) for _ in S1]     return fill_matrix(len(S1) - 1, len(S2) - 1) print(levenshtein_distance('кошка', 'кофта'))     

Вывод:

         2     

***

Материалы по теме

• 🐍 Функции в Python: 5 задач для тренировки *args, **kwargs и lambda-функций
• 6 алгоритмов решения задач по спортивному программированию
• 🐍🧩 Обработка вложенных списков и матриц в Python: 5 задач с решениями для совершенствования навыков