Начало работы с интерфейсными алгоритмами -- Структуры данных

Базовые знания

1) Что такое алгоритм?

Алгоритмы — это шаги, которые вычисляют или решают проблему.

2) В чем разница между алгоритмом и программой?

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

3) Как выбрать алгоритм?

Для одной и той же задачи у разных разработчиков разные решения, разные языки программирования и разные методы написания.Целью установления критериев оценки алгоритмов является выбор оптимального алгоритма. Есть два критерия для оценки плюсов и минусов алгоритма: один — это объем памяти, который требуется от запуска до вычисления результата, а другой — сколько времени требуется от запуска до вычисления результата. соответственно называется,космическая сложность,временная сложность. В целом, чем ниже сложность, тем меньше потребление памяти, тем быстрее выполняется и тем легче это понять людям. в общем,Самое главное - время работы алгоритма.

4) Как отразить время работы алгоритма?

Различные алгоритмы, разные устройства и разные объемы данных приведут к различиям во времени алгоритма.Время работы, рассчитанное теорией, является полиномом, и нам нужно иметь возможность понять взаимосвязь между временем и объемом данных наиболее интуитивным способом, и часто игнорируют неважные термины, чтобы получить простейшее выражение, которое лучше всего может отражать тенденцию времени выполнения, мы пишем: игнорирование неважных элементов, которое может быть записано в виде O(n), что может наиболее просто выразить отношение между временем выполнения и объемом данных, где O — верхний регистр, что означает игнорирование содержимого, кроме важных элементов, произношение такое же, как порядок; n означает количество данных, участвующих в алгоритме.

структура данных

★ Почему несколько структур данных?
В зависимости от цели использования использование различных типов данных может обеспечить использование пространства памяти.

1) Связанный список

Связный список является одной из структур данных, и его данные расположены линейно, в пространстве памяти данные разбросаны и хранятся в памяти, и каждые данные состоят из двух частей, одна часть - это сами данные, а другая часть является указателем, указывающим на следующий кусок памяти. При доступе к данным к ним можно обращаться только один за другим по указателю, пока они не будут найдены или доступны до конца.Если количество данных в связанном списке равно n, то для поиска данных необходимо самое быстрое время, и большинство из них нужно искать n раз; когда вам нужно добавить или удалить часть данных в связанном списке, вам нужно изменить только один или два указателя данных, независимо от количества данных в связанном списке, это постоянно.

резюме:
Данные связанного списка являются линейными, пространство для хранения прерывистым, временная сложность доступа равна O(n), а временная сложность добавления и удаления составляет O(1).

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

2) Массив

Массивы также являются одной из линейно расположенных структур данных, отличие их от связанных списков в том, что хранение массивов в пространстве памяти непрерывно. При доступе к массиву вам нужно только найти соответствующую позицию по индексу массива.Сложность поиска - постоянный уровень, выраженный как O(1).Расширение массива. Затем переместите каждый элемент назад по очереди.Сложность этого процесса составляет O(n), а если элемент добавляется в конец массива, сложность становится равной O(1).Точно так же, когда элемент удаляется, когда удаление хвоста равно O(1) и O(n) при удалении головы. Видно, что по сравнению со связанными списками, массив хоть и удобнее для запросов, но сложность операции выше.

3) стек

Стек представляет собой линейную структуру данных. Когда элемент добавляется в стек, этот элемент добавляется на вершину стека. Когда элемент удаляется, он может быть прочитан только из самой передней позиции в одном направлении, а затем последние могут быть прочитаны Элементы, то есть последние должны быть добавлены, но первыми быть прочитаны, поэтому стек называется режимом «последним пришел — первым вышел» (LIFO), а способ добавления и удаления данных — также называется нажатием и извлечением стека. Из-за характеристик стека LIFO он часто используется для хранения самых последних данных.

4) Очередь

Очередь также является структурой данных с линейной структурой.Она очень похожа на стек.Это односторонняя упорядоченная операция.Однако очередь пришла,первая вышла,а очередь похожа на очередь.Первым вышел (FIFO), для доступа к следующим элементам можно получить доступ только к предыдущим элементам, прежде чем можно будет получить доступ к целевому элементу. Операции добавления и удаления очередей также известны как постановка в очередь и удаление из очереди.

5) Хэш-таблица

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

6) куча

Куча представляет собой разновидность графа и представляет собой двумерную структуру данных. Ее представление может быть представлено двузначной древовидной диаграммой. Значение данных дочернего узла всегда больше, чем значение родительского узла. В куче данные вверху всегда самые маленькие, поэтому независимо от количества данных сложность выборки наименьшего значения всегда равна O(1). Кроме того, поскольку необходимо переместить последние данные наверх после выборки данных, а затем двигаться вниз, сравнивая их с размером данных дочернего узла, время выполнения, необходимое для выборки данных, пропорционально высоте дерева. , предполагая количество данных Для n, в соответствии с характеристиками формы кучи, высота дерева log2n, тогда сложность восстановления дерева O (logn). То же самое верно для добавления данных. Добавить данные в конец кучи, и сравниваем данные с размером родительского узла, при этом продвигаясь вверх до тех пор, пока не будут выполнены условия кучи.
Если вам нужно часто извлекать минимальное значение из данных, то куча — хороший выбор.

7) Бинарное дерево поиска

Бинарное дерево поиска также называют бинарным деревом поиска или бинарным отсортированным деревом. Это своего рода двумерная структура графа. Его характеристики таковы: каждый узел имеет не более двух узлов, называемых левым поддеревом и правым поддеревом соответственно, значение в каждом узле больше, чем значение в его левом поддереве, и значение в каждом узле меньше, чем его значение в правом поддереве. .
Согласно этим двум характеристикам:Двоичное дерево поиска находит минимальное значение в нижнем левом конце и находит максимальное значение в нижнем правом конце..

резюме

Какую структуру данных выбрать, следует определять в соответствии с целью использования.Вышеуказанные 7 типов обычно используются во внешнем интерфейсе.Как гибко использовать эти структуры данных? Что может быть сделано? Пожалуйста, смотрите следующий эпизод.

конец статьи

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

Готовитесь к интервью? Давайте поговорим и улучшайте себя каждый день, когда вы подходите к вопросам интервью; вы готовы перейти к расширенному полному стеку? Давайте поговорим о продвинутом способе и избегайте обходных путей; Устали набирать код? Приходите и пообщайтесь в группе, чтобы сделать работу более эффективной.

Из-за ограничений в настоящее время их более 200, и к ним можно присоединиться только по приглашению.Поэтому, пожалуйста, выполните поиск в общедоступной учетной записи [Front-end Advanced Interview Internal Push], и я приглашу вас присоединиться к группе. Приходи сюда, чтобы найти больше единомышленников для фронтенд-партнеров~