Решения задач по Python с разбором типовых ошибок

Дополнительные примеры с подробным разбором

Здесь представлены более сложные и редкие примеры использования Python для алгоритмических задач. Каждый пример содержит код и результат выполнения.

Индексы элементов для заданной суммы

Дан список целых чисел и целевая сумма. Находятся индексы двух элементов, дающих в сумме целевое значение. Решение с одним проходом использует словарь для сохранения уже встреченных чисел.

def two_sum(nums, target):
    seen = {}
    for index, value in enumerate(nums):
        complement = target - value
        if complement in seen:
            return [seen[complement], index]
        seen[value] = index
    return []

nums = [2, 7, 11, 15]
print(two_sum(nums, 9))

[0, 1]

Сложность алгоритма O(n), так как каждый элемент обрабатывается один раз.

Решето Эратосфена

Для нахождения всех простых чисел до N создается булев список, где False обозначает составное число. Кратные каждого простого числа вычеркиваются.

def sieve(limit):
    if limit < 2:
        return []
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    for number in range(2, int(limit ** 0.5) + 1):
        if is_prime[number]:
            for multiple in range(number * number, limit + 1, number):
                is_prime[multiple] = False
    return [number for number, prime in enumerate(is_prime) if prime]

print(sieve(30))

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Проверка скобочной последовательности

Стек используется для сопоставления открывающих и закрывающих скобок. Каждая открывающая скобка помещается в стек, при встрече закрывающей проверяется соответствие.

def is_balanced(text):
    brackets = {'(': ')', '[': ']', '{': '}'}
    stack = []
    for character in text:
        if character in brackets:
            stack.append(character)
        elif character in brackets.values():
            if not stack or brackets[stack.pop()] != character:
                return False
    return not stack

print(is_balanced('[({hello})]'))

True

В конце стек должен быть пустым, иначе количество скобок не совпадает.

Транспонирование матрицы

Операция transpose превращает строки матрицы в столбцы. Генератор списка собирает элементы по номерам столбцов.

def transpose(matrix):
    return [list(row) for row in zip(*matrix)]

matrix = [
    [1, 2, 3],
    [4, 5, 6]
]
print(transpose(matrix))

[[1, 4], [2, 5], [3, 6]]

Сжатие повторяющихся символов

Код подсчитывает количество подряд идущих одинаковых символов и формирует строку вида символ+количество.

def rle_encode(text):
    if not text:
        return ''
    result = []
    count = 1
    for index in range(1, len(text)):
        if text[index] == text[index - 1]:
            count += 1
        else:
            result.append(text[index - 1] + str(count))
            count = 1
    result.append(text[-1] + str(count))
    return ''.join(result)

print(rle_encode('aaabbc'))

a3b2c1

Замер времени выполнения функции

Декоратор оборачивает функцию и выводит время, затраченное на выполнение. Внутренняя функция сохраняет имя и аргументы исходной функции через *args, **kwargs.

import time

def timeit(func):
    def wrapper(*args, **kwargs):
        start = time.perf_counter()
        result = func(*args, **kwargs)
        elapsed = time.perf_counter() - start
        print(f'{func.__name__}: {elapsed:.6f} секунд')
        return result
    return wrapper

@timeit
def compute_sum(n):
    return sum(range(n))

print(compute_sum(1000000))

compute_sum: 0.021234 секунд
499999500000

Время выполнения в каждом запуске отличается.

Мемоизация рекурсивных функций

Декоратор lru_cache сохраняет результаты вызовов функции. Это ускоряет рекурсивные вычисления, например для чисел Фибоначчи.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(number):
    if number < 2:
        return number
    return fib(number - 1) + fib(number - 2)

print(fib(50))

12586269025

Кэширование исключает повторное выполнение одних и тех же вычислений.

Пересечение двух списков

Множества поддерживают операцию пересечения, результат не сохраняет порядок. Для сохранения порядка применяется фильтрация по множеству.

list_a = [1, 2, 3, 4]
list_b = [3, 4, 5, 6]

intersection_set = sorted(set(list_a) & set(list_b))
print(intersection_set)

set_b = set(list_b)
intersection_ordered = [item for item in list_a if item in set_b]
print(intersection_ordered)

[3, 4]
[3, 4]

Генерация комбинаций и перестановок

combinations из itertools создает кортежи длиной r без повторений. permutations учитывает порядок.

from itertools import combinations, permutations

items = [1, 2, 3]
print(list(combinations(items, 2)))
print(list(permutations(items, 2)))

[(1, 2), (1, 3), (2, 3)]
[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

Случайная строка для токена

Для генерации пароля или ключа используется модуль secrets, предназначенный для криптографически безопасных случайных данных.

import secrets
import string

alphabet = string.ascii_letters + string.digits
random_string = ''.join(secrets.choice(alphabet) for _ in range(12))
print(random_string)

K7aF2tR9QpNw

Результат каждого запуска будет другим.

Поиск пропущенного числа

Если дан список чисел от 1 до n, в котором отсутствует одно значение, его можно найти через сумму.

def find_missing(numbers, n):
    expected_sum = n * (n + 1) // 2
    actual_sum = sum(numbers)
    return expected_sum - actual_sum

print(find_missing([1, 2, 3, 5, 6], 6))

4

Двоичное представление числа

Встроенная функция bin возвращает строку с префиксом '0b'. Для подсчета единиц используется count.

number = 10
binary = bin(number)
print(binary)
print(binary.count('1'))

0b1010
2