График, не часто проверяемый
определение
Узлы, соединенные друг с другом в виде сети
Связанное с интервью
Реализовать поиск в ширину и в глубину
Проверьте, является ли граф деревом
Подсчитайте количество ребер в графе
Найдите кратчайшее расстояние между двумя вершинами
Монотонный стек Монотонный стек редко тестируется
Двусторонняя очередь Deque, редко тестируется
Union Find редко тестируется
Деревья отрезков линий редко тестируются.
Древовидный массив Двоичное индексированное дерево, BIT, тестируется редко
Дерево словаря Trie, редко тестируется
определение
Также известно как: префиксное дерево, особая древовидная структура данных.
использовать
Очень эффективен при решении проблем, связанных со строками.
Автоматические предложения в поисковых системах
интервью
Подсчитайте общее количество слов в словарном дереве.
Распечатать все слова, хранящиеся в дереве словаря
Сортировка элементов массива с помощью дерева словаря
Формируйте слова из словаря с помощью словарного дерева.
Сборка словаря T9: дерево словаря DFS
Хэш-таблица/хеш-карта Хэш-таблица, часто проверяемая
определение
Храните уникально идентифицированные объекты в виде пар ключ-значение.
Словарь: коллекция пар ключ-значение.
Поиск значения объекта с помощью ключа ключа
HashSet/HashMap в Java, unordered_map в C, dict в Python
Поддерживаемые операции: O(1) Вставить / O(1) Найти / O(1) Удалить.
Как работают хеш-таблицы
<br>Принцип работы: Для комплекта. Ключ получает индекс через хэш-функцию, а затем значение сохраняется в массиве. <br>Для получения найдите индекс с помощью ключей и хеш-функций и получите значение.
Почему нельзя просто считать временную сложность различных операций над хэшем равной O(1)?
Ключ может быть строкой, целым числом или чем-то неизвестным. Поэтому уместно использовать O(L); в строгом смысле временная сложность любой операции равна O(keySize), а не O(1)<br>
Как реализовать хеш-функцию
Как решить проблему коллизии хэшей (Collision)
Коллизия означает, что два разных ключа получают два одинаковых значения после вычисления хэш-функцией. Существует два основных способа разрешения конфликтов:<br>Открытое хеширование. Это означает, что в массиве, на котором основана хеш-таблица, каждая позиция является головным узлом связанного списка. Таким образом, конфликтующие кортежи <key, value> помещаются в один связанный список. <br>Закрытое хеширование. Это означает, что при возникновении конфликта последующие элементы перейдут на следующую позицию, чтобы найти пустое место<br>
Как заставить хеш-таблицу постоянно расширяться?
Факторы производительности
Метод обработки столкновений
интервью
Найдите симметричные пары ключ-значение в массиве
Будет ли хеш-таблица использоваться гибко для решения проблемы?
Вы владеете основными принципами хеш-таблиц?
Отслеживайте полный путь для удобства
Узнать, является ли массив подмножеством другого массива
Проверяет, являются ли данные массивы непересекающимися
526. Балансировщик нагрузки<br>
134. Стратегия кэширования LRU<br>657. Вставка Удалить GetRandom O(1)<br>954. Вставка Удалить GetRandom O(1) - Допускаются дубликаты<br>209.
Проблемы класса потока данных<br>960. Первое уникальное число в потоке II<br>138. Сумма подмассивов<br>105. Копирование связанного списка со случайными указателями<br>171. 124. Самая длинная непрерывная последовательность
Сортировать поиск
Находить
статическая таблица поиска
динамическая таблица поиска
Определение структуры данных. Структуру данных можно рассматривать как набор данных и несколько операций (функций), определенных в этом наборе.
Метод тестирования 1: Спросите об основных принципах определенной структуры данных и попросите ее реализовать.
Пример: поговорим о принципе хеширования и реализуем хэш-таблицу.
Метод тестирования 2. Используйте какую-либо структуру данных для выполнения задач.
Пример: объединить K упорядоченных массивов
Метод тестирования 3: реализация структуры данных для предоставления некоторых конкретных функций.
Пример: проблема с наиболее часто встречающимся элементом K
временная сложность:
Опишите временную сложность нескольких интерфейсов<br>
Например, вам нужно спроектировать структуру данных Set.
Алгоритм 1: O(n) нижняя граница O(1) добавить
Метод реализации: использовать хранилище массива, каждый раз сравнивать и вставлять непосредственно в конец массива.
Алгоритм 2: O(logn) lowBound O(logn) add
Метод реализации: использовать хранилище Red-black Tree, TreeSet в Java, карту в C.
Массив Массив, наиболее часто тестируемый
тип
подмассив
Вопросы для интервью
41. 42,43, Максимальный подмассив<br>44. Минимальный подмассив<br>138.
Проблема с интервалом массива
Вопросы для интервью
30. Вставка диапазонов<br>793. Пересечение нескольких массивов<br>156.
проблема с внешней сортировкой
Определение: Алгоритм внешней сортировки — это алгоритм сортировки данных, хранящихся в одном или нескольких больших файлах, при нехватке памяти. <br>
Два основных шага:<br>Разрежьте большой файл на несколько маленьких файлов и используйте память для их соответствующей сортировки.<br>Используйте алгоритм слияния K-way (k-way merge) для сортировки нескольких маленьких файлов. Объедините в один большой файл.
Вопросы для интервью
486. Объединить K отсортированных массивов<br>104. Объединить K отсортированных списков.
Битовые операции
Определение: Операции с двоичными битами.
Вопросы для интервью
365. Сколько единиц в двоичной системе координат<br>
Древовидные массивы редко рассматриваются
Также известно как: Fenwick Tree. Английское название: Binary Indexed Tree. Сокращение: BIT реализуется на основе префикса и информации<br>
Хотя имя — «Дерево», оно хранится в массиве (Array).<br>BIT представляет собой несколько деревьев, а отношения «родитель-потомок» представляют собой отношения включения.<br>Используйте getPrefixSum(k) для реализации getRangeSum(x, y) )
временная сложность
Log(n) Изменить значение в любой позиции<br>Log(n) Запросить сумму любого интервала
Функции
Для массива с N числами поддерживаются следующие функции:<br>update(index, val) //Обновляем значение в позиции массива за время logN getPrefixSum(k) //Получаем его за время log(K) Сумма первых K чисел массива
Вопросы для интервью
817. Переменная-сумма элемента матрицы диапазона<br>249. Подсчитайте количество предыдущих чисел, меньших самого себя.
Связанное с интервью
Найдите второй наименьший элемент массива
Найдите первое неповторяющееся целое число
Переставить положительные и отрицательные значения в массиве
65. Медиана двух отсортированных массивов, сложная задача<br>
6. Объединить отсортированные массивы II<br>64. Объединить отсортированные массивы<br>839. Объединить два отсортированных списка интервалов<br>486. Объединить K отсортированных массивов<br>547. два массива<br>548. Пересечение двух массивов<br>793. Пересечение нескольких массивов<br>654. Умножение разреженной матрицы<br>931. Медиана из K отсортированных массивов<br>149. время<br>405. Подматрица, сумма которой равна нулю<br>944. Максимальная подматрица<br>943. Запрос суммы диапазона - неизменяемая<br>665. Суммарная матрица диапазона плоскостей<br>840.
Стек стека, не часто тестируется
определение
ЛИФО. Например, при логистической загрузке товары, загруженные позже, выгружаются первыми.
Поддерживаемые операции: O(1) Push / O(1) Pop / O(1) Top
приложение
Используется для нерекурсивного обхода бинарных деревьев, вычисления обратных польских выражений и т. д.
Основная структура данных нерекурсивной реализации DFS
При поиске в ширину (BFS) записываются узлы, которые необходимо расширить.
Очереди можно использовать для реализации очередей сообщений для выполнения асинхронных задач.
Когда скорость создания и потребления сообщений непостоянна, необходима очередь сообщений для временного хранения сообщений, которые были отправлены, но не получены.
Реализация режима стека
Используйте структуру хранения (обычно используемые массивы, иногда связанные списки) для хранения элементов.
Использовать один массив для реализации трех стеков?
Реализовать стек, используя две очереди? <br>
разница
Массивы имеют лучшую производительность при произвольном доступе. <br>Связанные списки имеют лучшую производительность при вставке и удалении элементов.
Упражнения<br>
lintcode: 495. Реализация стека
494. Стек реализации двойной очереди<br>
224. Используйте массив для реализации трех стеков<br>
действовать
нажать, вставить элемент вверху
pop возвращает и удаляет верхний элемент стека
isEmptyСтек пуст и возвращает true
top возвращает верхний элемент, не удаляя его.
Java использует java.util.Stack, который является наследником класса Vector и поддерживает такие операции, как push(), pop(), peek(), пустой() и поиск().
C, просто используйте стек в <stack>. Этот метод аналогичен Java, за исключением того, что peek() в C называется top(), а когда pop(), возвращаемое значение пусто.
Python, используйте список напрямую, используйте операции нарезки, такие как [-1], для просмотра вершины стека, используйте list.pop() при извлечении вершины стека и используйте list.append() при перемещении вершины стека . <br>
Связанное с интервью
Использование стека для оценки постфиксных выражений
Сортировка элементов стека
Определить, является ли выражение сбалансированным в скобках
QueueQueue, часто тестируется
определение
Линейная структура хранения последовательных данных FIFO, касса в супермаркете
Поддерживаемые операции: O(1) Push / O(1) Pop / O(1) Top
приложение
Используется в качестве основной структуры данных для алгоритма BFS.
действовать
Вставить элементы в конец очереди
dequeue удаляет головной элемент очереди
Столбец isEmpty пуст и возвращает true
top возвращает первый элемент очереди
Метод реализации
Реализовать очередь, используя связанный список?
Реализовать очередь с двумя стеками? <br>
Реализовать очередь, используя круговой массив?
Упражнение: 955. Реализация очереди с помощью кругового массива<br>
интервью
Используйте очередь для представления стека
Поменяйте местами первые k элементов очереди
Используйте очередь для генерации двоичных чисел от 1 до n
642. Скользящее среднее из потока данных<br>
955. Реализация очереди с помощью кругового массива<br>
Связанный список, часто проверяемый
определение
Цепочка узлов: каждый узел содержит данные и указатели на последующие узлы.
использовать
Реализация файловой системы, хеш-таблицы, списка смежности.
тип
односторонний связанный список
действовать
isEmpty, пусто, возвращает true
интервью
Обнаружение циклов в связанных списках
Возвращает n-й узел от последнего в связанном списке.
Удалить дубликаты из связанного списка
ДеревоДерево
определение
иерархическая структура данных
Состоит из вершин и ребер
В дереве нет циклов, как показано на графике.
тип
Деревья отрезков линий принципиально не тестируются, они универсальны.
Бинарное дерево, часто проверяемое
двоичное дерево поиска
Определение: левое поддерево меньше корневого узла, а корневой узел меньше правого поддерева. Эффект таков: левая сторона всегда меньше правой.
сбалансированное двоичное дерево
Сбалансированное дерево (дерево AVL)
определение:
Это пустое дерево или абсолютное значение разницы высот между его левым и правым поддеревьями не превышает 1, а левое и правое поддеревья являются сбалансированными двоичными деревьями.
Выполнение
Красно-черное дерево, АВЛ, дерево козла отпущения, Треп, раскидистое дерево.
куча
Определение: Куча — это сбалансированное двоичное дерево. Родительский узел меньше дочернего узла. Лишние дочерние узлы максимально размещаются в левом дочернем узле. Между левым и правым дочерними узлами нет соотношения размеров. Может быть реализовано с использованием массивов<br>
Поддерживаемые операции: O(log N) Добавить / O(log N) Удалить / O(1) Мин. или Макс.
Максимальная куча против минимальной кучи
Характеристики значения: для кучи минимального типа родительский узел меньше дочернего узла, и между левым и правым дочерними узлами нет соотношения размеров, для кучи максимального типа родительский узел больше дочернего узла, и там; нет отношения размера между левым и правым дочерними узлами;
Структурные характеристики: Это двоичное дерево высотой logN.
Временная сложность: сложность удаления и извлечения равна logN, найти минимальную или максимальную сложность O(1)<br>
Метод вставки: всегда вставляйте слева, обеспечивая сбалансированное двоичное дерево. Если вставленное число небольшое, переместите его вверх, а родительский узел переместится вниз. Таким образом, максимальная сложность равна logN<br>
Метод удаления аналогичен
Метод реализации: Упражнение: lintcode 130 heapify<br>
Практические вопросы на собеседовании
104. Объединить K отсортированных списков<br>612. K ближайших точек<br>545. Top K больших чисел II<br>613. Отличные результаты<br>486. Объединить K отсортированных массивов<br>81. цифры<br>544. Верхние K больших чисел<br>401 k-е число от меньшего к большему в матрице сортировки.
Дерево сегментов<br>
Определение: Дерево отрезков линий — это расширенная структура данных и древовидная структура, если быть точным, это двоичное дерево. Он может эффективно решать такие проблемы, как запросы на изменение интервала. <br>
Примечание. По сути, оно не тестировалось, но если вы освоите его, вы сможете решить множество проблем за один раз. Дерево отрезков линий реализовано на основе метода «разделяй и властвуй» и может использоваться в качестве хорошей практики для разделения. и победить метод.
интервью
Найдите высоту двоичного дерева
Найдите k-е максимальное значение в бинарном дереве поиска.
Найдите узел, находящийся на расстоянии k от корневого узла.
Найдите узлы-предки данного узла в двоичном дереве.
104. Объединить K отсортированных списков<br>
3 метода
Способ 1: используйте PriorityQueue
Метод 2. Алгоритм «разделяй и властвуй», аналогичный сортировке слиянием.
Метод 3: Алгоритм попарного слияния снизу вверх
Временная сложность O(NlogK).
В сочетании с: алгоритмом Цзючжан
Все практические вопросы — это вопросы по lintcode.
Wondershare EdrawMind
