Примеры задач с использованием хеш-таблиц

8.1 Задача на поиск дубликатов в массиве

Задача: Дан массив чисел. Необходимо найти и вернуть все дубликаты в массиве.

Решение: Используем хеш-таблицу для отслеживания чисел, которые уже встречались. Если число встречается повторно, добавляем его в список дубликатов.

Пример реализации:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Примеры использования
arr1 = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr1))  # Вывод: [2, 4]

arr2 = []
print(find_duplicates(arr2))  # Вывод: []

arr3 = [1, 2, 3, 4, 5]
print(find_duplicates(arr3))  # Вывод: []

Пояснение:

• Создаём пустое множество seen для отслеживания уникальных чисел.
• Проходим по каждому элементу массива. Если элемент уже есть в seen, добавляем его в список duplicates.
• Если элемент не найден в seen, добавляем его туда.
• Возвращаем список дубликатов.

Обратите внимание, что функция корректно работает с пустым массивом и с массивом без дубликатов, возвращая пустой список в обоих случаях.

8.2 Задача на проверку анаграмм

Задача: Даны две строки. Необходимо определить, являются ли они анаграммами (содержат одни и те же символы в одинаковом количестве).

Решение: Используем хеш-таблицу для подсчёта частоты символов в обеих строках и сравниваем результаты.

Пример реализации:

def are_anagrams(str1, str2):
    # Приводим строки к нижнему регистру для учета разного регистра букв
    str1 = str1.lower()
    str2 = str2.lower()
    
    if len(str1) != len(str2):
        return False
    char_count = {}
    # Подсчёт частоты символов в первой строке
    for char in str1:
        char_count[char] = char_count.get(char, 0) + 1
    # Вычитание частоты символов во второй строке
    for char in str2:
        if char in char_count:
            char_count[char] -= 1
        else:
            return False
    # Проверка, что все значения в словаре равны 0
    return all(count == 0 for count in char_count.values())

# Примеры использования
print(are_anagrams("listen", "silent"))  # Вывод: True
print(are_anagrams("hello", "world"))  # Вывод: False
print(are_anagrams("", ""))  # Вывод: True
print(are_anagrams("Tea", "Eat"))  # Вывод: True

Пояснение:

• Если длины строк не совпадают, они не могут быть анаграммами.
• Используем словарь char_count для подсчёта частоты символов в первой строке.
• Проходим по второй строке и вычитаем частоту символов.
• Проверяем, что все значения в словаре равны нулю. Если так, строки являются анаграммами.

Обратите внимание, что функция учитывает регистр букв, приводя обе строки к нижнему регистру перед сравнением. Также она корректно обрабатывает пустые строки, считая их анаграммами друг друга.

8.3 Задача на нахождение пар с заданной суммой

Задача: Дан массив чисел и целевое значение суммы. Необходимо найти все пары чисел, которые в сумме дают целевое значение.

Решение: Используем хеш-таблицу для хранения чисел и проверки, образуют ли они пару с текущим числом, которая даёт целевую сумму.

Пример реализации:

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []
    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)
    return pairs

# Пример использования
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Вывод: [(1, 5), (1, 5)]

Пояснение:

• Создаём пустое множество seen для отслеживания чисел.
• Для каждого числа в массиве вычисляем его дополнение complement (разница между целевой суммой и текущим числом).
• Если дополнение уже есть в seen, добавляем пару (complement, num) в список pairs.
• Добавляем текущее число в seen.
• Возвращаем список пар.

Важно отметить, что данный алгоритм имеет временную сложность O(n), где n — количество элементов в массиве. Это значительно эффективнее наивного решения с двойным циклом, которое имеет сложность O(n^2). Использование хеш-таблицы позволяет нам найти все пары за один проход по массиву, что особенно важно при работе с большими объёмами данных.

Для сравнения, вот как выглядело бы наивное решение с временной сложностью O(n^2):

def find_pairs_naive(arr, target_sum):
    pairs = []
    n = len(arr)
    for i in range(n):
        for j in range(i+1, n):
            if arr[i] + arr[j] == target_sum:
                pairs.append((arr[i], arr[j]))
    return pairs

# Пример использования
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_naive(arr, target_sum))  # Вывод: [(1, 5), (1, 5)]

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

2

Задача

Модуль 1: Python Core, 16 уровень, 7 лекция

Недоступна

Поиск дубликатов

Поиск дубликатов

Открыть

2

Задача

Модуль 1: Python Core, 16 уровень, 7 лекция

Недоступна

Анаграммы

Анаграммы

Открыть