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

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

Алгоритм определения палиндрома

8 июля 2022

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

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

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

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

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

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

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

Решето Эратосфена для поиска простых чисел

17 июня 2022

Тэги: Java, Collections, алгоритмы, головоломки, руководство, YouTube.

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

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

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

16 июня 2022

Тэги: 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 (var i = 3; primes.size() < count; i += 2) {
        if (isPrime(i, primes)) {
            primes.add(i);
        }
    }
    return primes;
}

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

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

Алгоритм чисел Фибоначчи на Java и Kotlin

6 мая 2022

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

Немного теории

На собеседованиях по алгоритмам любят давать такую задачку, как нахождение чисел из последовательности Фибоначчи. Эта числовая последовательность названа в честь Леонардо Пизанского - известного математика Средневековья.

Сама последовательность довольно проста. Она состоит из целых положительных чисел, где каждый следующий элемент равен сумме двух предыдущих. Например, 2 = 1 + 1, 3 = 2 + 1, 5 = 3 + 2.

Последовательность начинается с 0 и 1:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...

Иногда в этой последовательности принято пропускать 0 и начинать её с двух единиц, однако официально она начинается именно с 0.

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

Бинарный поиск на отсортированном массиве

11 апреля 2022

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

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

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

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

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

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(), который позволяет «выравнивать» любую переданную ему дату (или дату со временем) по определённому правилу. В нашем случае дата будет выровнена по последнему дню месяца.

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

Далее ❯