Java | LeetCode

Задача: 688. Knight Probability in Chessboard Сложность: medium На шахматной доске размером n x n конь начинает в клетке (row, column) и пытается сделать ровно k ходов. Строки и столбцы нумеруются с 0, так что верхняя левая клетка — это (0, 0), а нижняя правая — (n - 1, n - 1). Шахматный конь имеет восемь возможных ходов, как показано ниже. Каждый ход — это два поля в кардинальном направлении, затем одно поле в ортогональном направлении. Каждый раз, когда конь делает ход, он случайным образом выбирает один из восьми возможных ходов (даже если этот ход выведет его за пределы шахматной доски) и перемещается туда. Конь продолжает двигаться, пока не сделает ровно k ходов или не выйдет за пределы доски. Верните вероятность того, что конь останется на доске после того, как он завершит свои ходы. Пример:

Input: n = 3, k = 2, row = 0, column = 0
Output: 0.06250
Explanation: There are two moves (to (1,2), (2,1)) that will keep the knight on the board.
From each of those positions, there are also two moves that will keep the knight on the board.
The total probability the knight stays on the board is 0.0625.

👨‍💻 Алгоритм: 1⃣Определите возможные направления для ходов коня в directions. Инициализируйте таблицу динамического программирования dp нулями. Установите dp[0][row][column] равным 1, что представляет начальную позицию коня. 2⃣Итерация по ходам от 1 до k. Итерация по строкам от 0 до n−1. Итерация по столбцам от 0 до n−1. Итерация по возможным направлениям: вычислите i' как i минус вертикальный компонент направления. Вычислите j' как j минус горизонтальный компонент направления. Проверьте, находятся ли i' и j' в диапазоне [0, n−1]. Если находятся, добавьте (1/8) * dp[moves−1][i'][j'] к dp[moves][i][j]. 3⃣Вычислите общую вероятность, суммируя все значения в dp[k]. Верните общую вероятность. 😎 Решение:

class Solution {
    public double knightProbability(int n, int k, int row, int column) {
        int[][] directions = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
        double[][][] dp = new double[k + 1][n][n];
        dp[0][row][column] = 1;

        for (int moves = 1; moves <= k; moves++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int[] direction : directions) {
                        int prevI = i - direction[0];
                        int prevJ = j - direction[1];
                        if (prevI >= 0 && prevI < n && prevJ >= 0 && prevJ < n) {
                            dp[moves][i][j] += dp[moves - 1][prevI][prevJ] / 8;
                        }
                    }
                }
            }
        }

        double totalProbability = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                totalProbability += dp[k][i][j];
            }
        }

        return totalProbability;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

Задача: 536. Construct Binary Tree from String Сложность: medium Вам нужно построить бинарное дерево из строки, состоящей из круглых скобок и целых чисел. Весь ввод представляет собой бинарное дерево. Он содержит целое число, за которым следуют ноль, одна или две пары круглых скобок. Целое число представляет значение корня, а пара круглых скобок содержит дочернее бинарное дерево с той же структурой. Вы всегда начинаете строить левый дочерний узел родителя сначала, если он существует. Пример:

Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]

👨‍💻 Алгоритм: 1⃣ Извлечение числа: Определите функцию getNumber, которая извлекает целое число из текущей строки, начиная с указанного индекса. Учтите знак числа, если он есть. 2⃣ Построение поддерева: Определите рекурсивную функцию str2treeInternal, которая принимает строку и текущий индекс в качестве входных данных и возвращает пару: узел TreeNode и следующий индекс для обработки. Внутри функции извлеките значение для корневого узла текущего поддерева, создайте узел, а затем рекурсивно постройте левое и правое поддеревья, если они существуют. 3⃣ Основная функция: Определите основную функцию str2tree, которая вызывает рекурсивную функцию str2treeInternal и возвращает построенное дерево. 😎 Решение:

class Solution {
    public TreeNode str2tree(String s) {
        return this.str2treeInternal(s, 0).getKey();
    }
    
    public Pair<Integer, Integer> getNumber(String s, int index) {
        
        boolean isNegative = false;
        
        if (s.charAt(index) == '-') {
            isNegative = true;
            index++;
        }
            
        int number = 0;
        while (index < s.length() && Character.isDigit(s.charAt(index))) {
            number = number * 10 + (s.charAt(index) - '0');
            index++;
        }
        
        return new Pair<Integer, Integer>(isNegative ? -number : number, index);
    } 
    
    public Pair<TreeNode, Integer> str2treeInternal(String s, int index) {
        
        if (index == s.length()) {
            return new Pair<TreeNode, Integer>(null, index);
        }
        
        Pair<Integer, Integer> numberData = this.getNumber(s, index);
        int value = numberData.getKey();
        index = numberData.getValue();
        
        TreeNode node = new TreeNode(value);
        Pair<TreeNode, Integer> data;
        
        if (index < s.length() && s.charAt(index) == '(') {
            data = this.str2treeInternal(s, index + 1);
            node.left = data.getKey();
            index = data.getValue();
        }
            
        if (node.left != null && index < s.length() && s.charAt(index) == '(') {
            data = this.str2treeInternal(s, index + 1);
            node.right = data.getKey();
            index = data.getValue();
        }
            
        return new Pair<TreeNode, Integer>(node, index < s.length() && s.charAt(index) == ')' ? index + 1 : index);
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 401. Binary Watch Сложность: easy Бинарные часы имеют 4 светодиода сверху для представления часов (0-11) и 6 светодиодов снизу для представления минут (0-59). Каждый светодиод представляет ноль или единицу, при этом младший разряд находится справа. Пример:

Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

👨‍💻 Алгоритм: 1⃣Генерация всех возможных комбинаций Переберите все возможные значения для часов и минут. Используйте битовые операции для подсчета количества единиц в бинарном представлении числа. 2⃣Проверка количества горящих светодиодов Для каждой комбинации проверьте, соответствует ли сумма единиц в бинарном представлении часов и минут заданному количеству горящих светодиодов. 3⃣Форматирование результата Если комбинация часов и минут соответствует условию, отформатируйте их в виде строки "часы:минуты" и добавьте в список результатов. 😎 Решение:

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> results = new ArrayList<>();
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
                    results.add(String.format("%d:%02d", h, m));
                }
            }
        }
        return results;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Вчера QA.GURU анонсировали вебинар с Head of QA в Dodo Engineering Дмитрием Тучс! Занять место бесплатно еще можно, регистрация здесь ▶️ Встреча для тех, кто уже пишет на Java и хочет прокачаться в архитектуре автотестов. Спикер, Дмитрий Тучс — Head of QA в Dodo Engineering, инженер с многолетним опытом и член программного комитета конференций CodeFest, CodeTalks, EpicHey!, E-CODE. Помимо QA — бэкграунд в Java-разработке, аналитике и проектном менеджменте с 2009 года. Что будет на вебинаре? — Познакомитесь с учебным проектом Niffler: вместе взглянем на микросервисную архитектуру и технические решения проекта, с которым предстоит работать. — Разберетесь, чем «тесты на Google» (black box) отличаются от white box. А еще на занятии вы: — Напишете свой первый JUnit Extension для создания тестовых данных через API. И тест, показывающий элегантность такого решения. — Создадите полноценный «каркас» будущего проекта с E-2-E тестами: сразу напишем конфиги, page-objects, API-клиенты, DTO и многое другое! Занять место ▶️▶️▶️ Реклама. Рекламодатель: ИП Васенков Станислав Олегович, ИНН 774335827403, erid: 2VtzqwA1TXB

Скидки на электрические зубные щетки Oral-B ORAL-B Genius-X с искусственным интеллектом – первая в мире зубная щетка, которая распознает стиль чистки зубов и дает рекомендации по улучшению. Купить #реклама market.yandex.ru О рекламодателе

Задача: 648. Replace Words Сложность: medium В английском языке есть понятие "корень", за которым может следовать какое-то другое слово, чтобы образовать другое более длинное слово - назовем это слово производным. Например, если за корнем "help" следует слово "ful", мы можем образовать производное "helpful". Дайте словарь, состоящий из множества корней, и предложение, состоящее из слов, разделенных пробелами, замените все производные в предложении на образующий их корень. Если производное может быть заменено более чем одним корнем, замените его корнем, имеющим наименьшую длину. Верните предложение после замены. Пример:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

👨‍💻 Алгоритм: 1⃣Преобразуйте словарь корней в набор для быстрого поиска. 2⃣Пройдите по каждому слову в предложении и найдите самый короткий корень, который является префиксом этого слова. 3⃣Замените слово найденным корнем и соберите обновленное предложение. 😎 Решение:

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution {
    public String replaceWords(List<String> roots, String sentence) {
        Set<String> rootSet = new HashSet<>(roots);
        
        StringBuilder result = new StringBuilder();
        for (String word : sentence.split(" ")) {
            String replacement = word;
            for (int i = 1; i <= word.length(); i++) {
                String prefix = word.substring(0, i);
                if (rootSet.contains(prefix)) {
                    replacement = prefix;
                    break;
                }
            }
            if (result.length() > 0) {
                result.append(" ");
            }
            result.append(replacement);
        }
        
        return result.toString();
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Подскажем, где остановиться на день или больше В путешествии, отпуске или поездке в соседний город. На Циан.Посуточно вы можете забронировать как квартиру и дом, так и отель — выбирайте, что удобнее. ✅ Онлайн-бронирование. Календарь в приложении покажет свободные даты и итоговую стоимость проживания. ✅ Безопасная предоплата. Всего 10% в приложении — можно вернуть, если планы поменяются. Остальное оплачивайте при заезде. ✅ Идеи для путешествий. Собрали рекомендации наших пользователей — что посмотреть и что попробовать — в путеводителе Циана. Перейти на сайт #реклама 16+ cian.ru О рекламодателе

Задача: 609. Find Duplicate File in System Сложность: medium Получив список paths информации о каталоге, включающий путь к каталогу и все файлы с содержимым в этом каталоге, верните все дубликаты файлов в файловой системе по их путям. Вы можете вернуть ответ в любом порядке. Группа дубликатов состоит как минимум из двух файлов с одинаковым содержимым. Одна строка информации о каталоге во входном списке имеет следующий формат: "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)" Это означает, что в каталоге "root/d1/d2/.../dm" имеется n файлов (f1.txt, f2.txt ... fn.txt) с содержимым (f1_content, f2_content ... fn_content) соответственно. Обратите внимание, что n >= 1 и m >= 0. Если m = 0, это означает, что каталог является только корневым. На выходе получается список групп дублирующихся путей к файлам. Для каждой группы он содержит все пути к файлам, которые имеют одинаковое содержимое. Путь к файлу - это строка, имеющая следующий формат: "каталог_путь/имя_файла.txt". Пример:

Input: paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)","root 4.txt(efgh)"]
Output: [["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]

👨‍💻 Алгоритм: 1⃣Пройдите по списку путей, разберите каждый путь и соберите информацию о содержимом файлов и соответствующих им путях. 2⃣Используйте словарь для хранения списков путей файлов, сгруппированных по их содержимому. 3⃣Пройдите по словарю и соберите группы дубликатов, содержащие как минимум два пути. 😎 Решение:

import java.util.*;

public class Solution {
    public List<List<String>> findDuplicate(String[] paths) {
        Map<String, List<String>> contentToFilePaths = new HashMap<>();
        
        for (String path : paths) {
            String[] parts = path.split(" ");
            String root = parts[0];
            
            for (int i = 1; i < parts.length; i++) {
                String[] fileParts = parts[i].split("\\(");
                String fileName = fileParts[0];
                String content = fileParts[1].substring(0, fileParts[1].length() - 1);
                
                String filePath = root + "/" + fileName;
                contentToFilePaths.computeIfAbsent(content, k -> new ArrayList<>()).add(filePath);
            }
        }
        
        List<List<String>> result = new ArrayList<>();
        for (List<String> filePaths : contentToFilePaths.values()) {
            if (filePaths.size() > 1) {
                result.add(filePaths);
            }
        }
        
        return result;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

erid: 2W5zFHDmQ1e Канал про собеседования, алгоритмы, System Design, процессы, культуру и инженерию в FAANG/BigTech Автор канала — разработчик с 18-летним опытом, из которых 8 лет он провёл в FAANG (3,5 года — в Amazon). Работал и жил в России, Германии, Люксембурге и Великобритании, провёл более 100 технических интервью в FAANG-компании. На канале разбираю реальные задачи с собеседований в FAANG по алгоритмам и System Design. Рассматриваю задачи из не-FAANG компаний на Java, делая акцент на многопоточность. Делюсь опытом работы в FAANG, рассказываю о процессах, технологиях и инженерной культуре, обсуждаю особенности релокации и жизни разработчика в разных странах. Если вам интересны эти темы, подписывайтесь: t.me/faangmaster

Получи грант на обучение в Центральном университете Прояви себя, получи грант до 2,8 млн на обучение ИТ и бизнесу в вузе. Для школьников 10-х и 11-х классов, СПО. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 927. Three Equal Parts Сложность: hard Вам дан массив arr, состоящий только из нулей и единиц. Разделите массив на три непустые части так, чтобы все эти части представляли одно и то же двоичное значение. Если это возможно, верните любой [i, j] с i + 1 < j, такой что: arr[0], arr[1], ..., arr[i] - это первая часть, arr[i + 1], arr[i + 2], ...., arr[j - 1] - вторая часть, и arr[j], arr[j + 1], ..., arr[arr.length - 1] - третья часть. Все три части имеют одинаковые двоичные значения. Если это невозможно, верните [-1, -1]. Обратите внимание, что вся часть используется при рассмотрении того, какое двоичное значение она представляет. Например, [1,1,0] представляет 6 в десятичной системе, а не 3. Кроме того, допускаются ведущие нули, поэтому [0,1,1] и [1,1] представляют одно и то же значение. Пример:

Input: arr = [1,0,1,0,1]
Output: [0,3]

👨‍💻 Алгоритм: 1⃣Подсчитать количество единиц в массиве. 2⃣Если количество единиц не делится на три, вернуть [-1, -1]. Найти индексы начала каждой части, игнорируя ведущие нули. Использовать эти индексы для проверки, могут ли три части быть одинаковыми. 3⃣Если три части одинаковы, вернуть соответствующие индексы, иначе вернуть [-1, -1]. 😎 Решение:

class Solution {
    public int[] threeEqualParts(int[] arr) {
        int ones = 0;
        for (int num : arr) {
            ones += num;
        }
        if (ones % 3 != 0) return new int[]{-1, -1};
        if (ones == 0) return new int[]{0, arr.length - 1};

        int partOnes = ones / 3;
        int first = 0, second = 0, third = 0, cnt = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 1) {
                if (cnt == 0) first = i;
                else if (cnt == partOnes) second = i;
                else if (cnt == 2 * partOnes) third = i;
                cnt++;
            }
        }

        while (third < arr.length && arr[first] == arr[second] && arr[first] == arr[third]) {
            first++;
            second++;
            third++;
        }

        if (third == arr.length) return new int[]{first - 1, second};
        return new int[]{-1, -1};
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Роадмап подготовки к Java собеседованиям Цель роадмапа – предоставить список тем и источников для быстрой подготовки к собеседованиям. Темы: – Java (архитектура jvm, gc, многопоточность) – Spring (aop, transaction, cloud) – SQL/NoSQL (acid, base, уровни изоляций, explain) – Kafka/Docker/Kubernetes – Паттерны проектирования, ООП, SOLID – Алгоритмы и структуры данных – Системный дизайн Полная версия роадмапа со всеми темами и источниками лежит в канале @backend_interviewer

Современная магистратура от Центрального университета Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой? Поступай в магистратуру Центрального университета! - 4 офлайн программы по востребованным направлениям ИТ - Онлайн-программа по машинному обучению - 300 мест с грантами до 1,2 млн руб. - Вечерние занятия и учеба по выходным — удобно совмещать с работой - Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса - Возможность стажировок и трудоустройства в ведущих компаниях - Государственный диплом за 2 года Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии. Оставляй заявку на грант уже сейчас! Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 947. Most Stones Removed with Same Row or Column Сложность: medium Учитывая массив stones длины n, где stones[i] = [xi, yi] представляет местоположение i-го камня, верните наибольшее возможное количество камней, которые могут быть удалены. Пример:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

👨‍💻 Алгоритм: 1⃣Представить каждую строку и столбец как узлы в графе. 2⃣Создать связи между узлами для камней, которые находятся в той же строке или столбце. Использовать алгоритм поиска в глубину (DFS) или объединение-поиска (Union-Find), чтобы найти компоненты связности. 3⃣Количество камней, которые могут быть удалены, это общее количество камней минус количество компонентов связности. 😎 Решение:

import java.util.*;

class Solution {
    public int removeStones(int[][] stones) {
        Map<Integer, Integer> parent = new HashMap<>();
        
        int find(int x) {
            if (!parent.containsKey(x)) {
                parent.put(x, x);
            }
            if (parent.get(x) != x) {
                parent.put(x, find(parent.get(x)));
            }
            return parent.get(x);
        }
        
        void union(int x, int y) {
            parent.put(find(x), find(y));
        }
        
        for (int[] stone : stones) {
            union(stone[0], ~stone[1]);
        }
        
        Set<Integer> uniqueRoots = new HashSet<>();
        for (int key : parent.keySet()) {
            uniqueRoots.add(find(key));
        }
        
        return stones.length - uniqueRoots.size();
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Как списать долги? Бесплатно через МФЦ! Долги от 200 000₽. Поможем бесплатно списать долг и расторгнуть все кредитные договоры! Узнать больше #реклама нет-кредит.рф О рекламодателе

Задача: 1231. Divide Chocolate Сложность: hard У вас есть одна шоколадка, состоящая из нескольких кусочков. Каждый кусочек имеет свою сладость, заданную массивом сладости. Вы хотите поделиться шоколадом со своими k друзьями, поэтому начинаете разрезать шоколадку на k + 1 кусочков с помощью k разрезов, каждый кусочек состоит из нескольких последовательных кусочков. Будучи щедрым, вы съедите кусочек с минимальной общей сладостью, а остальные кусочки отдадите своим друзьям. Найдите максимальную общую сладость кусочка, который вы можете получить, оптимально разрезав шоколадку. Пример:

Input: sweetness = [1,2,3,4,5,6,7,8,9], k = 5
Output: 6

👨‍💻 Алгоритм: 1⃣Для решения задачи мы можем использовать метод двоичного поиска для определения максимальной минимальной сладости, которую можно получить. 2⃣Двоичный поиск: Мы будем искать ответ в диапазоне от минимальной сладости до суммы всех сладостей. Начнем с середины этого диапазона и проверим, можно ли разрезать шоколад таким образом, чтобы минимальная сладость была не менее этого значения. 3⃣Проверка делимости: Для каждой попытки значения сладости в двоичном поиске проверим, можем ли мы разрезать шоколад так, чтобы каждая из k+1 частей имела сладость не меньше текущего значения. 😎 Решение:

public class Solution {
    public int maximizeSweetness(int[] sweetness, int k) {
        int left = Arrays.stream(sweetness).min().getAsInt();
        int right = Arrays.stream(sweetness).sum() / (k + 1);

        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (canDivide(sweetness, k, mid)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

    private boolean canDivide(int[] sweetness, int k, int minSweetness) {
        int currentSum = 0, cuts = 0;
        for (int sweet : sweetness) {
            currentSum += sweet;
            if (currentSum >= minSweetness) {
                cuts++;
                currentSum = 0;
            }
        }
        return cuts >= k + 1;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 713. Subarray Product Less Than K Сложность: medium Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k. Пример:

Input: nums = [10,5,2,6], k = 100
Output: 8

👨‍💻 Алгоритм: 1⃣Инициализируйте переменные для отслеживания текущего произведения и количества допустимых подмассивов. Используйте два указателя для границ подмассива. 2⃣Перемещайте правый указатель по массиву и умножайте текущий элемент на текущее произведение. Если произведение становится больше или равно k, перемещайте левый указатель, уменьшая произведение до тех пор, пока оно снова не станет меньше k. 3⃣Подсчитайте количество подмассивов с текущим правым указателем, добавив к общему количеству допустимых подмассивов разницу между правым и левым указателями. 😎 Решение:

public class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int product = 1, count = 0, left = 0;
        for (int right = 0; right < nums.length; right++) {
            product *= nums[right];
            while (product >= k) {
                product /= nums[left];
                left++;
            }
            count += right - left + 1;
        }
        return count;
    }
}

Ставь 👍 и забирай 📚 Базу знаний

Задача: 990. Satisfiability of Equality Equations Сложность: medium Дан массив строк equations, представляющий отношения между переменными, где каждая строка equations[i] имеет длину 4 и принимает одну из двух форм: "xi==yi" или "xi!=yi". Здесь xi и yi - это строчные буквы (не обязательно разные), представляющие имена переменных из одной буквы. Верните true, если возможно назначить целые числа именам переменных таким образом, чтобы удовлетворить всем заданным уравнениям, или false в противном случае. Пример:

Input: equations = ["b==a","a==b"]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

👨‍💻 Алгоритм: 1⃣Создание графа для уравнений "==": Создайте структуру данных для объединения (Union-Find) для обработки уравнений равенства. Пройдите через массив equations и для каждого уравнения типа "xi==yi" объедините соответствующие переменные. 2⃣Проверка уравнений "!=": Пройдите через массив equations и для каждого уравнения типа "xi!=yi" проверьте, принадлежат ли переменные к одной и той же группе в структуре объединения. Если принадлежат, верните false. 3⃣Возврат результата: Если после проверки всех уравнений "xi!=yi" не было обнаружено противоречий, верните true. 😎 Решение:

public class Solution {
    public boolean equationsPossible(String[] equations) {
        UnionFind uf = new UnionFind(26);
        
        for (String eq : equations) {
            if (eq.charAt(1) == '=') {
                int x = eq.charAt(0) - 'a';
                int y = eq.charAt(3) - 'a';
                uf.unionSet(x, y);
            }
        }
        
        for (String eq : equations) {
            if (eq.charAt(1) == '!') {
                int x = eq.charAt(0) - 'a';
                int y = eq.charAt(3) - 'a';
                if (uf.connected(x, y)) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
    private class UnionFind {
        private int[] parent;
        
        public UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        
        public void unionSet(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                parent[rootX] = rootY;
            }
        }
        
        public boolean connected(int x, int y) {
            return find(x) == find(y);
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний

20 000 баллов на сервисы Яндекс Go для бизнеса Подключайтесь к сервису и оптимизируйте бизнес-процессы без бумажной волокиты. Яндекс Go для бизнеса как личный помощник: - организует командировку; - отвезет до работы; - накормит сотрудников. Пока вы экономите время и силы. Узнать больше #реклама 16+ business.go.yandex О рекламодателе Реклама на Яндексе