Алгоритмы на Java

1. Данный проект представляет собой примеры реализации классических алгоритмов на языке Java таких как:

• сортировка массива
• backtracking
• бинарный поиск
• динамическое программирование
• жадный алгоритм

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

Виды представленных сортировок:

1. Пузырьковая
2. Блочная
3. Расческой
4. Подсчётом
5. Вставками
6. Слиянием
7. Две реализации быстрой сортировки: 1, 2
8. Выбором
9. Методом Шелла

Сравнение сортировок с java.util.Arrays.sort()

Первая строка соответствует отсортированному массиву Вторая строка соответствует массиву отсортированному в обратном порядке Третья строка соответствует массиву случайных чисел

Задачи с использованием алгоритма backtracking

1. Получить все возможные комбинации букв для переданного набора цифр. Каждой цифре соответствует набор букв в точности, как кнопочном мобильном телефоне
2. Получение уникальных комбинаций чисел из переданного массива
3. Получение всех возможных представлений массива после перестановок его элементов
4. Получение всех возможных правильных комбинаций открытых-закрытых скобок для заданного числа пар
5. Получение всех возможных комбинаций элементов массива с сохранением порядка следования и в неубывающем порядке значений
6. Получение комбинаций чисел на отрезке от 1 до заданного числа
7. Получение всех уникальных наборов чисел из переданного массива, сумма которых равна заданному числу
8. Получение всех возможных разбиений переданной строки на подстроки-палиндромы
9. Получение всех возможных комбинаций символов для данной строки с изменением регистра букв
10. Поиск всех возможных путей от начального узла до конечного в направленном ациклическом графе
11. Получение количества всех возможных уникальных комбинаций из букв переданной буквенной строки
12. Поиск переданного слова в матрице символов
13. Поиск количества красивых композиций
14. Разбиение целочисленного массива на k-подмножеств с равными суммами их значений

Задачи с использованием бинарного поиска

1. Поиск элемента в повёрнутом массиве, отсортированном в неубывающем порядке
2. Поиск первого и последнего индекса заданного элемента в отсортированном массиве
3. Поиск первого индекса элемента с заданным значением в отсортированном по возрастанию массиве
4. Определение является ли переданное число "идеальным квадратом"
5. Поиск k-го наименьшего элемента в матрице, в которой ряды и столбцы отсортированы в возрастающем порядке
6. Поиск уникального элемента в отсортированном по возрастанию массиве целых чисел, все остальные элементы которого дублированы
7. Поиск пикового элемента в целочисленной матрице
8. Определение содержится ли целевой элемент в матрице, ряды которой отсортированы в возрастающем порядке, а первый элемент следующего ряда всегда больше последнего элемента в предыдущем ряду

Задачи с использованием поиска в глубину

1. Поиск максимальной длины строки, образованной при конкатенации строк из переданного списка и содержащей только уникальные буквы
2. Поиск количества "островов" из единиц в бинарной матрице
3. Поиск количества "провинций" для заданной матрицы связей "городов"
4. Получение численных результатов соотношений двух параметров из строковых запросов
5. Сортировка целых чисел в лексикографическом порядке
6. Перемещение по целочисленному массиву неотрицательных чисел в соответствии с условиями
7. Получение максимальной суммы значений элементов, доступных для первого игрока
8. Поиск всех существующих путей выхода объекта за границы поля заданного размера
9. Получение индексов столбцов, из которых "выпадает мяч"
10. Получение максимальной длины последовательности элементов массива вида: a{i}, a{a{i}}, a{a{a{i}}},...
11. Поиск безопасных узлов направленного графа
12. Поиск пути с минимальным усилием
13. Поиск минимальной длины моста для соединения двух островов
14. Подсчёт времени необходимого на оповещение всех сотрудников компании
15. Проверка является ли неориентированный граф двудольным
16. Поиск узла во взвешенном ненаправленном графе с наименьшим числом достижимых соседних узлов, находящихся на расстоянии не превышающем пороговое
17. Поиск минимально возможного времени для обход дерева с целью сбора всех яблок в его узлах и возвращения в вершину

Задачи с использованием поиска в ширину

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

Задачи с использованием динамического программирования

1. Задачи размена суммы монетами заданных номиналов
2. Поиск различных комбинаций элементов массива уникальных целых чисел, сумма которых равна целевой
3. Получение количества квадратных подматриц, состоящих только из 1, в целочисленной матрице
4. Подсчёт минимального числа операций удаления символов из двух исходных строк, чтобы получить эквивалентные строки
5. Получение всех возможных калькуляций при различных комбинациях скобок в математическом выражении
6. Задачи о максимизации награбленной суммы при обходе домов домушником
7. Перемещение по элементам массива от нулевого к последнему в соответствии с условиями
8. Получение самого длинного делимого поднабора из целочисленного массива
9. Поиск максимальной длины общего подмножества символов двух строк
10. Поиск длины самой большой возрастающей последовательности чисел в переданном массиве
11. Поиск длины самой большой палиндромической подпоследовательности символов в строке
12. Поиск в бинарной символьной матрице максимальной площади квадрата, состоящего только из '1'
13. Поиск максимальной длины цепи отрезков
14. Поиск максимального по значению произведения элементов среди подмассивов исходного массива
15. Подсчёт минимальной стоимости билетов для покрытия всех дней для путешествий
16. Получение минимальной суммы падающего пути
17. Поиск количества хороших способов разбиения строки
18. Получение максимального набора бинарных строк из массива в соответствии с ограничениями на общее количество нулей и единиц
19. Определение возможности разбиения переданного массива положительных целых чисел на две части с равными суммами значений элементов
20. Определение является ли сумма элементов, доступная первому игроку больше или равной сумме элементов, доступной второму игроку
21. Получение количества строк заданной длины, состоящих из гласных отсортированных в лексико-графическом порядке
22. Получение целевой суммы различными комбинациями знаков для элементов исходного массива
23. Поиск минимальной суммы прохождения от головы до низа треугольного массива
24. Поиск минимального числа операций копирований-вставок для получения заданного числа исходного символа
25. Поиск n-го уродливого числа
26. Поиск количества уникальных путей, которыми робот, двигаясь из верхнего левого угла поля заданного размера, может достичь правого нижнего угла
27. Провера валидности скобок
28. Получение размера самой длинной качающейся подпоследовательности
29. Разбиение целочисленного массива на подмассивы, значение каждого элемента в которых будет равно максимальному значению в данном подмассиве
30. Определение максимального времени задержки при прохождении сигнала от заданного узла до всех остальных
31. Задачи подсчёта максимальной прибыли от покупки-продажи акций
32. Поиск минимальной цены полёта из одного города в другой с ограничением на количество транзитных городов
33. Набор нажатий кнопок мобильного телефона путём перемещения по ним шахматного коня
34. Определение наибольшего количества очков, которые может дать пара в массиве

Задачи с использованием жадного алгоритма

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

Задачи с использованием скользящего окна

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