Круговой сдвиг вправо

Круговой сдвиг (или циклический сдвиг) — это операция, которая смещает элементы массива или строки влево или вправо, перенося крайние элементы на противоположный конец.

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

Ближайшая пара точек с использованием алгоритма «Разделяй и властвуй»

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

Алгоритм:
1. Найдите среднюю точку, которая равна P[n/2].
2. Разделите массив на две половины: от P[0] до P[n/2] и от P[n/2+1] до P[n-1].
3. Рекурсивно находим минимальные расстояния в обеих половинах, получая dl и dr.
4. Пусть d будет минимумом dl и dr.
5. Создайте массив «полосы», содержащий точки ближе, чем d к средней вертикальной линии, и отсортируйте его по координатам y.
6. Найдите наименьшее расстояние в массиве полос, рассматривая не более 7 точек после каждой точки.
7. Верните минимум d и расстояние, найденное на шаге 6, как ближайшую пару точек.

Сложность: O(n (Logn)^2)

Проверить, находится ли данная точка внутри или снаружи многоугольника?

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

Сложность: O(N)

Как проверить, лежит ли точка внутри заданных N точек выпуклого многоугольника?

Алгоритм:

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

2. Установите нижнюю левую точку в качестве начальной точки, а верхнюю правую точку в качестве конечной точки.

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

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

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

6. Если точка не существует в векторе, то точка лежит внутри выпуклой оболочки.

Сложность: O(N * log(N))

Выпуклая оболочка с использованием алгоритма Грэхема

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

Алгоритм:

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

2. Отсортируйте оставшиеся n-1 точек по углам вокруг P0 против часовой стрелки. Если углы одинаковы, сначала отдайте приоритет ближайшей точке.

3. Удалите точки с одинаковым углом, оставив только самую дальнюю от P0. Пусть размер нового массива будет m.

4. Если m меньше 3, верните «Выпуклая оболочка невозможна».

5. Создайте пустой стек «S» и поместите первые три точки в «S».

6. Обрабатываем оставшиеся m-3 точки одну за другой. Для каждой точки:
⁃ Пока ориентация двух верхних точек в стеке и «points[i]» не против часовой стрелки, извлекайте точки из стека
⁃ Положите «points[i]» в «S».

7. Стек «S» теперь содержит точки выпуклой оболочки.

Сложность: O(nLogn)

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

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

Алгоритм:
1. Сначала отсортируйте заданные точки по их полярным углам относительно опорной точки. Ориентиром может быть любая точка из набора.
2. Постройте путь: начиная с контрольной точки, посещайте точки в отсортированном порядке. Двигаясь от одной точки к другой, соединяйте их отрезками линий. Убедитесь, что путь не пересекает сам себя.
3. После посещения всех точек соедините последнюю точку с контрольной точкой, чтобы закрыть путь.

Сложность: O(n Log n), если мы используем алгоритм сортировки O(nLogn) для сортировки точек.

Проверка, пересекаются ли два заданных отрезка

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

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

Сложность: O(1)

Алгоритм рекурсивного лабиринта

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

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

Если мы обнаружим какой-либо тупик перед конечной точкой, нам придется вернуться назад и изменить направление. Направление движения — север, восток, запад и юг. Нам придется продолжать «двигаться и возвращаться», пока не достигнем финальной точки.

Ориентация 3-х упорядоченных точек

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

Ориентация упорядоченной тройки точек на плоскости может быть:
⁃ Против часовой стрелки: математически ориентация является против часовой стрелки, если векторное произведение векторов AB и BC положительно.
⁃ По часовой стрелке: математически ориентация по часовой стрелке, если векторное произведение векторов AB и BC отрицательно.
⁃ Коллинеарность: Если ориентация коллинеарна, это означает, что точки A, B и C находятся на одной прямой. Математически ориентация коллинеарна, если векторное произведение векторов AB и BC равно нулю.

Сложность определение ориентации точек: O(1)

Z-алгоритм

Алгоритм находит все вхождения шаблона в тексте.

Идея состоит в том, чтобы объединить шаблон и текст и создать строку «P$T», где P — это шаблон, $ — специальный символ, который не должен присутствовать в шаблоне и тексте, а T — это текст. Создайте массив Z для объединенной строки. В массиве Z, если значение Z в любой точке равно длине шаблона, то шаблон присутствует в этой точке.

Сложность: O(m + n), где длина текста равна n, а шаблона — m

Хеширование

— это процесс генерации выходных данных фиксированного размера из входных данных переменного размера с использованием математических формул, известных как хэш-функции.

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

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

Компоненты хеширования

В основном существует три компонента хеширования:

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

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

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

Хеш-функции, основанные на делении

Хэш-функция — это функция, которая преобразует заданный числовой или буквенно-цифровой ключ в небольшое практическое целочисленное значение. Сопоставленное целочисленное значение используется в качестве индекса в хеш-таблице.

Хеш-функции, основанные на делении, это самый простой и легкий метод генерации хеш-значения. Хэш-функция делит значение k на M, а затем использует полученный остаток.

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

Минусы:
⁃ Этот метод приводит к снижению производительности, поскольку последовательные ключи сопоставляются с последовательными значениями хеш-функции в хеш-таблице.
⁃ Иногда следует проявлять особую осторожность при выборе значения M.

Метод среднего квадрата для хеш-функции

Метод хеширования, который включает в себя два шага для вычисления хеш-значения:
1. Возведите в квадрат значение ключа k, т.е. k2.
2. Извлеките средние цифры r в качестве значения хеш-функции.

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

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

Метод складывания цифр для хеш-функции

Этот метод включает в себя два этапа:
1. Разделите ключ-значение k на несколько частей, то есть k1, k2, k3,….,kn, где каждая часть имеет одинаковое количество цифр, за исключением последней части, которая может иметь меньше цифр, чем другие части.
2. Добавьте отдельные части. Хэш-значение получается путем игнорирования последнего переноса, если таковой имеется.

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

Метод обработки коллизий — метод цепочек

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

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

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

Недостатки:
⁃ Некоторые части хеш-таблицы никогда не используются
⁃ Если цепочка становится длинной, то время поиска в худшем случае может стать O(n).
⁃ Использует дополнительное пространство для ссылок

Количество диагоналей в n-стороннем выпуклом многоугольнике

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

Количество диагоналей = (n * (n - 3)) / 2

Эта формула выведена из того факта, что в выпуклом многоугольнике с n сторонами каждая вершина может быть соединена с любой другой вершиной диагональю, за исключением самой себя, соседних с ней вершин и двух соседних с ними вершин. В результате из каждой вершины можно провести n — 3 диагонали. Однако вы должны разделить это на 2, чтобы не считать каждую диагональ дважды (поскольку, например, соединение вершины A с вершиной B — это то же самое, что соединение вершины B с вершиной A).

Задача о ходе коня

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

Алгоритм:
1. Создаем шахматную доску n x n, где n - размерность доски.
2. Инициализируем текущую позицию коня на доске.
3. Помечаем текущую позицию как посещенную.
4. Проверяем, есть ли еще непосещенные клетки на доске:
- Если все клетки посещены, то задача решена, и мы можем вернуть найденный маршрут.
- Если не все клетки посещены, переходим к следующему шагу.
5. Находим все возможные ходы коня из текущей позиции:
- Проверяем, что следующий ход находится в пределах доски и не был посещен.
6. Для каждого возможного хода коня:
- Передвигаем коня на следующий ход.
- Рекурсивно вызываем алгоритм для новой позиции коня.
- Если рекурсивный вызов вернул true (маршрут найден), то возвращаем true.
- Если рекурсивный вызов вернул false, отменяем текущий ход и ищем другие возможные ходы.

Сложность: O(8^n), где n - размерность доски.

Задача о сумме подмножеств

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

Для каждого элемента есть две возможности:
1. Включите текущий элемент в подмножество и повторите операцию для остальных элементов с оставшейся суммой.
2. Исключить текущий элемент из подмножества и повторить операцию для остальных элементов.
3. Наконец, если сумма становится равной 0, выведите элементы текущего подмножества.

Сложность: O(n^2)