Как внешний интерфейс подготавливает структуры данных и алгоритмы?

внешний интерфейс алгоритм

1. Введение

Насколько я знаю, довольно много front-end программистов не очень понимают основные понятия "структура данных" и "алгоритм", что напрямую вызывает у многих людей разочарование, когда они видят содержание этой части.

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

Многие студенты, изучающие передовые технологии, будут испытывать определенное сопротивление, увидев «структуру данных» и «алгоритм», или попытаются попрактиковаться, но окажутся в тупике и сдадутся.

Это большая часть причины, потому что вы недостаточно знаете об их значении, или нет разумного метода упражнений.

На самом деле, когда у вас есть определенная цель и разумный метод практики, будет удобно выучить эту часть заново.

В этой статье я поделюсь своим опытом и методами изучения «структур данных» и «алгоритмов».

Позже я также проведу всесторонний анализ всех распространенных структур данных и классификаций алгоритмов.

1.1 Описание категории

Существует множество типов структур данных и алгоритмов.В качестве примера возьмем деревья.Типы деревьев включают:бинарные деревья,B-деревья,B+ деревья,Trie деревья,красно-черные деревья и т.д.В этой статье выбраны только бинарные деревья.

Для фронтенда нет необходимости знать больше о некоторых более предвзятых типах и решениях: одно — пустая трата драгоценного времени, а другое — мало приложений.

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

1.2 Описание темы

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

Источник темы:

  • awesome-coding-js: Мой открытый проект алгоритма внешнего интерфейса, включая темы, которые я сделал, и подробный анализ.
  • leetcode
  • 剑指offer

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

2. Зачем изучать структуры данных и алгоритмы

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

Это облегчит вам получение пользы от процесса обучения и придаст вам мотивации к учебе.

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

2.1 Идея решения проблемы

Компьютер — это просто очень холодная машина, какую команду вы ему дадите, какой ответ он может дать.

Что должны сделать инженеры-разработчики, так это как преобразовать практические проблемы в компьютерные инструкции и как их преобразовать Давайте посмотрим на классическое утверждение «Структура данных»:

Разработайте структуру данных и примените алгоритм.

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

Если Java — это автомобиль с автоматической коробкой передач, то C — это джип с механической коробкой передач. А структуры данных? Вот так работает коробка передач. Вы можете вести машину с автоматической коробкой передач от А до Б, не зная, как работает коробка передач, и не обязательно медленнее, чем тот, кто знает. Написание программы, как вождение автомобиля, большую роль может сыграть опыт, но если не знать, как работает нижний слой, можно только вечно ездить, ни ремонтировать, ни строить. Если вас не интересует ни одна из этих вещей, ничего страшного, если вы знаете, как использовать структуры данных. Но если в этой жизни у вас есть более высокие цели в области программирования, структура данных — неизбежная тема.

2.2 Интервью

Это очень важный момент, и причина, по которой многие интерфейсы изучают структуры данных и алгоритмы.

В целом отношение к алгоритмам можно разделить на следующие категории:

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

Вторая категория заключается в том, что алгоритм является важным фактором.Некоторые крупные отечественные фабрики также будут использовать структуру данных и алгоритм в качестве важного справочного фактора во время интервью.В основном, интервью требуется.Если вы не соответствуете определенным требованиям, вы будете прямо повесить трубку.

Третья категория — дополнительные баллы.Многие компании не относятся к структурам данных и алгоритмам как к жестким требованиям, но они также дают некоторые символические вопросы.Когда вы красиво отвечаете на вопрос об алгоритме, это определенно бонусный пункт.

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

3. Как подготовиться

Зная важность структур данных и алгоритмов, какой метод следует использовать для подготовки?

3.1 Всестороннее понимание

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

В следующих главах этой статьи я проведу всесторонний анализ общих структур данных и алгоритмов.

3.2 Упражнение по классификации

Получив общее представление о структурах данных и алгоритмах, можно приступать к практике.

Обратите внимание, это должно быть упражнение по классификации! Практика классификации! Практика классификации! Важные вещи говорятся трижды.

Я видел много одноклассников, которые с энтузиазмом начинали чистить вопросы.leetcodeВ начале первый вопрос, часто очень мотивированный в начале, а еще может постить круг друзей или точку кипения или еще что 😅, а дальше уже нет.

Поскольку первые несколько вопросов очень просты, они могут придать вам определенную уверенность, но если вы будете следовать порядковому номеру, то вскоре столкнетесь сhard. Или некоторые люди просто чистят простые и заканчивают сначала все простые.

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

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

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

3.3 Периодический обзор и сводка

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

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

Итак, когда вы видите проблему, в первую очередь вы должны думать о том, к какой структуре данных или алгоритму она принадлежит, затем к какой это проблеме, а затем к решению такой проблемы.

Если вы видите новую задачу и не можете сделать вышеперечисленное, значит, вы недостаточно освоили такого рода задачи, и вам нужно потратить больше опыта на практику.

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

3.4 Выбор тем

Что касается источника темы, то здесь я рекомендую сначала прочитать "Sword Fingers".offer",Послеleetcode«Доказать безопасностьoffer", вы можете найти много типичных тем, что очень важно для вас, чтобы открыть и обобщить правила. Почистить после прочтенияleetcodeВам будет легче.

По поводу выбора сложности, вот предлагаюleetcodeПростой и средней сложности достаточно, потому что нам нужно найти правила, то есть освоить типичные задачи.Когда вы освоите эти правила, вы сможете решить некоторые задачи.hardПроблема тоже возможна, просто вопрос в том, чтобы тратить больше времени. Прежде всего, не тратьте слишком много времени на множество каверзных вопросов.

После описанного выше метода, попрактиковавшись некоторое время, я в основномleetcodeВопросы средней сложности можно найти в20minВнутриAC, Кроме того, в процессе смены места работы в последнее время я могу быстро выписать почти все задачи по алгоритмам от руки или быстро придумать идеи решения проблем. Я надеюсь, что каждый сможет добиться такого же эффекта, увидев мой опыт и метод, или сделает это лучше меня.

В-четвертых, временная сложность и пространственная сложность

Прежде чем мы начнем учиться, мы должны сначала понять концепции временной сложности и пространственной сложности, которые вместе определяют качество фрагмента кода:

4.1 Временная сложность

Временная сложность алгоритма отражает время, необходимое программе для выполнения от начала до конца. Временная сложность алгоритма — это количество раз (частота), которые повторяются основные операции в алгоритме.

Нет оператора цикла, помнитеO(1), также известный как постоянный порядок. При наличии только одного цикла частота выполнения основной операции алгоритма линейно возрастает с размером задачи n, что обозначается какO（n）, также известный как линейный порядок.

Общие временные сложности:

  • O(1): Постоянная сложность: Постоянная постоянная сложность
  • O(log n): Логарифмическая сложность: Логарифмическая сложность
  • O(n): Линейная сложность: Линейная временная сложность
  • O(n^2): N квадрат Квадрат сложности
  • O(n^3): N квадратная сложность
  • O(2^n): Индекс экспоненциального роста
  • O(n!): факториал

4.2 Пространственная сложность

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

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

Пять, структура данных

Я полагаю, что все знакомы со словом структура данных, и вы, возможно, слышали его во многих сценариях, но задумывались ли вы когда-нибудь о том, что такое «структура данных»?

Структура данных — это набор одного или нескольких конкретных отношений, существующих между элементами данных.

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

5.1 Логическая структура

Проще говоря, логическая структура — это связь между данными, и логическую структуру можно условно разделить на два типа: линейная структура и нелинейная структура.

Линейная структура: представляет собой упорядоченный набор элементов данных. Связь между элементами данных представляет собой связь «один к одному», то есть, кроме первого и последнего элементов данных, остальные элементы данных связаны встык.

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

- Нелинейная структура: отдельные элементы данных больше не поддерживаются в линейной последовательности, и каждый элемент данных может быть связан с нулем или более другими элементами данных.

Распространенными нелинейными структурами являются двумерные массивы, деревья и т. д.

5.2 Структура хранения

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

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

5.3 Структура данных — двоичное дерево

Дерево используется для моделирования набора данных с древовидной структурой. По своим характеристикам его можно разделить на множество типов.Нам достаточно освоить структуру бинарного дерева.Это также самый простой и широко используемый тип дерева.

Бинарное дерево представляет собой типичную древовидную структуру. Как следует из названия, бинарное дерево представляет собой древовидную структуру с не более чем двумя поддеревьями на узел, обычно называемыми «левым поддеревом» и «правым поддеревом».

5.3.1 Обход бинарного дерева

Ключевым моментом является то, что лучше всего освоить как рекурсивную, так и нерекурсивную версии.Рекурсивную версию легко написать, но нерекурсивная версия — это то, что действительно исследует основы.

Реконструкция бинарного дерева по характеристикам обхода в прямом и обратном порядке, обратное мышление, очень интересная тема

5.3.2 Симметрия бинарных деревьев

5.3.3 бинарное дерево поиска

Бинарное дерево поиска — это особое бинарное дерево.Тема изучения бинарного дерева поиска, как правило, заключается в изучении характеристик бинарного дерева поиска, поэтому очень важно освоить его характеристики.

  1. Если левое поддерево любого узла не пусто, значение всех узлов левого поддерева меньше значения его корневого узла;
  2. Если правое поддерево любого узла не пусто, значение всех узлов в правом поддереве больше, чем значение его корневого узла;
  3. Левое и правое поддеревья любого узла также являются бинарными деревьями поиска соответственно.

5.3.4 Глубина бинарного дерева

Глубина бинарного дерева — это количество узлов на самом длинном пути от корневого узла до самого дальнего листового узла.

Сбалансированное бинарное дерево: разница между глубинами левого и правого поддеревьев больше 1

5.4 Структура данных — связанный список

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

  • Для запроса элементов требуется обход, и запрос выполняется медленно.
  • Для вставки элемента нужно только отключить и переназначить, и вставка выполняется быстро.

Связанные списки также часто используются при разработке структур данных.React16изFiber Nodeобразован путем соединенияFiber Tree- это отдельно связанная структура списка.

5.4.1 Базовое применение

Это в основном применение основных понятий и характеристик связанных списков.Если основные понятия твердо усвоились, такие проблемы могут быть легко решены.

5.4.2 Проблемы с кольцом

Проблема кольцевого класса — это проблема, полученная из оценки того, есть ли цикл в односвязном списке.

5.4.3 Двойной указатель

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

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

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

5.4.4 Двусвязный список

Двойная цепочка также имеет ссылочное поле, называемоеprevполе. С помощью этого дополнительного поля вы можете узнать предыдущий узел текущего узла.

5.5 Структуры данных — массивы

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

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

5.5.1 Двойной указатель

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

5.5.2 Проблема суммы N чисел

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

5.5.3 Двумерные массивы

Установите определенную способность к абстрактному моделированию, чтобы абстрагироваться от многих практических проблем.

5.5.4 Статистика

Массивы неотделимы от статистики и вычислений, и такие вопросы исследуют, как выполнять статистические вычисления с массивами более эффективным способом.

5.6 Структуры данных — стеки и очереди

В приведенном выше массиве мы можем получить доступ к элементам случайным образом по индексу, но в некоторых случаях мы можем захотеть ограничить порядок доступа к данным, поэтому есть две структуры данных, которые ограничивают порядок доступа: стек (последний вошел первым), очередь (первым прибыл, первым обслужен)

5.7 Структура данных — хэш-таблица

Основной принцип хеширования заключается в преобразовании заданного значения ключа в адрес смещения для извлечения записи.

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

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

Как спроектировать хэш-функции и как избежать коллизий — общие проблемы с хеш-таблицами. Есть два критерия выбора хорошей хеш-функции:

  • 1. Простой и способный быстро считать
  • 2. Возможность получения равномерного распределения ключей в адресном пространстве

Например, следующая тема:

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

5.8 Структура данных — куча

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

  • Значение каждого элемента узла не меньше, чем у его дочерних элементов - max heap
  • Значение каждого элемента узла не больше, чем у его дочерних элементов - min-heap

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

6. Алгоритм

6.1 Сортировка

Сортировка может быть алгоритмом с наибольшим контактом во внешнем интерфейсе. Путь алгоритма многих людей начинается с пузырьковой сортировки. Существует много методов сортировки, каждый из которых имеет свои сценарии применения, преимущества и недостатки. Здесь я рекомендую следующие 6 типов. Наиболее используемый метод сортировки, если вам интересно, вы также можете изучить несколько других.

Выберите целевое значение, поместите его слева, если оно меньше целевого значения, и поместите его справа, если оно больше целевого значения Положение целевого значения было упорядочено, а левая и правая стороны быстро устроится.

Разделите большую последовательность на маленькие последовательности, отсортируйте маленькие последовательности, а затем объедините отсортированные маленькие последовательности в большую последовательность.

Каждая сортировка берет наибольшее или наименьшее число и помещает его в предыдущую отсортированную последовательность.

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

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

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

6.2 Бинарный поиск

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

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

6.3 Рекурсия

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

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

Чтобы рекурсивная функция не вызывала бесконечный цикл, она должна иметь следующие свойства:

  • Простой базовый случай — схема завершения, которая может дать ответ без рекурсии.
  • Набор правил, также известный как рекуррентное отношение, которое разбивает все остальные случаи на базовые.

6.3.1 Двойной счет

Некоторые проблемы используют рекурсию для рассмотрения, идея очень ясна, но рекурсия не рекомендуется, например следующие проблемы:

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

вы можете использовать记忆化Метод, позволяющий избежать повторных вычислений, т. е. открыть дополнительное пространство для хранения вычисленного значения, но при этом будет потрачен определенный объем памяти. Поэтому вышеперечисленные проблемы обычно решаются с помощью динамического программирования.

Поэтому перед использованием рекурсии обязательно оцените, содержит ли код повторяющиеся вычисления, если да, то использовать рекурсию не рекомендуется.

Рекурсия — это идея, а не тип, и многие классические алгоритмы основаны на рекурсии, поэтому здесь больше нет вопросов.

6.4 Поиск в ширину

Поиск в ширину (BFS) — это алгоритм, который проходит или ищет структуру данных, такую ​​как дерево или граф, и может также использоваться в более абстрактных сценариях.

Его характеристика состоит в том, что узлы, расположенные ближе к корневому узлу, будут пройдены раньше.

Например, мы можем использоватьBFSНайдите путь от начального узла к целевому узлу, особенно кратчайший путь.

существуетBFS, порядок обработки узлов точно такой же, как и порядок их добавления в очередь, то есть «первым пришел — первым вышел», поэтому поиск в ширину обычно реализуется с использованием очередей.

6.5 Поиск в глубину

Как и поиск в ширину, поиск в глубину (DFS) — важный алгоритм обхода/поиска в дереве/графе.

а такжеBFSИными словами, узел, доступ к которому был получен ранее, может не быть узлом, расположенным ближе к корню. Следовательно, выDFSПервый найденный путь может не быть кратчайшим путем.

существуетDFS, узлы обрабатываются в порядке, прямо противоположном тому, как если бы они добавлялись в стек, это LIFO. Поэтому поиск в глубину обычно реализуется с использованием стеков.

6.6 Алгоритм поиска с возвратом

Система выбирает допустимое решение из всех возможных вариантов на каждом шаге решения задачи.

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

Все варианты задачи, решаемой методом поиска с возвратом, можно представить в виде древовидной структуры.

  • На шаге есть n возможных вариантов, которые можно рассматривать как узел дерева.
  • Каждая опция узла рассматривается как соединение узла, достигающее его n дочерних узлов.
  • Листовые узлы соответствуют терминальным состояниям.
  • Если листовой узел удовлетворяет ограничениям, это возможное решение.
  • Узел листьев не удовлетворяет ограничениям, обратно в узел и попробуйте другие узлы листьев.
  • Если все дочерние узлы узла не соответствуют условию, затем вернитесь к предыдущему узлу.
  • Все состояния не могут удовлетворять условиям, и задача не имеет решения.

Алгоритмы поиска с возвратом подходят для задач, состоящих из нескольких шагов, и каждый шаг имеет несколько вариантов.

6.7 Динамическое программирование

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

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

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

6.7.1 Проблемы с путями

6.7.2 Вопросы покупки и продажи акций

проблема следствия

6.8 Жадные алгоритмы

Жадный алгоритм: при решении проблемы всегда делайте то, что кажется лучшим в данный момент.

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

6.8.1 Проблемы покупки и продажи акций

6.8.2 Проблемы с выбором валюты

6.9 Различия между жадными алгоритмами, динамическим программированием и поиском с возвратом

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

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

7. Возможность внешнего кодирования

Эта часть наиболее близка к фронтенд-разработке.При написании бизнес-кода мы также должны позаботиться о внутренней реализации некоторых библиотек классов или фреймворков.

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

Ниже я выбрал несколько вопросов:

8. Резюме

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

В этой статье проводится не глубокий анализ каждого пункта, а всесторонний анализ структур данных и алгоритмов с точки зрения почему, как и что делать (для front-end точки зрения).Я надеюсь, что после прочтения этого статьи, вам помогут следующие идеи:

  • Создать более комплексную когнитивную систему для структур данных и алгоритмов
  • Научитесь быстро изучать структуры данных и алгоритмы
  • Понимать важные категории и классические типы вопросов структур данных и алгоритмов

Если вы хотите узнать больше о структурах данных и алгоритмах, обратите внимание на мои последующие статьи.

Порекомендуйте мое резюме алгоритма:awesome-coding-js:GitHub.com/con AR DL i/Арвен…

Если в статье есть ошибки, исправьте их в комментариях, если статья вам поможет, ставьте лайк и подписывайтесь.

Если вы хотите читать больше качественных статей, вы можете подписаться на меняблог на гитхабе, твоя звезда✨, лайки и внимание - движущая сила моего постоянного творчества!

Рекомендую обратить внимание на мой паблик WeChat [code secret garden], каждый день выкладывать качественные статьи, будем общаться и расти вместе.

Мы являемся научно-исследовательской командой ByteDance Interactive Entertainment, включая Douyin Short Video, Douyin Volcano, TikTok, Faceu, Qingyan, Jianying и т. д. По состоянию на январь 2020 года Douyin Daily Active (DAU) превысил 400 миллионов человек и продолжает поддерживать быстрый рост. . Вы будете поддерживать разработку продуктов и связанные с ними архитектурные работы, где каждая строка кода может повлиять на сотни миллионов пользователей.

Код набора в школу 2021:DRZUM5Z

Официальный сайт доставки:job.toutiao.com/s/JR8SthH

Категории