Статьи с тэгом «алгоритмы»

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

Одно слово является анаграммой другого, если второе слово получается из первого путём перестановки букв. Например, слово «фара» является анаграммой слова «арфа». Также «комар» является анаграммой слова «корма».

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

Давайте реализуем алгоритм поиска слов-палиндромов на Java.

Что такое палиндром

Для начала надо определиться, что же такое палиндром? Палиндром – это слово или строка текста, которая читается слева направо и справа налево одинаково. Например, палиндромами являются такие слова как «ага», «дед», «довод», «кабак», «мадам», «шалаш». В более широком смысле число «101» также является палиндромом.

Проверка слова

Давайте сначала рассмотрим более простой алгоритм, который на вход получает одно слово без пробелов. В случае, если данное слово палиндром – возвращаем true.

Ранее я уже приводил Алгоритм поиска простых чисел методом перебора делителей. Эта реализация хороша, если вам нужно ровно N первых простых чисел. Но если вы ищете простые числа в некотором диапазоне (скажем, не превосходящие 1 000 000), то лучше воспользоваться более быстрым алгоритмом, который называется «решето Эратосфена».

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

Рассмотрим алгоритм поиска простых чисел, известный как «метод перебора делителей». Для этого давайте реализуем на Java метод getFirstPrimes(), который будет возвращать N первых простых чисел.

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

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

Суть бинарного поиска можно описать как «разделяй и властвуй». Исходный отсортированный по порядку массив мы делим пополам и проверяем элемент посередине. Если он равен тому, который мы ищем, то возвращаем его индекс. Если не равен, то проверяем границы и выбираем ту половину, в которой искомый элемент может находиться и выполняем проверку снова. Так мы сужаем область поиска до тех пор, пока левая граница не станет равна правой. Если элемент не удалось найти, возвращаем -1.

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

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

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

Зачем нужно проверять вложенность скобок

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

Первое, что приходит в голову, это подсчитать количество открывающих и количество закрывающих скобок в строке и если эти числа равны, то считать, что последовательность скобок правильная. Возможно, это и будет работать в самых простых случаях, однако последовательность «(())» будет правильной, а последовательность «())(» – неправильной. При этом количество открывающих и закрывающих скобок у них одинаковы. Кроме того, скобки могут быть разных типов (круглая, фигурная, квадратная и т.п.) и скобки должны соответствовать ещё и по типу. Поэтому в основе такой проверки должна лежать работа со стеком.

Контрольная сумма от набора байт позволяет убедиться в том, что данные на клиенте, полученные от сервера, являются корректными. Для этого вместе с файлом сервер может предоставлять контрольную сумму для проверки на клиентской стороне. Существует несколько алгоритмов вычисления контрольной суммы, рассмотрим самые популярные: md5, sha-256, sha-512 и crc-32.

Вычисление md5 с помощью MessageDigest

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

MD5 хэш (Message Digest 5) – это 128 битный алгоритм вычисления хэша от сообщения произвольной длины. Чаще всего хэш вычисляется от строки (для проверки паролей) и от файла (для контроля его целостности).

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

Вычисление хэша от строки

Алгоритм хэширования MD5 является частью стандартной библиотеки Java, поэтому вычислить хэш от строки (например, от пароля) достаточно легко.

При работе с файловой системой может потребоваться вычислить размер папки (folder) с лежащими в ней файлами. Как известно, директория – это лишь логический раздел на файловой системе, поэтому её размер равняется сумме размеров всех файлов, находящихся внутри неё. При этом нужно пройтись по всей иерархии файлов и папок, находящихся внутри.

Сначала создадим объект папки с помощью метода Paths.get(). В него передадим полный путь до интересующей нас папки. Этот путь мы получаем в качестве параметра нашего метода.