Перейти к основному содержимому

Установить операции в Java

· 6 мин. чтения

Задача: Наибольшая подстрока без повторений

Для заданной строки s, найдите длину наибольшей подстроки без повторяющихся символов. Подстрока — это непрерывная непустая последовательность символов внутри строки...

ANDROMEDA 42

1. Введение

Набор — это удобный способ представить уникальную коллекцию предметов.

В этом руководстве мы узнаем больше о том, что это значит и как мы можем использовать его в Java.

2. Немного теории множеств

2.1. Что такое набор?

Набор — это просто набор уникальных вещей. Итак, существенной характеристикой любого набора является то, что он не содержит дубликатов .

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

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

setA : {1, 2, 3, 4}

setB : {2, 4, 6, 8}

Мы можем показать наборы в виде диаграммы, просто поместив значения в круги:

./9874c2945a422008b78fd77595d09214.png

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

2.2. Пересечение множеств

Термин пересечение означает общие значения различных наборов .

Мы видим, что целые числа 2 и 4 существуют в обоих множествах. Таким образом, пересечение setA и setB равно 2 и 4, потому что это значения, общие для обоих наших наборов.

setA intersection setB = {2, 4}

Чтобы показать пересечение на диаграмме, мы объединяем два наших набора и выделяем область, общую для обоих наших наборов:

./7e58267c161e0e6cb5f86d21058dc011.png

2.3. Союз наборов

Термин объединение означает объединение значений различных наборов .

Итак, давайте создадим новый набор, который будет объединением наших наборов примеров. Мы уже знаем, что в наборе не может быть повторяющихся значений. Однако в наших наборах есть несколько повторяющихся значений (2 и 4). Поэтому, когда мы объединяем содержимое обоих наборов, нам нужно убедиться, что мы удалили дубликаты. Таким образом, мы получаем 1, 2, 3, 4, 6 и 8.

setA union setB = {1, 2, 3, 4, 6, 8}

Снова мы можем показать объединение на диаграмме. Итак, давайте объединим наши два набора и выделим область, представляющую объединение:

./9b9e8f4cc7955898b41ce51c7fea293f.png

2.4. Относительное дополнение множеств

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

Теперь давайте создадим новые наборы, которые являются относительными дополнениями setA и setB .

relative complement of setA in setB = {6, 8}

relative complement of setB in setA = {1, 3}

А теперь давайте выделим область в setA , которая не является частью setB . Это дает нам относительное дополнение setB в setA :

./6b1facb6e09688f2893bf5a2ad14795b.png

2.5. Подмножество и надмножество

Подмножество — это просто часть большего множества, а большее множество называется надмножеством. Когда у нас есть подмножество и надмножество, их объединение равно надмножеству, а пересечение равно подмножеству.

3. Реализация операций над множествами с помощью java.util.Set

Чтобы увидеть, как мы выполняем операции над множествами в Java, мы возьмем наборы примеров и реализуем пересечение, объединение и относительное дополнение. Итак, давайте начнем с создания наших образцов наборов целых чисел:

private Set<Integer> setA = setOf(1,2,3,4);
private Set<Integer> setB = setOf(2,4,6,8);

private static Set<Integer> setOf(Integer... values) {
return new HashSet<Integer>(Arrays.asList(values));
}

3.1. Перекресток

Во-первых, мы собираемся использовать метод continueAll , чтобы создать пересечение наших выборочных наборов . Поскольку continueAll изменяет набор напрямую, мы создадим копию setA с именем intersectSet. Затем мы будем использовать метод continueAll , чтобы сохранить значения, которые также находятся в setB :

Set<Integer> intersectSet = new HashSet<>(setA);
intersectSet.retainAll(setB);
assertEquals(setOf(2,4), intersectSet);

3.2. Союз

Теперь воспользуемся методом addAll для создания объединения наших выборочных наборов . Метод addAll добавляет все элементы предоставленного набора в другой. Опять же, поскольку addAll напрямую обновляет набор, мы создадим копию setA с именем unionSet , а затем добавим к ней setB :

Set<Integer> unionSet = new HashSet<>(setA);
unionSet.addAll(setB);
assertEquals(setOf(1,2,3,4,6,8), unionSet);

3.3. Относительное дополнение

Наконец, мы будем использовать метод removeAll для создания относительного дополнения setB в setA . Мы знаем, что нам нужны значения из setA , которых нет в setB . Итак, нам просто нужно удалить все элементы из setA , которые также находятся в setB :

Set<Integer> differenceSet = new HashSet<>(setA);
differenceSet.removeAll(setB);
assertEquals(setOf(1,3), differenceSet);

4. Реализация операций над множествами с помощью Stream s

4.1. Перекресток

Создадим пересечение наших наборов с помощью Streams .

Во-первых, мы получим значения из setA в поток. Затем мы отфильтруем поток, чтобы сохранить все значения, которые также находятся в setB . И, наконец, мы соберем результаты в новый Set :

Set<Integer> intersectSet = setA.stream()
.filter(setB::contains)
.collect(Collectors.toSet());
assertEquals(setOf(2,4), intersectSet);

4.2. Союз

Теперь воспользуемся статическим методом Streams.concat , чтобы добавить значения наших наборов в один поток .

Чтобы получить объединение из конкатенации наших наборов, нам нужно удалить все дубликаты. Мы сделаем это, просто собрав результаты в Set :

Set<Integer> unionSet = Stream.concat(setA.stream(), setB.stream())
.collect(Collectors.toSet());
assertEquals(setOf(1,2,3,4,6,8), unionSet);

4.3. Относительное дополнение

Наконец, мы создадим относительное дополнение setB в setA .

Как и в примере с пересечением, мы сначала получим значения из setA в поток. На этот раз мы отфильтруем поток, чтобы удалить любые значения, которые также находятся в setB . Затем мы соберем результаты в новый Set :

Set<Integer> differenceSet = setA.stream()
.filter(val -> !setB.contains(val))
.collect(Collectors.toSet());
assertEquals(setOf(1,3), differenceSet);

5. Вспомогательные библиотеки для операций над множествами

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

5.1. Зависимости

Чтобы использовать SetUtils наборов Guava и коллекций Apache Commons , нам нужно добавить их зависимости:

<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>31.0.1-jre</version>
</dependency>
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-collections4</artifactId>
<version>4.3</version>
</dependency>

5.2. Наборы гуавы

Давайте воспользуемся классом Guava Sets для выполнения пересечения и объединения наших наборов примеров. Для этого мы можем просто использовать объединение и пересечение статических методов класса Sets :

Set<Integer> intersectSet = Sets.intersection(setA, setB);
assertEquals(setOf(2,4), intersectSet);

Set<Integer> unionSet = Sets.union(setA, setB);
assertEquals(setOf(1,2,3,4,6,8), unionSet);

Взгляните на нашу статью о наборах гуавы , чтобы узнать больше.

5.3. Коллекции Apache Commons

Теперь давайте воспользуемся статическими методами пересечения и объединения класса SetUtils из коллекций Apache Commons:

Set<Integer> intersectSet = SetUtils.intersection(setA, setB);
assertEquals(setOf(2,4), intersectSet);

Set<Integer> unionSet = SetUtils.union(setA, setB);
assertEquals(setOf(1,2,3,4,6,8), unionSet);

Взгляните на наше руководство по SetUtils Apache Commons Collections `` , чтобы узнать больше.

6. Заключение

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

Все примеры кода можно найти на GitHub .