Статьи
Утилиты Telegram YouTube Отзывы

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

Алгоритм поиска суммы двух элементов в массиве

20 мая 2024

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

На собеседованиях и на leetcode можно встретить такую алгоритмическую задачу. Дан неупорядоченный массив целых чисел. Нужно найти все пары чисел, сумма которых равна указанной. Числа в массиве могут быть как положительными, так и отрицательными. В качестве результата нужно вернуть порядковые индексы найденных элементов.

Например, если дан массив [2, 7, 11, 15] и целевая сумма равна 9, то правильным ответом будут индексы 0 и 1 (то есть первый и второй элементы массива), т.к. 2 + 7 = 9.

Алгоритм поиска суммы двух элементов в массиве

Рассмотрим несколько вариантов реализации этого алгоритма.

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

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

25 марта 2024

Тэги: алгоритмы, 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.

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

Перебор элементов через Iterator

11 февраля 2024

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

Интерфейсы Iterator и Iterable часто используются для работы с коллекциями в Java. Они позволяют эффективно и безопасно работать с коллекциями, обеспечивая контроль над процессом перебора элементов (итерации).

Интерфейс Iterator

Паттерн Итератор

Интерфейс Iterator представляет собой одноимённый шаблон проектирования «Итератор» и содержит несколько методов. Нас интересуют два из них:

interface Iterator<E> {

    boolean hasNext();

    E next();
}
  1. Метод hasNext(), который возвращает true при наличии следующего элемента.
  2. Метод next(), который сдвигает указатель итератора на следующий элемент и возвращает этот элемент в качестве результата. Если доступных элементов не осталось – метод кидает исключение NoSuchElementException.

Пример использования интерфейса Iterator:

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

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

10 февраля 2024

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

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

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

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

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

SequencedCollection и SequencedSet

3 ноября 2023

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

SequencedCollection

В Java 21 появилась новая группа интерфейсов коллекций, самым основным из которых является SequencedCollection. Он расширяет базовый интерфейс Collection, добавляя в него ряд полезных методов для манипуляций с первым и последним элементами, а также для инвертирования коллекции:

interface SequencedCollection<E> extends Collection<E> {
    void addFirst(E e);
    void addLast(E e);
    E getFirst();
    E getLast();
    E removeFirst();
    E removeLast();
    SequencedCollection<E> reversed();
}

Две основных реализации интерфейса List (ArrayList и LinkedList) также поддерживают этот интерфейс.

Иерархия интерфейсов и классов SequencedCollection
Читать полностью...

Алгоритм инверсии двусвязного списка

8 мая 2023

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

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

Структура элемента

Класс Node, представляющий собой один элемент списка, выглядит следующим образом:

class Node {
    int value;
    Node next; // всегда null у последнего элемента
    Node prev; // всегда null у первого элемента

    Node(int value) {
        this.value = value;
        this.next = null;
        this.prev = null;
    }
}
Читать полностью...

Алгоритм записи римских цифр

17 апреля 2023

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

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

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

Вычисление арифметических выражений

5 марта 2023

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

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


" 20 * (10 - 5) "

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

Обработку такого выражения можно разделить на три основных этапа:

  1. Разбиение строки на отдельные части
  2. Обработка этих частей с учётом математических операций
  3. Само вычисление

Разберём каждую из этих частей подробнее.

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

Системы счисления

26 февраля 2023

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

Что такое системы счисления

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

Иными словами, как записать любое сколь угодно большое число, имея в арсенале всего 10 цифр-символов? Правильно, комбинируя эти цифры друг с другом. Причём расположение цифры в записи числа имеет значение, ибо 123 не равно 321. Хотя цифры используются одинаковые.

Десятичная система счисления

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

Обратите внимание, что любое число в десятичной записи можно разбить на слагаемые и степени числа 10. Например:

123 = 100 + 20 + 3 = 1*10^2 + 2*10^1 + 3*10^0
// символ ^ означает возведение в степень

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

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

Алгоритм инвертирования массива

22 февраля 2023

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

Давайте рассмотрим алгоритм инвертирования массива. На вход нам подаётся массив произвольной длины и нужно поменять порядок следования его элементов на обратный. То есть сделать первый элемент последним, второй – предпоследним и т.д.

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

public void invertArray(int[] array) {
    for (int i = 0; i < array.length / 2; i++) {
        int temp = array[i];
        array[i] = array[array.length - i - 1];
        array[array.length - i - 1] = temp;
    }
}

Метод invertArray() получает исходный массив в качестве параметра. Затем в цикле проходим по первой половине элементов и на каждой итерации меняем местами элемент с индексом i и элемент с таким же смещением, но с конца массива (array.length – i – 1). Чтобы обменять значения местами мы используем временную переменную.

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

Далее ❯