Хеш-таблицы представляют собой чрезвычайно полезную структуру данных, поскольку поиск в среднем занимает ожидаемое время O (1), то есть объем работы, выполняемой хеш-таблицей для выполнения поиска, в лучшем случае является константой. Некоторые проблемы, связанные со структурой данных и алгоритмами, могут быть очень эффективно решены с помощью хеширования, которые в противном случае имеют высокую временную сложность.
В этом посте мы перечислим несколько проблем, которые можно элегантно решить с помощью хеширования со значительной экономией времени и пространства. Мы рекомендуем ознакомиться со следующими структурами данных, прежде чем приступать к проблемам хеширования.
std::set
,std::map
,std::unordered_set
,std::unordered_map
in C++HashMap
,HashSet
,TreeMap
в JavaDictionary
,Set
в Python
- Найти пару с заданной суммой в массиве
- Проверить, существует ли подмассив с нулевой суммой
- Вывести все подмассивы с нулевой суммой
- Найти самую длинную подпоследовательность, состоящую из последовательных целых чисел
- Найти дубликаты в заданном диапазоне k в массиве
- Подсчитать различные абсолютные значения в отсортированном массиве
- Найти подмассив по заданной сумме в заданном массиве целых чисел
- Найти наибольший подмассив, состоящий из последовательных целых чисел
- Найти повторяющийся элемент в массиве с ограниченным диапазоном
- Найти подмассив максимальной длины, имеющий одинаковое количество нулей и единиц
- Найти подмассив максимальной длины по заданной сумме
- Найти мажоритарный элемент в массиве (алгоритм большинства голосов Бойера – Мура)
- Пользовательская сортировка | Сортировать массив на основе другого массива
- Пользовательская сортировка | Сортировать элементы по их частоте и индексу
- Эффективная сортировка массива с множеством повторяющихся значений
- Рассчитать частоту всех элементов, присутствующих в массиве указанного диапазона, в линейное время и с использованием постоянного пространства
- Заменить каждый элемент массива на его соответствующий ранг
- Группировать элементы массива по первому вхождению
- Найти все симметричные пары в массиве пар
- Построить самый длинный палиндром путем перемешивания или удаления символов из строки
- Найти количество различных элементов в каждом подмассиве размера k
- Распечатать все подмассивы массива, имеющего отдельные элементы
- Найти минимальный индекс повторяющегося элемента в массиве
- Найти индекс максимального встречающегося элемента с равной вероятностью
- Проверить, сформирован ли массив последовательными целыми числами
- Найти две неперекрывающиеся пары с одинаковой суммой в массиве
- Найти подмассивы с заданной суммой в массиве
- Проблема с 3 разделами
- Найти два нечетно встречающихся элемента в массиве, не используя лишнего места
- Найти пары с заданной разностью k в массиве
- Найти нечетно встречающийся элемент в массиве за один проход
- Определить, равны ли два целых числа без использования операторов сравнения и арифметических операций
- Задача на 4 суммы | Четверки с заданной суммой
- Найти триплет с заданной суммой в массиве
- Найти количество превосходящих для каждого элемента массива
- Построить двоичное дерево по порядку и порядку уровней
- Построить двоичное дерево из обходов inorder и postorder
- Построить бинарное дерево из обхода по порядку и по предзаказу
- Клонировать двоичное дерево со случайными указателями
- Эффективно распечатайте все узлы между двумя заданными уровнями в двоичном дереве
- Найти предварительный обход двоичного дерева по его порядку и послепорядку
- Печать правого вида двоичного дерева
- Найти обход двоичного дерева по порядку и по порядку следования двоичного дерева
- Итеративно выводить путь от листа к корневому для каждого листового узла в двоичном дереве
- Найти пару с заданной суммой в BST
- Найти максимальную ширину заданного двоичного дерева
- Построить двоичное дерево из заданного родительского массива
- Найти диагональную сумму заданного двоичного дерева
- Печать диагонального обхода двоичного дерева
- Выполнить вертикальный обход бинарного дерева
- Найти вертикальную сумму в заданном двоичном дереве
- Найти предков данного узла в двоичном дереве
- Печать двоичного дерева сверху
- Печать двоичного дерева снизу
- Печать бинарного дерева слева
- Вывести все узлы идеального двоичного дерева в определенном порядке
- Обход двоичного дерева в обратном порядке
- Обход двоичного дерева по спирали
- Обход двоичного дерева с порядком уровней
- Построить двоичное дерево из матрицы предков
- Найти вероятность того, что человек жив после N шагов на острове
- Узлы ссылок присутствуют на каждом уровне двоичного дерева в виде связанного списка
- Преобразование двоичного дерева в двусвязный список по спирали
- Удалять дубликаты из связанного списка за один проход
- Определить цикл в связанном списке (алгоритм определения цикла Флойда)
- Клонировать связанный список со случайными указателями
- Найти все общие элементы, присутствующие в каждой строке данной матрицы
- Сгенерировать список возможных слов из символьной матрицы
- Найти общие элементы, присутствующие во всех строках матрицы
- Найти повторяющиеся строки в двоичной матрице
- Найти все слова из данного списка, которые следуют тому же порядку символов, что и заданный образец
- Найти все возможные комбинации, заменив заданные цифры на символы из соответствующего списка
- Изоморфные струны
- Определить, являются ли две строки анаграммой или нет
- Проверить, присутствует ли в строке повторяющаяся подпоследовательность
Спасибо за чтение.