Проверяем двоичные деревья на симметричность, вычисляем расстояние Дамерау-Левенштейна и оцениваем сложность алгоритмов.
Задание 1
Напишите программу, которая принимает на вход целое число, и возвращает целое число, цифры в котором переставлены в обратном порядке. Например, если введено число 561, программа должна вернуть 165, а если -578, то -875. Решите задачу двумя способами – с использованием методов строк и без. Какое решение более эффективно?
Решение
При использовании методов строк задача решается максимально просто:
Для решения без использования строк нужно запустить цикл 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 равно числу цифр в числе:
Сравним быстродействие решений:
Решение, использующее методы строк, работает заметно быстрее:
Это связано с тем, что встроенная функция [::-1] для инвертирования строки в Python реализована на C-уровне и оптимизирована для работы с символами.
🐍 Библиотека питониста
Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека питониста»
🐍💼 Библиотека собеса по Python
Подтянуть свои знания по Python вы можете на нашем телеграм-канале «Библиотека собеса по Python»
🧩🐍 Библиотека задач по Python
Интересные задачи по Python для практики можно найти на нашем телеграм-канале «Библиотека задач по Python»
Задание 2
Вычислите частное от деления x на y, где х и y – целые положительные числа. Допустимые операции – сложение, вычитание и побитовый сдвиг.
Решение
Это задачка с подвохом – простейшее решение, при котором y в цикле вычитается из x до тех пор, пока остаток не станет меньше, чем y, окажется самым затратным. Например, если y = 1, a x = 231 –1, для вычисления потребуется 231 – 1 итераций:
Более оптимальный подход:
- Найти наибольшее число 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):
Сравним время выполнения брутфорсного и оптимизированного алгоритмов:
Результат:
💼 Вакансии по Python, Django, Flask
Лучшие вакансии из мира Python @pydevjob
Задание 3
Имеются текст text и подстрока st. Напишите программу, которая находит индекс первого вхождения st в text.
Решение
Брутфорсный подход – создать вложенный цикл:
Временная сложность этого алгоритма O(nm), где n – длина текста, а m – длина подстроки. Эффективнее использовать один из специальных алгоритмов поиска подстроки – Бойера-Мура, Рабина-Карпа или Кнута-Морриса-Пратта. Воспользуемся алгоритмом Рабина-Карпа – его преимущество в том, что хеши вычисляются очень быстро, а сравнивать строки приходится только при совпадении хешей. Это значительно ускоряет поиск по сравнению с перебором всех срезов подряд:
Вывод:
При условии правильного выбора хеш-функции временная сложность этого решения равна O(n+m).
Задание 4
Напишите функцию для проверки симметричности двоичного дерева. Примеры деревьев:
Первое и третье деревья симметричны, а второе – нет.
Решение
В соответствии с условием симметричным деревом считается дерево, которое симметрично и с точки зрения структуры, и с точки зрения значений узлов. Чтобы проверить дерево на симметричность, можно создать его зеркальное отражение и сравнить его с оригиналом. Временная и пространственная сложность такого алгоритма – O(n), где n – число узлов. Проверку можно оптимизировать, если вместо создания отражения целого дерева сравнивать пары поддеревьев – временная сложность такого подхода O(n), а пространственная – O(h), где h – высота дерева:
Пример использования с заданными в условии деревьями:
Вывод:
Задание 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. Вот так выглядит матрица вычисления расстояния Левенштейна для слов «кошка» и «кофта»:
Временная сложность этого решения – O(len(s1)*len(s2)):
Вывод:
***