Java | LeetCode

Утраиваем бюджет на продвижение в Директе Запустите первое продвижение в Яндекс Директе с утроенным бюджетом и ИИ-помощником ✨ Используйте один из промокодов : При пополнении от 10 000 ₽ +20 000 ₽ Промокод START20 При пополнении от 15 000 ₽ +30 000 ₽ Промокод START30 Зарегистрироваться #реклама 16+ direct.yandex.ru О рекламодателе

Задача: 1365. How Many Numbers Are Smaller Than the Current Number Сложность: easy Дан массив nums. Для каждого элемента nums[i] определите, сколько чисел в массиве меньше его. То есть, для каждого nums[i] вам нужно посчитать количество допустимых j, таких что j != i и nums[j] < nums[i]. Верните ответ в виде массива. Пример:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

👨‍💻 Алгоритм: 1⃣Создание копии и сортировка массива: Создайте отсортированную копию массива nums, чтобы легко находить количество элементов, меньших текущего. 2⃣Поиск индекса каждого элемента: Для каждого элемента nums[i] найдите его индекс в отсортированной копии массива. Этот индекс указывает количество элементов, меньших nums[i]. 3⃣Формирование ответа: Сформируйте массив ответов, где каждый элемент будет соответствовать количеству чисел, меньших текущего. 😎 Решение:

import java.util.Arrays;

public class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] sortedNums = nums.clone();
        Arrays.sort(sortedNums);
        int[] result = new int[nums.length];
        
        for (int i = 0; i < nums.length; i++) {
            result[i] = Arrays.binarySearch(sortedNums, nums[i]);
        }
        
        return result;
    }
}

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

Надежные VDS-сервера в NetAngels от 130₽/месяц Подберем мощные VDS-сервер для любых задач. Техподдержка 24/7. Защита от DDoS-атак. Гибкая конфигурация. Бесплатный перенос VDS с сохранением всех данных. Выбери тариф под свои задачи: Старт (Для низкой нагрузки: хранение файлов, раздача статики и простые веб-проекты) Оптима (NVMe-диски для высокой скорости и баланс цены и производительности) Турбо (Элитный VDS на базе топового оборудования с высокочастотными процессорами) Про (Мощный VDS с гарантированными ресурсами для масштабных проектов) ТурбоПро (VDS уровня enterprise с гарантированными ядрами и высокочастотными процессорами) Ультра (Высокопроизводительный VDS для ресурсоемких проектов и корпоративных систем. В тариф включена поддержка GPU) Попробуйте VDS-сервер от NetAngels! Перейти на сайт #реклама 16+ netangels.ru О рекламодателе

Осталось 3 часа до конца акции: «Пожизненный PRO тариф — по цене 1 года» Поиск работы отнимает силы, время и веру в себя, но не у тех кто использует easyoffer PRO. Успей сделать самую выгодную инвестицию в развитие своей карьеры. Акция закончится уже сегодня 23 июня 23:59 по мск: 👉 https://easyoffer.ru/pro

Задача: 754. Reach a Number Сложность: medium Вы стоите в позиции 0 на бесконечной числовой прямой. В позиции target находится пункт назначения. Вы можете сделать некоторое количество ходов numMoves так, чтобы: на каждом ходу вы могли пойти либо налево, либо направо. Во время i-го хода (начиная с i == 1 до i == numMoves) вы делаете i шагов в выбранном направлении. Учитывая целое число target, верните минимальное количество ходов (т.е. минимальное numMoves), необходимое для достижения пункта назначения. Пример:

Input: target = 2
Output: 3

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

public class Solution {
    public int reachTarget(int target) {
        target = Math.abs(target);
        int position = 0;
        int steps = 0;
        while (position < target || (position - target) % 2 != 0) {
            steps++;
            position += steps;
        }
        return steps;
    }

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

Задача: 1466. Reorder Routes to Make All Paths Lead to the City Zero Сложность: medium Дано n городов, пронумерованных от 0 до n - 1, и n - 1 дорог, таких, что существует только один путь между двумя различными городами (эта сеть образует дерево). В прошлом году Министерство транспорта решило направить дороги в одном направлении, потому что они слишком узкие. Дороги представлены массивом connections, где connections[i] = [ai, bi] представляет дорогу от города ai до города bi. В этом году в столице (город 0) будет большое событие, и многие люди хотят приехать в этот город. Ваша задача состоит в том, чтобы переориентировать некоторые дороги так, чтобы каждый город мог посетить город 0. Верните минимальное количество изменённых дорог. Гарантируется, что каждый город может добраться до города 0 после перенаправления. Пример:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

👨‍💻 Алгоритм: 1⃣Создайте переменную count для подсчета количества рёбер, которые необходимо изменить. Инициализируйте её нулём. Создайте список смежности adj, который содержит список пар целых чисел так, чтобы adj[node] содержал всех соседей node в форме (neighbor, sign), где neighbor - соседний узел, а sign обозначает направление ребра (оригинальное или искусственное). 2⃣Начните обход в глубину (DFS). Используйте функцию dfs для выполнения обхода. В каждом вызове передавайте параметры node, parent и adj. Начните с узла 0 и parent равным -1. 3⃣Перебирайте всех соседей узла с помощью adj[node]. Для каждого neighbor, sign в adj[node], проверьте, равен ли neighbor родителю. Если равен, не посещайте его снова. Если neighbor не равен parent, выполните count += sign и рекурсивно вызовите dfs с node = neighbor и parent = node. По завершении обхода DFS, в count будет содержаться количество рёбер, которые необходимо изменить. Верните count. 😎 Решение:

class Solution {
    int count = 0;

    public void dfs(int node, int parent, Map<Integer, List<List<Integer>>> adj) {
        if (!adj.containsKey(node)) {
            return;
        }
        for (List<Integer> nei : adj.get(node)) {
            int neighbor = nei.get(0);
            int sign = nei.get(1);
            if (neighbor != parent) {
                count += sign;
                dfs(neighbor, node, adj);
            }
        }
    }

    public int minReorder(int n, int[][] connections) {
        Map<Integer, List<List<Integer>>> adj = new HashMap<>();
        for (int[] connection : connections) {
            adj.computeIfAbsent(connection[0], k -> new ArrayList<List<Integer>>()).add(
                    Arrays.asList(connection[1], 1));
            adj.computeIfAbsent(connection[1], k -> new ArrayList<List<Integer>>()).add(
                    Arrays.asList(connection[0], 0));
        }
        dfs(0, -1, adj);
        return count;
    }
}

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

Последний день акции: «Пожизненный PRO тариф — по цене 1 года» 🚀 PRO включает: – Полный доступ ко всем грейдам и профессиям – База live-coding задач и вопросов из технических собеседований с вероятностью их встречи – Примеры лучших ответов от Senior разработчиков – 1100+ записи реальных собеседований, в том числе в топовые компании (Сбер, Авито, Яндекс, WB, OZON, МТС и др.) – База 400+ тестовых заданий от компаний. – Автоотклики на вакансии в хедхантер – Аналитика ТОП-требований из вакансий для лучшего написания резюме и прохождения ATS систем рекрутеров – Генератор уникального резюме и CV под каждую вакансию – Тренажеры подготовки к собеседованию: «Реальное собеседование» и «Проработка вопросов» по методике интервальных повторений (как Anki) – (скоро) Агрегатор вакансий – (скоро) Сообщество Акция закончится уже сегодня 23 июня 23:59 по мск: 👉 https://easyoffer.ru/pro

Аренда VPS/VDS-сервера. Виртуальные выделенные серверы в дата-центрах уровня Tier III — 7 готовых конфигураций от 200 ₽/мес. Преимущества аренды: - Выделенные ресурсы без переплаты; - KVM-виртуализация; - Быстрые NVMe SSD; - Соответствие 152-ФЗ, PCI DSS; - Бесплатная защита от DDoS; - Управление через панель, API и Terraform; - Техподдержка 24/7. Запустите сервер за несколько минут! Попробовать #реклама 16+ selectel.ru О рекламодателе

Задача: 315. Count of Smaller Numbers After Self Сложность: hard Дан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i]. Пример:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

👨‍💻 Алгоритм: 1⃣Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4. 2⃣Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия: Смещайте число на num + offset. Запросите количество элементов в дереве отрезков, которые меньше текущего числа. Обновите счетчик текущего числа в дереве отрезков. 3⃣Верните результат. 😎 Решение:

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int offset = 10000;
        int size = 2 * 10000 + 1;
        int[] tree = new int[size * 2];
        List<Integer> result = new ArrayList<Integer>();

        for (int i = nums.length - 1; i >= 0; i--) {
            int smaller_count = query(0, nums[i] + offset, tree, size);
            result.add(smaller_count);
            update(nums[i] + offset, 1, tree, size);
        }
        Collections.reverse(result);
        return result;
    }

    private void update(int index, int value, int[] tree, int size) {
        index += size;
        tree[index] += value;
        while (index > 1) {
            index /= 2;
            tree[index] = tree[index * 2] + tree[index * 2 + 1];
        }
    }

    private int query(int left, int right, int[] tree, int size) {
        int result = 0;
        left += size;
        right += size;
        while (left < right) {
            if (left % 2 == 1) {
                result += tree[left];
                left++;
            }
            left /= 2;
            if (right % 2 == 1) {
                right--;
                result += tree[right];
            }
            right /= 2;
        }
        return result;
    }
}

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

Пожизненный PRO тариф — по цене 1 года. Покупаешь один раз — пользуешься всю жизнь: 👉 https://easyoffer.ru/pro 🚀 PRO-доступ закроет 99% проблем на пути к офферу: 1. Полный доступ ко всем грейдам и профессиям. Не важно, Junior вы или Senior, Тестировщик, Разработчик, Проджект — вы получите материалы под ваш текущий уровень и цели, без ограничений. 2. База live-coding задач и вопросов с реальных собесов с уникальной системой вероятности их встречи. Вы будете готовиться не вслепую, а точечно по тем темам, которые спрашивают чаще всего. 3. Эталонные ответы от Senior-разработчиков. Никакой воды и догадок — только четкие, структурированные решения, за которые дают «зеленый свет» к офферу 4. 1100+ записей реальных собеседований (включая топы: Сбер, Авито, Яндекс, WB, OZON, МТС). Вы увидите всё изнутри: как спрашивают, как отвечают сильные кандидаты и на каких ошибках проваливаются 80% проходящих. 5. База 400+ тестовых заданий. Если вы еще студент, то практикуйтесь на решении задач, которые помогут попасть на собес 6. Автоотклики на Хедхантере — пока вы спите, ваше резюме летит к рекрутерам автоматически. Это экономия сотен часов ручного кликанья. 7. Аналитика ТОП-требований из вакансий. Мы парсим рынок и показываем, какие скиллы сейчас в цене. Это позволит вам точечно апгрейдить резюме и проходить суровые ATS-фильтры (которые отсеивают до 75% резюме еще до просмотра рекрутером). 8. Генератор уникального резюме и CV под каждую вакансию. Забудьте про «универсальное» резюме — нейросеть адаптирует ваш опыт под конкретную позицию за минуту, повышая шансы на приглашение в разы. 9. Тренажеры подготовки к собеседованию: «Реальное собеседование» — сценарий вопросов из реальных интервью «Проработка вопросов» — флеш карточки с вопросами/ответами по методике интервальных повторений (как Anki) 10. (Скоро) Агрегатор вакансий — все вакансии из HH, Telegram, LinkedIn и других площадок в одной ленте. 11. (Скоро) Закрытое комьюнити — нетворкинг и помощь в сложных вопросах от таких же целеустремленных айтишников. Завтра последний день акции: 👉 https://easyoffer.ru/pro

Задача: 238. Product of Array Except Self Сложность: medium Дан массив целых чисел nums, верните массив answer такой, что answer[i] равен произведению всех элементов массива nums, кроме nums[i]. Произведение любого префикса или суффикса массива nums гарантированно помещается в 32-битное целое число. Вы должны написать алгоритм, который работает за время O(n) и не использует операцию деления. Пример:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

👨‍💻 Алгоритм: 1⃣Инициализация массивов L и R: Инициализируйте два пустых массива L и R. Массив L будет содержать произведение всех чисел слева от i, а массив R будет содержать произведение всех чисел справа от i. Заполните массив L, установив L[0] равным 1, а для остальных элементов используйте формулу L[i] = L[i-1] * nums[i-1]. Заполните массив R, установив R[length-1] равным 1, а для остальных элементов используйте формулу R[i] = R[i+1] * nums[i+1]. 2⃣Заполнение массивов L и R: Пройдите два цикла для заполнения массивов L и R. В первом цикле заполните массив L, начиная с L[0] и двигаясь вправо. Во втором цикле заполните массив R, начиная с R[length-1] и двигаясь влево. 3⃣Формирование результата: Пройдите по исходному массиву и для каждого элемента i вычислите произведение всех элементов, кроме nums[i], используя L[i] * R[i]. Сохраните результат в массиве answer и верните его. 😎 Решение:

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] L = new int[length];
        int[] R = new int[length];
        int[] answer = new int[length];

        L[0] = 1;
        for (int i = 1; i < length; i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }

        R[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--) {
            R[i] = nums[i + 1] * R[i + 1];
        }

        for (int i = 0; i < length; i++) {
            answer[i] = L[i] * R[i];
        }

        return answer;
    }
}

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

Нужен мессенджер для работы? Битрикс24 — ваш мессенджер для работы и бизнеса. Личные и групповые чаты, видеозвонки и каналы в одном сервисе. Приглашайте коллег и внешние команды. Работает как привычный мессенджер. Есть бесплатный тариф. Начните работать уже сейчас. Битрикс24 — мессенджер для вашей компании. Попробовать #реклама 16+ bitrix24.ru О рекламодателе

Задача: 303. Range Sum Query - Immutable Сложность: easy Дан целочисленный массив nums. Обработайте несколько запросов следующего типа: Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right. Реализуйте класс NumArray: - NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums. - int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]). Пример:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums. 2⃣Предварительное вычисление сумм: Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно. 3⃣Вычисление диапазонной суммы: Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат. 😎 Решение:

public class NumArray {
    private int[] sum;

    public NumArray(int[] nums) {
        sum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }

    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

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

Регистрируйся на ИТ-Пикник от Т-Банка 8 августа 8 августа — время отложить ноутбуки и встретиться офлайн на ИТ-Пикнике от Т-Банка в музее-заповеднике «Коломенское». Вот сколько всего запланировано: — научпоп-лекции; — мастер-классы; — дискуссии об ИИ и больших языковых моделях; — доклады о кибербезопасности; — примеры, как данные из логов становятся решениями; — много музыки. Бери с собой друзей, супругов и детей — каждый найдет себе что-то по душе. Узнать больше #реклама 16+ it-picnic.ru О рекламодателе

Привет, ребята! У нас для вас отличные новости — на easyoffer вышло сразу несколько крупных обновлений: 1. Автоотклики на HeadHunter Снова работают в полную силу — можно смело возвращаться к активному поиску. 2. Новый раздел «Резюмейкер» Теперь вы можете быстро создавать уникальные резюме, адаптированные под каждую вакансию, и сразу добавлять сопроводительное письмо. Это заметно повышает шансы получить приглашение на собеседование. 3. База вопросов стала чище Мы навели порядок и удалили около 30% дубликатов. Ориентироваться стало проще. –––––––––––––––––– 🔥 Акция в честь обновления Пожизненный тариф easyoffer PRO — по цене одного года. Успейте до 23 июня: 👉 https://easyoffer.ru/pro –––––––––––––––––– Что дальше? В ближайшие пару недель добавим ещё два раздела: 1. Сообщество с чатами по всем профессиональным направлениям. 2. Агрегатор вакансий, чтобы поиск работы стал ещё удобнее.

Задача: 1233. Remove Sub-Folders from the Filesystem Сложность: medium Если дан список папок folder, верните папки после удаления всех вложенных папок в этих папках. Вы можете вернуть ответ в любом порядке. Если папка[i] находится внутри другой папки[j], она называется ее вложенной папкой. Формат пути - это одна или несколько скомбинированных строк вида: '/', за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" являются допустимыми путями, а пустая строка и "/" - нет. Пример:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]

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

import java.util.*;

public class Solution {
    public List<String> removeSubfolders(String[] folder) {
        Arrays.sort(folder);
        List<String> result = new ArrayList<>();
        String parent = "";
        
        for (String path : folder) {
            if (parent.isEmpty() || !path.startsWith(parent + "/")) {
                parent = path;
                result.add(path);
            }
        }
        
        return result;
    }
}

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

Вакансия Альфа-Агент — в команде Альфа-Банка Станьте Альфа-Агентом — работа в прямых продажах у лучшего работодателя страны. Присоединяйтесь к команде ❤️ Конкурентоспособная зарплата, расширенный ДМС со стоматологией, программа поддержки первые 3 месяца. Карьера в ваших руках! Смотрите актуальные вакансии на официальном сайте Альфа-Банка. Перейти на сайт #реклама job.alfabank.ru О рекламодателе

Задача: 1472. Design Browser History Сложность: medium У вас есть браузер с одной вкладкой, где вы начинаете на домашней странице и можете посетить другой URL, вернуться назад на определённое количество шагов в истории или переместиться вперёд на определённое количество шагов в истории. Реализуйте класс BrowserHistory: BrowserHistory(string homepage) Инициализирует объект с домашней страницей браузера. void visit(string url) Посещает URL с текущей страницы. Это очищает всю историю вперёд. string back(int steps) Перемещает на steps шагов назад в истории. Если вы можете вернуться только на x шагов в истории, а steps > x, вы вернётесь только на x шагов. Возвращает текущий URL после перемещения назад в истории на не более чем steps шагов. string forward(int steps) Перемещает на steps шагов вперёд в истории. Если вы можете переместиться только на x шагов вперёд в истории, а steps > x, вы переместитесь только на x шагов. Возвращает текущий URL после перемещения вперёд в истории на не более чем steps шагов. Пример:

Input:
["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"]
[["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]]
Output:
[null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]

Explanation:
BrowserHistory browserHistory = new BrowserHistory("leetcode.com");
browserHistory.visit("google.com");       // You are in "leetcode.com". Visit "google.com"
browserHistory.visit("facebook.com");     // You are in "google.com". Visit "facebook.com"
browserHistory.visit("youtube.com");      // You are in "facebook.com". Visit "youtube.com"
browserHistory.back(1);                   // You are in "youtube.com", move back to "facebook.com" return "facebook.com"
browserHistory.back(1);                   // You are in "facebook.com", move back to "google.com" return "google.com"
browserHistory.forward(1);                // You are in "google.com", move forward to "facebook.com" return "facebook.com"
browserHistory.visit("linkedin.com");     // You are in "facebook.com". Visit "linkedin.com"
browserHistory.forward(2);                // You are in "linkedin.com", you cannot move forward any steps.

👨‍💻 Алгоритм: 1⃣Инициализация: Создайте класс BrowserHistory с двумя стеками (history и future) и строковой переменной current для хранения текущего URL. Инициализируйте current с домашней страницей. 2⃣Посещение URL: Метод visit(url) сохраняет текущий URL в стеке history, устанавливает url как текущий и очищает стек future. 3⃣Навигация назад и вперед: Метод back(steps) перемещает текущий URL в стек future и извлекает URL из стека history, пока шаги не будут исчерпаны или стек history не станет пустым. Метод forward(steps) перемещает текущий URL в стек history и извлекает URL из стека future, пока шаги не будут исчерпаны или стек future не станет пустым. 😎 Решение:

class BrowserHistory {
    private Stack<String> history, future;
    private String current;
    
    public BrowserHistory(String homepage) {
        history = new Stack<String>();
        future = new Stack<String>();
        current = homepage;
    }
    
    public void visit(String url) {
        history.push(current);
        current = url;
        future = new Stack<String>();
    }
    
    public String back(int steps) {
        while(steps > 0 && !history.empty()) {
            future.push(current);
            current = history.pop();
            steps--;
        }
        return current;
    }
    
    public String forward(int steps) 
        while(steps > 0 && !future.empty()) {
            history.push(current);
            current = future.pop();
            steps--;
        }
        return current;
    }
}

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

Задача: 1257. Smallest Common Region Сложность: medium Вам даны списки регионов, в которых первый регион каждого списка включает все остальные регионы этого списка. Естественно, если регион x содержит другой регион y, то x больше y. Также, по определению, регион x содержит сам себя. Даны два региона: region1 и region2, верните наименьший регион, который содержит их оба. Если вам даны регионы r1, r2 и r3 такие, что r1 включает r3, то гарантированно не существует r2 такого, что r2 включает r3. Гарантированно существует наименьший регион. Пример:

Input:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
Output: "North America"

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

import java.util.*;

public class Solution {
    public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
        Map<String, String> parent = new HashMap<>();

        for (List<String> regionList : regions) {
            for (int i = 1; i < regionList.size(); i++) {
                parent.put(regionList.get(i), regionList.get(0));
            }
        }

        Set<String> ancestors1 = new HashSet<>();
        while (region1 != null) {
            ancestors1.add(region1);
            region1 = parent.get(region1);
        }

        while (!ancestors1.contains(region2)) {
            region2 = parent.get(region2);
        }

        return region2;
    }
}

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

Онлайн-демо вендоров ВКС-оборудования ✅Как выбрать ВКС-комплект для переговорной и не ошибиться с интеграцией? Для ИТ-руководителя это не всегда просто: одна переговорная маленькая, другая — на 20 человек, нужны чистый звук, видеосвязь без сбоев, корректная интеграция в ИТ-инфраструктуру и соответствие требованиям безопасности. 💻 Чтобы не тратить недели на изучение характеристик и сравнение вендоров, приходите на 40-минутную онлайн-экскурсию МТС Линк по готовым решениям для переговорных и конференц-залов. За 40 минут экскурсии вы получите: — обзор и сравнение готовых решений от ведущих вендоров Yealink, Lumien и IPVS; — рекомендации по интеграции; — разбор требований к безопасности; — примеры комплектов для переговорных разного размера. 🎓Получите запись онлайн-экскурсии бесплатно Получить предложение #реклама 16+ mts-link.ru О рекламодателе