Статьи
YouTube-канал

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

Пузырьковая сортировка

4 апреля 2021

Тэги: Java 11 алгоритмы Kotlin

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

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

Читать полностью...

Подсчёт количества строк в текстовом файле

23 марта 2021

Тэги: Java 11 Java алгоритмы ввод-вывод

Во многих редакторах при работе с текстовым документом вы можете видеть, сколько всего строк содержится в этом файле. Строки между собой разделяются символом перевода строки, который в каждой операционной системе (Windows, Unix, Mac) свой.

Давайте разберёмся, как быстро подсчитать количество строк в текстовом файле независимо от той ОС, в котором выполняется наш код. Более того, текстовый файл может быть сколь угодно большим, поэтому мы будем использовать буферизацию потока, чтобы не израсходовать всю доступную оперативную память.

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

Читать полностью...

Проверка вложенности скобок

22 марта 2021

Тэги: Java алгоритмы головоломки Java 8

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

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

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

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

Читать полностью...

Вычисление контрольной суммы файла

21 марта 2021

Тэги: Java 11 алгоритмы Java ввод-вывод

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

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

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

Читать полностью...

Как получить последний день месяца

30 сентября 2020

Тэги: Java Java 8 Kotlin алгоритмы

При работе с датами часто бывает нужно получить последний день текущего месяца или года. Поскольку последний день года всегда равен 31 декабря, то мы можем напрямую создать эту дату с помощью метода LocalDate.of(). А вот последний день месяца зависит от конкретного месяца. Дней в месяце может быть 30 или 31, а для февраля и вовсе 28 или 29.

Чтобы не разбираться в логике работы календаря, начиная с Java 8 (а, значит, и в Kotlin) нам доступен специальный класс TemporalAdjusters. Он имеет несколько полезных методов, но в данном случае нас интересует lastDayOfMonth(), возвращающий специальный объект с интерфейсом TemporalAdjuster. Этот интерфейс содержит метод adjustInto(), который позволяет «выравнивать» любую переданную ему дату (или дату со временем) по определённому правилу. В нашем случае дата будет выровнена по последнему дню месяца.

Читать полностью...

Вычисление MD5-хэша

13 февраля 2020

Тэги: Java 10 алгоритмы Spring

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

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

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

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

Читать полностью...

Вычисление размера директории

25 января 2020

Тэги: Java 8 алгоритмы Stream API ввод-вывод

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

public long getFolderSize(String path) throws IOException {
    Path folder = Paths.get(path);
    return Files.walk(folder)
            .map(Path::toFile)
            .filter(File::isFile)
            .mapToLong(File::length)
            .sum();
}

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

Читать полностью...

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

23 января 2020

Тэги: Java 10 алгоритмы Java

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

var random = new SecureRandom();
var list = Arrays.asList("апельсин", "лимон", "грейпфрут");
var randomElement = list.get(random.nextInt(list.size()));
System.out.println(randomElement);

Сначала создадим генератор случайных значений SecureRandom. Можно также использовать и обычный Random, но первый выдаёт более случайные значения.

Читать полностью...

Алгоритм поиска простых чисел

7 мая 2019

Тэги: Java алгоритмы

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

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

public List<Integer> getFirstPrimes(int count) {
    List<Integer> primes = new ArrayList<>();
    if (count > 0) {
        primes.add(2);
    }
    for (int i = 3; primes.size() < count; i += 2) {
        if (isPrime(i, primes)) {
            primes.add(i);
        }
    }
    return primes;
}

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

Читать полностью...

Как обменять значения двух переменных без буфера

1 мая 2018

Тэги: головоломки Java алгоритмы

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

int buffer = a;
a = b;
b = buffer;

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

А что, если нам нужно обменять значения числовых переменных между собой, не создавая новых переменных?

Читать полностью...