Для кого эта статья?

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

Предварительные требования

  • Вам необходимо иметь базовое представление об общих структурах данных, таких как «Массив, Связанный список, Хеш-карта, Стек, Очередь, Куча и График».

А как насчет узоров

  • Цель состоит в том, чтобы понять основной шаблон, чтобы мы могли применять этот шаблон для решения других проблем.
  • В интервью по кодированию, проводимом FANG (Facebook, Amazon, Netflix и Google), эти этапы кодирования на собеседовании основаны на действительно новом уровне мышления, эти этапы кодирования связаны не только с тем, насколько хорошо вы кодируете, но и с тем, как вы будете думать и как вы определяете проблема и дать оптимальное решение.
  • Прежде чем писать код для конкретного алгоритма, задайте вопрос или проблему. Во-первых, вам нужно хорошо понять проблему и какой подход вы пытаетесь ее решить.
  • Эти шаблоны созданы для того, чтобы вы прошли любое собеседование по кодированию.

Обзор нотации Big-O

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

Введение в сложность времени - большой O

Константа - O (1)

Линейный - O (n)

Логарифмический - O (войти n)

Квадратичный - O (n²)

Экспоненциальная - O (2 ^ n)

Цвета показывают, насколько хороши временные сложности, если вы не знакомы с нотацией Big-O. Нет, проблема, взгляните на это https://medium.com/@nagamalliaditya3/big-o-notation-what-is-time-complexity-and-space-complexity-87631add1746?source=your_.

Давайте углубимся в тему "Шаблоны"

1. скользящее окно

Введение: шаблон "Скользящее окно" используется для выполнения требуемой операции с определенным размером окна данного массива или связанного списка.

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

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

Например. Проблем:

  • Подмассив максимальной суммы размера K
  • Наименьший подмассив с заданной суммой
  • Самая длинная подстрока с k разными символами
  • Фрукты в корзинах
  • Подстрока без повтора
  • Самая длинная подстрока с такими же буквами после замены
  • Самый длинный подмассив с единицами после замены

2. Два указателя или итератора

Введение: два указателя - это шаблон, в котором два указателя проходят по структуре данных в тандеме до тех пор, пока один или оба указателя не достигнут определенного условия. Два указателя часто полезны при поиске пар в отсортированном массиве или связанных список.

Определите проблему:

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

Например. Проблем:

  • Пара с целевой суммой
  • Возведение в квадрат отсортированного массива
  • Удалить дубликаты.
  • Сравнение строк, содержащих пробелы
  • Сумма триплетов до нуля
  • Сумма триплетов близка к цели
  • Тройняшки с меньшей суммой
  • Подмассивы с продуктом меньше целевого
  • Голландский национальный флаг

3.Быстрый и медленный указатели

Введение. Метод быстрых и медленных указателей, также известный как алгоритм Зайца и Черепахи, представляет собой алгоритм указателя, который использует два указателя, которые перемещаются по массиву (или последовательности / связанному списку) с разной скоростью.

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

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

Определите проблему:

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

Например. Проблем:

  • Цикл связанного списка
  • Середина связанного списка
  • Начало цикла связанного списка
  • Счастливый номер
  • Связанный список палиндрома
  • Цикл в круговом массиве

4. Интервалы слияния

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

Определите проблему:

  • Если вы слышите термин «перекрывающиеся интервалы».

Например. Проблем:

  • Интервалы слияния
  • Вставить интервалы
  • Интервалы Пересечение
  • Конфликтующие встречи
  • Максимальная загрузка процессора

5.Циклическая сортировка

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

Определите проблему:

  • Возникнут проблемы с отсортированным массивом с числами в заданном диапазоне.
  • Проблема просит вас найти недостающее / повторяющееся / наименьшее число в заданном диапазоне.

Например. Проблем:

  • Циклическая сортировка
  • Найдите недостающий номер
  • Найдите все недостающие числа
  • Найдите повторяющиеся числа

6. сторнирование связанного списка на месте

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

Определите проблему:

  • Обратить связанный список без использования дополнительной памяти

Например. Проблем:

  • Отменить связанный список
  • Перевернуть подсписок
  • Обратить каждый подсписок K-Element

7. поиск в ширину дерева

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

Определите проблему:

  • Обходите дерево поэтапно (или обходя порядок уровней).

Например. Проблем:

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

8 поиск по дереву в глубину

Введение: Tree DFS основан на методе поиска в глубину (DFS) для обхода дерева.

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

Определите проблему:

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

Например. Проблем:

  • Сумма пути двоичного дерева
  • Все Пути за сумму
  • Сумма номеров путей
  • Путь с заданной последовательностью
  • Подсчитайте пути на определенную сумму.

9. Две кучи

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

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

Определите проблему:

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

Например. Проблем:

  • Найдите медиану числового потока
  • Раздвижное окно по средине
  • Максимизировать капитал

10. Подмножества

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

Определите проблему:

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

Например. Проблем:

  • Подмножества
  • Подмножества с дубликатами
  • Перестановки
  • Перестановки строк изменением регистра
  • Сбалансированные круглые скобки
  • Уникальные обобщенные сокращения.

11. Модифицированный двоичный поиск

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

Этот шаблон описывает эффективный способ решения всех проблем, связанных с двоичным поиском.

Определите проблему:

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

Например. Проблем:

  • Бинарный поиск без привязки к порядку
  • Потолок номера
  • Следующее письмо
  • Поиск по номеру
  • Поиск в отсортированном бесконечном массиве
  • Элемент минимальной разницы
  • Максимум битонического массива

12.Верхние элементы "K"

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

Лучшая структура данных для отслеживания элементов «K» - это куча. Этот шаблон будет использовать кучу для решения нескольких проблем, связанных с элементами «K» из набора заданных элементов.

Выглядит выкройка так:

  1. Вставьте элементы «K» в min-heap или max-heap в зависимости от проблемы.
  2. Переберите оставшиеся числа, и если вы найдете одно, которое больше, чем то, что у вас есть в куче, удалите это число и вставьте большее.

Определите проблему:

  • Найдите самые популярные / самые маленькие / частые «K» элементов данного набора.
  • Если вас попросят отсортировать массив, чтобы найти точный элемент.

Например. Проблем:

  • Лучшие числа "K"
  • K-е наименьшее число
  • ‘K’ Ближайшие точки к исходной точке
  • Соединить веревки
  • Самые частые номера "K"
  • Сортировка по частоте
  • K-е наибольшее число в потоке
  • K Ближайшие номера
  • Максимум отчетливых элементов
  • Сумма элементов
  • Переставить строку

13. K-way слияние

Введение: K-way Merge помогает решать проблемы, связанные с набором отсортированных массивов.

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

Схема выглядит так:

  1. Вставьте первый элемент каждого массива в минимальную кучу.
  2. После этого выньте из кучи самый маленький (верхний) элемент и добавьте его в объединенный список.
  3. После удаления самого маленького элемента из кучи вставьте в кучу следующий элемент того же списка.
  4. Повторите шаги 2 и 3, чтобы заполнить объединенный список в отсортированном порядке.

Определите проблему:

  • В задаче будут отсортированные массивы, списки или матрица.
  • Если проблема требует объединить отсортированные списки, найдите наименьший элемент в отсортированном списке.

Например. Проблем:

  • Объединить K отсортированных списков
  • K-е наименьшее число в M отсортированных списках
  • K-е наименьшее число в отсортированной матрице.
  • Наименьший диапазон чисел.

14. Топологическая сортировка

Введение: топологическая сортировка используется для определения линейного порядка элементов, которые зависят друг от друга. Например, Если событие «B» зависит от события «A», «A» стоит перед «B» в топологическом порядке.

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

Этот шаблон работает следующим образом:

  1. Инициализация

я. Сохраните график в списках смежности с помощью HashMap.

II. Чтобы найти все источники, используйте HashMap, чтобы вести подсчет внутренних градусов. Постройте граф и найдите внутренние степени всех вершин.

2. Постройте график на основе входных данных и заполните HashMap в градусах.

3. найти все источники

я. Все вершины с «0» в градусах будут исходными и хранятся в очереди.

4. сортировка

а. Для каждого источника выполните следующие действия:

i) Добавьте его в отсортированный список.

ii) Получить всех его дочерних элементов из графа.

iii) Уменьшите внутреннюю степень каждого ребенка на 1.

iv) Если дочерний элемент в градусах становится «0», добавьте его в Очередь источников.

  1. Повторяйте (i), пока исходная очередь не станет пустой.

Определите проблему:

  • Задача будет иметь дело с графами, не имеющими ориентированных циклов.
  • Если вас попросят обновить все объекты в отсортированном порядке.
  • Если у вас есть класс объектов, которые следуют определенному порядку

Например. Проблем:

  • Топологическая сортировка
  • Планирование задач
  • Порядок планирования задач
  • Все задачи Планирование заказов
  • Словарь инопланетян

ПРИМЕЧАНИЕ IMP: «Большая часть содержания этой статьи собрана только из Интернета. Я не единственный, кто имеет право на получение этого кредита. Большинство умных и опытных людей будут работать над этим еще до того, как я и я собрали некоторые данные из открытых источников и опубликовали в своей статье ».

ПРИМЕЧАНИЕ. Кодирование - это не копирование и вставка некоторых данных. Кодирование - это логическое мышление, если вы хотите быть профессионалом в кодировании. Вы должны знать эти основы, а также структуры данных и алгоритмы. Узнать ›› Применить ›› Поделиться этими тремя следует в циклическом цикле.

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