Топ 45 алгоритмических задач по Python

Бинарный поиск — это алгоритм, используемый для поиска элемента в отсортированном массиве путем многократного деления интервала поиска пополам. Принцип алгоритма бинарного поиска очень прост. Мы всегда имеем дело с упорядоченным массивом. Это позволяет прибегать к хитрости - на каждой итерации цикла, который мы запускаем, мы вычисляем индекс среднего элемента. Этот элемент сравниваем с искомым. Если элемент из середины массива оказался меньше, чем тот, что мы ищем, значит нужный нам находится правее по массиву, ведь массив упорядочен. Соответственно, нам нужно перейти в следующую итерацию цикла, "оставляя" ей лишь правую часть массива - в ней снова будет найден средний элемент и алгоритм повторится. Если же элемент из середины массива оказался больше искомого, то мы переходим к следующей итерации, отбрасывая правую часть массива, а оставляя левую. Если же элемент совпадает с искомым, мы выходим из цикла. def BinarySearch(lys, val): first = 0 last = len(lys)-1 index = -1 while (first <= last) and (index == -1): mid = (first+last)//2 if lys[mid] == val: index = mid else: if val<lys[mid]: last = mid -1 else: first = mid +1 return index Также, вместо цикла мы могли бы обратиться к рекурсии. Я не могу написать бинарный поиск

Задача: Необходимо реализовать функцию, принимающую в аргументах строку, состоящую из букв и вернуть новую строку, в которой повторяющиеся буквы заменены количеством повторений. # AAAABBCAA --> A4B2C1A2 Решение: def encode_message(message): encoded_string = "" i = 0 while (i <= len(message)-1): count = 1 ch = message[i] j = i while (j < len(message)-1): if (message[j] == message[j + 1]): count = count + 1 j = j + 1 else: break encoded_string = encoded_string + str(count) + ch i = j + 1 return encoded_string Приведенный фрагмент содержит функцию encode_message() с параметром message (строка), подлежащим кодированию. Переменная encoded_string используется для хранения закодированной строки. Цикл while инициализируется с счетчиком с значением 1 и итерируется по всем символам строки. Внутренний цикл while проверяет, совпадает ли символ текущего индекса с символом следующего индекса. Если символы совпадают, то счётчик инкрементируется. Если нет, то счетчик и символ конкатенируются в переменную encoded_string и возвращаются. Алгоритм имеет сложность O (n). Также можно воспользоваться функцией groupby из модуля itertools. Она превратит последовательность элементов в последовательность групп повторяющихся символов. from itertools import groupby def rle_encode(data: str) -> str: return "".join(str(len(list(group_items))) + key for key, group_items in groupby(data)) Простейшие алгоритмы сжатия: RLE и LZ77

Палиндром — это последовательность символов, которая одинаково читается в обоих направлениях. 1. Метод с использованием индексации Первый и самый простой способ проверить, является ли строка палиндромом, — использовать трюк с индексацией для получения «зеркальной» строки и сравнения её с исходной. s = "radar" if s == s[::-1]: print("Это палиндром") else: print("Это не палиндром") 2. Метод с использованием цикла Мы можем также использовать цикл для определения палиндрома, сравнивая символы на симметричных позициях. s = "radar" is_palindrome = True for i in range(len(s) // 2): if s[i] != s[-i - 1]: is_palindrome = False break if is_palindrome: print("Это палиндром") else: print("Это не палиндром") 3. Использование функции Проверку на палиндром можно также реализовать с помощью рекурсивной функции. def is_palindrome(s): if len(s) < 2: return True if s[0] != s[-1]: return False return is_palindrome(s[1:-1]) 4. Определение палиндрома с учетом пробелов и знаков препинания Если вы хотите проверить, является ли строка палиндромом, игнорируя пробелы, знаки препинания и регистр, вы можете использовать методы lower() и replace(), а также функцию isalnum() для удаления всех небуквенных символов. s = "A man, a plan, a canal: Panama" s = ''.join(c for c in s if c.isalnum()).lower() if s == s[::-1]: print("Это палиндром") else: print("Это не палиндром") 5. Использование стека Этот подход использует структуру данных «стек», чтобы сохранить первую половину строки и затем сравнить ее с обратной половиной. def is_palindrome(s): s = ''.join(c for c in s if c.isalnum()).lower() stack = list() for character in s: stack.append(character) for character in s: if character != stack.pop(): return False return True Алгоритмы для поиска палиндромов Алгоритм поиска самой длинной подстроки-палиндрома АТАТА: распутываем задачу про палиндром

Анаграмма — это перестановка букв одного слова для получения нового слова. 1. Решение без оптимизации Для начала рассмотрим простейший способ. Для каждой строки мы создадим словарь, который будет хранить количество вхождений каждого символа. Затем мы сравним словари и выясним, являются ли строки анаграммами. Вот как может выглядеть код для реализации данного алгоритма: def is_anagram(str1, str2): # создаем словарь для первого слова dict1 = {} for char in str1: dict1[char] = dict1.get(char, 0) + 1 # создаем словарь для второго слова dict2 = {} for char in str2: dict2[char] = dict2.get(char, 0) + 1 # сравниваем словари return dict1 == dict2 На этом решение задачи поиска анаграмм без оптимизации можно считать выполненной. Однако этот алгоритм не оптимален. 2. Оптимизация алгоритма Можно заметить, что мы используем два словаря для каждого слова. Это может быть неэффективно, особенно, если слова достаточно длинные. Вместо хранения двух словарей мы можем использовать один словарь и удалять из него ключи, которые мы уже нашли. После этого мы снова сравниваем словари. Если они равны, значит слова являются анаграммами. Вот как может выглядеть оптимизированный код: def is_anagram(str1, str2): # создаем словарь для первого слова dict1 = {} for char in str1: dict1[char] = dict1.get(char, 0) + 1 # проверяем второе слово for char in str2: if char in dict1: dict1[char] -= 1 if dict1[char] == 0: del dict1[char] else: return False # если словарь пуст, значит слова являются анаграммами return not dict1 Теперь код выглядит более эффективно, но он все еще имеет недостатки. 3. Более сложная оптимизация Работа с словарями может быть медленной, особенно если слова достаточно длинные. Мы можем использовать более продвинутые алгоритмы, чтобы ускорить этот процесс. Один из таких алгоритмов — это использование массивов. Мы можем создать два массива фиксированной длины, которые будут хранить количество букв в каждом слове. Затем мы можем проходить по каждой букве в обоих словах и увеличивать счетчики в массиве. По завершении прохода мы можем сравнить массивы. Если они равны, значит слова являются анаграммами. Вот как может выглядеть код для этого алгоритма: def is_anagram(str1, str2): # создаем массивы count1 = [0] * 26 count2 = [0] * 26 # заполняем массивы for char in str1: index = ord(char) - ord('a') count1[index] += 1 for char in str2: index = ord(char) - ord('a') count2[index] += 1 # сравниваем массивы return count1 == count2 Поиск анаграмм и сабанаграмм во всех словах языка

Первый способ — использование цикла for string = "Привет, мир!" count = 0 for char in string: if char in "аеёиоуыэюяАЕЁИОУЫЭЮЯ": count += 1 print("Количество гласных букв:", count) #Количество гласных букв: 3 Второй способ — использование метода count() # Введите строку input_string = "Пример строки на русском языке" # Преобразуем строку к нижнему регистру, чтобы учитывать гласные в верхнем и нижнем регистре input_string = input_string.lower() # Определите гласные для русского языка vowels = "аеёиоуыэюя" # Используйте sum() и count() для подсчета количества каждой гласной vowel_count = sum(input_string.count(vowel) for vowel in vowels) # Выведите результат print(f"Количество гласных в строке: {vowel_count}") #Количество гласных в строке: 10 Третий способ — использование регулярных выражений import re string = "Привет, мир!" count = len(re.findall("[аеёиоуыэюяАЕЁИОУЫЭЮЯ]", string)) print("Количество гласных букв:", count) #Количество гласных букв: 3 Четвертый способ — использование генераторов списков string = "Привет, мир!" vowels = [char for char in string if char in "аеёиоуыэюяАЕЁИОУЫЭЮЯ"] count = len(vowels) print("Количество гласных букв:", count) #Количество гласных букв: 3

Постановка: Напишите функцию для проверки симметричности двоичного дерева. Примеры деревьев: Дерево 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 Структуры данных: бинарные деревья. Часть 1 Бинарные деревья поиска и рекурсия – это просто