В этом кратком руководстве мы узнаем, как мы можем обнаружить цикл в заданном ориентированном графе.
В этом руководстве мы будем придерживаться графа списка смежности .
Во-первых, давайте начнем с определения вершины в Java:
В этом руководстве мы увидим, как работает сортировка кучей, и реализуем ее на Java.
Сортировка кучей основана на структуре данных кучи. Чтобы правильно понять сортировку кучи, мы сначала рассмотрим кучи и то, как они реализованы.
Куча — это специализированная древовидная структура данных . Поэтому он состоит из узлов. Мы присваиваем элементы узлам: каждый узел содержит ровно один элемент.
В этом руководстве мы объясним, как работает алгоритм сортировки на месте.
Алгоритмы на месте — это те алгоритмы, которые не нуждаются в какой-либо вспомогательной структуре данных для преобразования входных данных. По сути, это означает, что алгоритм не использует дополнительное пространство для обработки ввода. Он практически переопределяет ввод с выводом.
Однако на самом деле алгоритм может потребовать небольшого и непостоянного дополнительного пространства для вспомогательных переменных. Сложность этого пространства в большинстве случаев O(log n) , хотя иногда допускается что-то меньшее, чем линейное.
В этом уроке мы обсудим алгоритм сортировки вставками и рассмотрим его реализацию на Java .
Сортировка вставками — это эффективный алгоритм для упорядочения небольшого количества элементов. Этот метод основан на том, как карточные игроки сортируют карты.
Начинаем с пустой левой рукой и картами, выложенными на стол. Затем мы убираем одну карту со стола и вставляем ее в правильное положение в левой руке. Чтобы найти правильную позицию для новой карты, мы сравниваем ее с уже отсортированным набором карт в руке, справа налево.
Давайте начнем с понимания шагов алгоритма в форме псевдокода.
В этом уроке мы рассмотрим алгоритмы интерполяционного поиска и обсудим их плюсы и минусы. Кроме того, мы реализуем его на Java и поговорим о временной сложности алгоритма.
Поиск с интерполяцией — это усовершенствование бинарного поиска , предназначенное для равномерно распределенных данных.
Двоичный поиск разделяет пространство поиска на каждом шаге независимо от распределения данных, поэтому его временная сложность всегда равна O(log(n)) .
В этой статье мы представим различные решения для нахождения k -го по величине элемента в последовательности уникальных чисел. Мы будем использовать массив целых чисел для наших примеров.
Мы также поговорим о средней и наихудшей временной сложности каждого алгоритма.
Теперь давайте рассмотрим несколько возможных решений — одно с использованием простой сортировки и два с использованием алгоритма быстрого выбора, полученного из быстрой сортировки.
Односвязный список — это последовательность соединенных узлов, оканчивающаяся нулевой ссылкой. Однако в некоторых сценариях последний узел может указывать на предыдущий узел, что фактически создает цикл.
В большинстве случаев мы хотим иметь возможность обнаруживать и знать об этих циклах; эта статья будет посвящена именно этому — обнаружению и потенциальному удалению циклов.
Давайте теперь рассмотрим пару алгоритмов обнаружения циклов в связанных списках .
В этом руководстве мы объясним, как найти средний элемент связанного списка в Java.
В следующих разделах мы представим основные проблемы и покажем различные подходы к их решению.
Эту проблему можно легко решить, просто отслеживая размер при добавлении новых элементов в список . Если мы знаем размер, мы также знаем, где находится средний элемент, поэтому решение тривиально.
В этом руководстве сравните способы поиска самой длинной подстроки уникальных букв с помощью Java. Например, самая длинная подстрока уникальных букв в «CODINGISAWESOME» — «NGISAWE».
Начнем с наивного подхода. Для начала мы можем проверить каждую подстроку на наличие уникальных символов:
String getUniqueCharacterSubstringBruteForce(String input) {
String output = "";
for (int start = 0; start < input.length(); start++) {
Set<Character> visited = new HashSet<>();
int end = start;
for (; end < input.length(); end++) {
char currChar = input.charAt(end);
if (visited.contains(currChar)) {
break;
} else {
visited.add(currChar);
}
}
if (output.length() < end - start + 1) {
output = input.substring(start, end);
}
}
return output;
}