Java | LeetCode

Задача: 847. Shortest Path Visiting All Nodes Сложность: hard У вас есть неориентированный связный граф из n узлов, пронумерованных от 0 до n - 1. Вам дан массив graph, где graph[i] — это список всех узлов, соединенных с узлом i ребром. Верните длину кратчайшего пути, который посещает каждый узел. Вы можете начать и закончить в любом узле, вы можете несколько раз посещать узлы и использовать ребра повторно. Пример:

Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

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

class Solution {
    public int shortestPathLength(int[][] graph) {
        if (graph.length == 1) {
            return 0;
        }
        
        int n = graph.length;
        int endingMask = (1 << n) - 1;
        boolean[][] seen = new boolean[n][endingMask];
        ArrayList<int[]> queue = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            queue.add(new int[] {i, 1 << i});
            seen[i][1 << i] = true;
        }
        
        int steps = 0;
        while (!queue.isEmpty()) {
            ArrayList<int[]> nextQueue = new ArrayList<>();
            for (int i = 0; i < queue.size(); i++) {
                int[] currentPair = queue.get(i);
                int node = currentPair[0];
                int mask = currentPair[1];
                for (int neighbor : graph[node]) {
                    int nextMask = mask | (1 << neighbor);
                    if (nextMask == endingMask) {
                        return 1 + steps;
                    }
                    
                    if (!seen[neighbor][nextMask]) {
                        seen[neighbor][nextMask] = true;
                        nextQueue.add(new int[] {neighbor, nextMask});
                    }
                }
            }
            steps++;
            queue = nextQueue;
        }
        
        return -1;
    }
}

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

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

Задача: 286. Walls and Gates Сложность: medium Вам дана сетка размером m x n, представляющая комнаты, инициализированные следующими значениями: -1: Стена или препятствие. 0: Ворота. INF: Бесконечность, обозначающая пустую комнату. Мы используем значение 2^31 - 1 = 2147483647 для представления INF, так как можно предположить, что расстояние до ворот меньше 2147483647. Заполните каждую пустую комнату расстоянием до ближайших ворот. Если невозможно добраться до ворот, комната должна быть заполнена значением INF. Пример:

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

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

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    private static final int INF = 2147483647;
    private static final int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public void wallsAndGates(int[][] rooms) {
        int m = rooms.length;
        if (m == 0) return;
        int n = rooms[0].length;
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    queue.add(new int[]{i, j});
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] point = queue.poll();
            int x = point[0], y = point[1];
            for (int[] direction : directions) {
                int nx = x + direction[0];
                int ny = y + direction[1];
                if (nx >= 0 && ny >= 0 && nx < m && ny < n && rooms[nx][ny] == INF) {
                    rooms[nx][ny] = rooms[x][y] + 1;
                    queue.add(new int[]{nx, ny});
                }
            }
        }
    }
}

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких 30 дней бесплатно. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 1240. Tiling a Rectangle with the Fewest Squares Сложность: hard Если задан прямоугольник размером n x m, верните минимальное количество квадратов с целочисленными сторонами, которые покрывают этот прямоугольник. Пример:

Input: n = 2, m = 3
Output: 3

👨‍💻 Алгоритм: 1⃣Инициализация рекурсивной функции: Функция принимает размеры прямоугольника n x m. 2⃣Базовый случай: Если n = 0 или m = 0, возвращаем 0, так как не осталось пространства для покрытия. 3⃣Рекурсивный случай: Находим наибольший возможный квадрат, который может быть размещен в текущем прямоугольнике. Это квадрат со стороной min(n, m). Размещаем этот квадрат в левом верхнем углу и рекурсивно покрываем оставшиеся три части: Прямоугольник слева от квадрата. Прямоугольник сверху от квадрата. Прямоугольник справа и снизу от квадрата. 😎 Решение:

public class Solution {
    public int tilingRectangle(int n, int m) {
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; ++i) {
            for (int j = 0; j <= m; ++j) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }

        for (int i = 1; i <= Math.min(n, m); ++i) {
            dp[i][i] = 1;
        }

        for (int h = 1; h <= n; ++h) {
            for (int w = 1; w <= m; ++w) {
                if (h == w) continue;
                for (int i = 1; i <= h / 2; ++i) {
                    dp[h][w] = Math.min(dp[h][w], dp[i][w] + dp[h - i][w]);
                }
                for (int j = 1; j <= w / 2; ++j) {
                    dp[h][w] = Math.min(dp[h][w], dp[h][j] + dp[h][w - j]);
                }
            }
        }
        return dp[n][m];
    }
}

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

Высшее образование онлайн — поменяйте жизнь в 2025 году! ✅Набор в июне: от 6700 ₽/мес.* Московский технологический институт предлагает: — Высшее образование в московском вузе без выезда на сессии — Полностью дистанционный онлайн-формат — Возможность обучаться дома, на работе, в путешествии — Диплом государственного образца — Более 60 направлений на выбор (IT, инженерные, экономические, педагогические, управленческие и другие) — 5 способов оплаты обучения — Поддержка персонального куратора: от поступления до получения диплома Узнать больше #реклама 16+ mti-vuz.ru О рекламодателе

Задача: 173. Binary Search Tree Iterator Сложность: medium Реализуйте класс BSTIterator, который представляет итератор по обходу бинарного дерева поиска (BST) в порядке in-order: BSTIterator(TreeNode root): Инициализирует объект класса BSTIterator. Корень BST передается в качестве параметра конструктора. Указатель должен быть инициализирован на несуществующее число, меньшее любого элемента в BST. boolean hasNext(): Возвращает true, если в обходе справа от указателя существует число, иначе возвращает false. int next(): Перемещает указатель вправо, затем возвращает число на указателе. Обратите внимание, что при инициализации указателя на несуществующее наименьшее число, первый вызов next() вернет наименьший элемент в BST. Можно предположить, что вызовы next() всегда будут допустимы. То есть, при вызове next() в обходе всегда будет хотя бы одно следующее число. Пример:

Input
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
Output
[null, 3, 7, true, 9, true, 15, true, 20, false]

Explanation
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // return 3
bSTIterator.next();    // return 7
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 9
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 15
bSTIterator.hasNext(); // return True
bSTIterator.next();    // return 20
bSTIterator.hasNext(); // return False

👨‍💻 Алгоритм: 1⃣Инициализируйте пустой массив, который будет содержать узлы бинарного дерева поиска в отсортированном порядке. 2⃣Мы обходим бинарное дерево поиска в порядке in-order и для каждого узла, который обрабатываем, добавляем его в наш массив узлов. Обратите внимание, что перед обработкой узла сначала нужно обработать (или рекурсивно вызвать) его левое поддерево, а после обработки узла — его правое поддерево. 3⃣Когда у нас будут все узлы в массиве, нам просто нужен укзатель или индекс в этом массиве для реализации двух функций next и hasNext. Всякий раз, когда вызывается hasNext, мы просто проверяем, достиг ли индекс конца массива или нет. При вызове функции next мы просто возвращаем элемент, на который указывает индекс. Также, после вызова функции next, мы должны переместить индекс на один шаг вперед, чтобы имитировать прогресс нашего итератора. 😎 Решение:

class BSTIterator {
    ArrayList<Integer> nodesSorted;
    int index;

    public BSTIterator(TreeNode root) {
        this.nodesSorted = new ArrayList<Integer>();
        this.index = -1;
        this._inorder(root);
    }

    private void _inorder(TreeNode root) {
        if (root == null) {
            return;
        }

        this._inorder(root.left);
        this.nodesSorted.add(root.val);
        this._inorder(root.right);
    }

    public int next() {
        return this.nodesSorted.get(++this.index);
    }

    public boolean hasNext() {
        return this.index + 1 < this.nodesSorted.size();
    }
}

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

Высшее образование дистанционно в Московском ВУЗе Вы мечтаете получить высшее образование, но не сдали ЕГЭ или получили низкие баллы? У нас есть решение для вас! Институт Международных Экономических Связей предлагает дистанционное обучение , которое позволяет получать качественные знания из любой точки мира по 10+ направлениям обучения. ✅ Государственный диплом без отметки о дистанте ✅ Удобный личный кабинет студента ✅ Поддержка кураторов на каждом этапе обучения ✅ Можно поступить без ЕГЭ Узнать больше #реклама 16+ imes.su О рекламодателе

Задача: 314. Binary Tree Vertical Order Traversal Сложность: medium Дан корень бинарного дерева, верните вертикальный порядок обхода значений его узлов (т.е. сверху вниз, столбец за столбцом). Если два узла находятся в одной строке и столбце, порядок должен быть слева направо. Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

👨‍💻 Алгоритм: 1⃣Создайте хэш-таблицу с именем columnTable для отслеживания результатов. 2⃣Инициализируйте очередь, поместив в нее корневой узел вместе с его индексом столбца (0). Выполните обход в ширину (BFS), извлекая элементы из очереди. На каждой итерации извлекайте элемент, состоящий из узла и соответствующего индекса столбца. Если узел не пуст, добавьте его значение в columnTable. Затем поместите дочерние узлы с их индексами столбцов (т.е. column-1 и column+1) в очередь. 3⃣После завершения BFS обхода получите хэш-таблицу, содержащую значения узлов, сгруппированные по индексам столбцов. Для каждой группы значений отсортируйте их по индексам строк. Отсортируйте хэш-таблицу по ключам (индексам столбцов) в порядке возрастания и верните результаты по столбцам. 😎 Решение:

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> output = new ArrayList<>();
        if (root == null) {
            return output;
        }

        Map<Integer, ArrayList<Integer>> columnTable = new HashMap<>();
        Queue<Pair<TreeNode, Integer>> queue = new ArrayDeque<>();
        int column = 0;
        queue.offer(new Pair<>(root, column));

        while (!queue.isEmpty()) {
            Pair<TreeNode, Integer> p = queue.poll();
            root = p.getKey();
            column = p.getValue();

            if (root != null) {
                if (!columnTable.containsKey(column)) {
                    columnTable.put(column, new ArrayList<Integer>());
                }
                columnTable.get(column).add(root.val);

                queue.offer(new Pair<>(root.left, column - 1));
                queue.offer(new Pair<>(root.right, column + 1));
            }
        }

        List<Integer> sortedKeys = new ArrayList<>(columnTable.keySet());
        Collections.sort(sortedKeys);
        for (int k : sortedKeys) {
            output.add(columnTable.get(k));
        }

        return output;
    }
}

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

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

Задача: 999. Available Captures for Rook Сложность: easy Вам дана матрица 8 x 8, изображающая шахматную доску. На ней есть ровно одна белая ладья, представленная символом "R", некоторое количество белых слонов "B" и некоторое количество черных пешек "p". Пустые клетки обозначаются символом '.'. Ладья может перемещаться на любое количество клеток по горизонтали или вертикали (вверх, вниз, влево, вправо), пока не достигнет другой фигуры или края доски. Ладья атакует пешку, если она может переместиться на ее клетку за один ход. Примечание: Ладья не может перемещаться через другие фигуры, такие как слоны или пешки. Это означает, что ладья не может атаковать пешку, если путь ей преграждает другая фигура. Верните количество пешек, которые атакует белая ладья. Пример:

Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]

Output: 3

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

public class Solution {
    public int numRookCaptures(char[][] board) {
        int countPawns(int x, int y, int dx, int dy) {
            while (x >= 0 && x < 8 && y >= 0 && y < 8) {
                if (board[x][y] == 'B') break;
                if (board[x][y] == 'p') return 1;
                x += dx;
                y += dy;
            }
            return 0;
        }

        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (board[i][j] == 'R') {
                    return countPawns(i, j, -1, 0) + countPawns(i, j, 1, 0) +
                           countPawns(i, j, 0, -1) + countPawns(i, j, 0, 1);
                }
            }
        }
        return 0;
    }
}

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

Задача: 477. Total Hamming Distance Сложность: medium Хэммингово расстояние между двумя целыми числами — это количество позиций, в которых соответствующие биты отличаются. Дан целочисленный массив nums, верните сумму Хэмминговых расстояний между всеми парами чисел в nums. Пример:

Input: nums = [4,14,2]
Output: 6
Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case).
The answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

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

public class Solution {
    public int totalHammingDistance(int[] nums) {
        int ans = 0;
        
        if (nums.length == 0) {
            return ans;
        }
        
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                ans += Integer.bitCount(nums[i] ^ nums[j]);
            }
        }
        
        return ans;
    }
}

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

Задача: 329. Longest Increasing Path in a Matrix Сложность: hard Дана матрица целых чисел размером m x n. Верните длину самого длинного возрастающего пути в матрице. Из каждой ячейки можно перемещаться в четырех направлениях: влево, вправо, вверх или вниз. Перемещение по диагонали или выход за границы матрицы (т.е. замкнутые переходы) не допускается. Пример:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

👨‍💻 Алгоритм: 1⃣Инициализация и создание матрицы: Инициализируйте размеры матрицы m и n. Создайте матрицу matrix с добавленными границами (нулевыми значениями) вокруг исходной матрицы, чтобы избежать выхода за пределы при обработке. Рассчитайте количество исходящих связей (outdegrees) для каждой клетки и сохраните их в outdegree. 2⃣Поиск начальных листьев: Найдите все клетки с нулевыми исходящими связями и добавьте их в список leaves. Эти клетки будут начальной точкой для "слоевого удаления". 3⃣Удаление слоев: Повторяйте процесс удаления клеток уровня за уровнем в порядке топологической сортировки, пока не останется листьев. Обновляйте количество исходящих связей и добавляйте новые листья на следующем уровне. Подсчитывайте количество уровней, что в итоге даст длину самого длинного возрастающего пути. 😎 Решение:

public class Solution {
    private static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private int m, n;
    public int longestIncreasingPath(int[][] grid) {
        int m = grid.length;
        if (m == 0) return 0;
        int n = grid[0].length;
        int[][] matrix = new int[m + 2][n + 2];
        for (int i = 0; i < m; ++i)
            System.arraycopy(grid[i], 0, matrix[i + 1], 1, n);

        int[][] outdegree = new int[m + 2][n + 2];
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                for (int[] d: dir)
                    if (matrix[i][j] < matrix[i + d[0]][j + d[1]])
                        outdegree[i][j]++;

        n += 2;
        m += 2;
        List<int[]> leaves = new ArrayList<>();
        for (int i = 1; i < m - 1; ++i)
            for (int j = 1; j < n - 1; ++j)
                if (outdegree[i][j] == 0) leaves.add(new int[]{i, j});

        int height = 0;
        while (!leaves.isEmpty()) {
            height++;
            List<int[]> newLeaves = new ArrayList<>();
            for (int[] node : leaves) {
                for (int[] d:dir) {
                    int x = node[0] + d[0], y = node[1] + d[1];
                    if (matrix[node[0]][node[1]] > matrix[x][y])
                        if (--outdegree[x][y] == 0)
                            newLeaves.add(new int[]{x, y});
                }
            }
            leaves = newLeaves;
        }
        return height;
    }
}

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

Регистрируйтесь на вебинар SIEM UserGate 💻Расскажет о том, как экосистема и SIEM UserGate помогает бороться с фишинговыми атаками в рамках демонстрации конкретного кейса. На вебинаре будет: - Вступительное слово - Экспертиза UserGate и сценарий конкретного кейса - Демонстрация кейса защиты от фишинговой атаки - Ответы на вопросы 👌Расскажем, как защитить вашу компанию. Регистрируйтесь — будет интересно! Зарегистрироваться #реклама 16+ webinar.usergate.com О рекламодателе

Задача: 1315. Sum of Nodes with Even-Valued Grandparent Сложность: medium Given the root of a binary tree, return the sum of values of nodes with an even-valued grandparent. If there are no nodes with an even-valued grandparent, return 0. A grandparent of a node is the parent of its parent if it exists. Пример:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 18
Explanation: The red nodes are the nodes with even-value grandparent while the blue nodes are the even-value grandparents.

👨‍💻 Алгоритм: 1⃣Определите метод solve(), который принимает TreeNode root, значение родителя parent и значение бабушки или дедушки gParent. Этот метод возвращает сумму значений узлов с четным значением бабушки и дедушки в поддереве узла root. Если root равен null, верните 0 как сумму. 2⃣Рекурсивно пройдите по левому и правому дочерним узлам, передавая в качестве значения parent root, а в качестве значения gParent parent. Если значение gParent четное, добавьте значение root к ответу. 3⃣Вызовите рекурсивную функцию solve() с корневым узлом и значениями -1 для parent и gParent. Верните сумму для левого и правого дочерних узлов и значение для текущего узла. 😎 Решение:

class Solution {
    int solve(TreeNode root, int parent, int gParent) {
        if (root == null) {
            return 0;
        }
        return solve(root.left, root.val, parent) + solve(root.right, root.val, parent) + (gParent % 2 != 0 ? 0 : root.val);
    }

    public int sumEvenGrandparent(TreeNode root) {
        return solve(root, -1, -1);
    }
}

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

Битрикс24 дропнул новую фичу — онлайн-доски Теперь к вашему рабочему мессенджеру, видеозвонкам и таскам добавился еще один маст-хэв инструмент. Все это бесплатно и в одном комплекте. Офисные стикеры, берегитесь.😊 Узнать больше #реклама 16+ bitrix24.ru О рекламодателе

Задача: 56. Merge Intervals Сложность: medium Дан массив интервалов, где intervals[i] = [starti, endi]. Объедините все перекрывающиеся интервалы и верните массив неперекрывающихся интервалов, которые покрывают все интервалы во входных данных. Пример:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

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

import java.util.*;

class Solution {
    private Map<int[], List<int[]>> graph;
    private Map<Integer, List<int[]>> nodesInComp;
    private Set<int[]> visited;

    private boolean overlap(int[] a, int[] b) {
        return a[0] <= b[1] && b[0] <= a[1];
    }

    private void buildGraph(int[][] intervals) {
        graph = new HashMap<>();
        for (int[] interval : intervals) {
            graph.put(interval, new LinkedList<>());
        }

        for (int[] interval1 : intervals) {
            for (int[] interval2 : intervals) {
                if (overlap(interval1, interval2)) {
                    graph.get(interval1).add(interval2);
                    graph.get(interval2).add(interval1);
                }
            }
        }
    }

    private int[] mergeNodes(List<int[]> nodes) {
        int minStart = nodes.get(0)[0];
        for (int[] node : nodes) {
            minStart = Math.min(minStart, node[0]);
        }

        int maxEnd = nodes.get(0)[1];
        for (int[] node : nodes) {
            maxEnd = Math.max(maxEnd, node[1]);
        }

        return new int[] { minStart, maxEnd };
    }

    private void markComponentDFS(int[] start, int compNumber) {
        Stack<int[]> stack = new Stack<>();
        stack.add(start);

        while (!stack.isEmpty()) {
            int[] node = stack.pop();
            if (!visited.contains(node)) {
                visited.add(node);

                if (nodesInComp.get(compNumber) == null) {
                    nodesInComp.put(compNumber, new LinkedList<>());
                }
                nodesInComp.get(compNumber).add(node);

                for (int[] child : graph.get(node)) {
                    stack.add(child);
                }
            }
        }
    }

    private void buildComponents(int[][] intervals) {
        nodesInComp = new HashMap<>();
        visited = new HashSet<>();
        int compNumber = 0;

        for (int[] interval : intervals) {
            if (!visited.contains(interval)) {
                markComponentDFS(interval, compNumber);
                compNumber++;
            }
        }
    }

    public int[][] merge(int[][] intervals) {
        buildGraph(intervals);
        buildComponents(intervals);

        List<int[]> merged = new LinkedList<>();
        for (int comp = 0; comp < nodesInComp.size(); comp++) {
            merged.add(mergeNodes(nodesInComp.get(comp)));
        }

        return merged.toArray(new int[merged.size()][]);
    }
}

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

Привет ребят! Мне в последнее время пишет очень много начинающих предпринимателей оценить их бизнес со стороны. Я как человек с 10 годами опыта в создании стартапов, как успеших так и абсолютно убыточных могу дать свою оценку. Я продавал свой бизнес в прибыль, и я также в убыток продовал несколько своих проектов. Готов с вами обсудить ваши идеи, но только сейчас, пока я пьян и на веселе. Напишите @kivaiko и мы созвонимся, чтобы я трезво оценивал ваши шансы и дал экспертные рекомендации.

Обучение Data Science. Комбо курсов со скидкой! 🎓Комплексные программы обучения для начинающих и продвинутых с упором на практику Узнать больше #реклама 16+ karpov.courses О рекламодателе

Задача: 412. Fizz Buzz Сложность: easy Учитывая целое число n, верните строковый массив answer (с индексом 1), где: answer[i] == "FizzBuzz", если i делится на 3 и 5. answer[i] == "Fizz", если i делится на 3. answer[i] == "Buzz", если i делится на 5. answer[i] == i (как строка), если ни одно из перечисленных условий не верно. Пример:

Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

👨‍💻 Алгоритм: 1⃣Создайте пустой список для хранения результата. 2⃣Пройдите по всем числам от 1 до n и для каждого числа выполните проверку: Если число делится на 3 и на 5, добавьте "FizzBuzz". Если число делится на 3, добавьте "Fizz". Если число делится на 5, добавьте "Buzz". Если ни одно из условий не выполнено, добавьте само число как строку. 3⃣Верните полученный список. 😎 Решение:

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

public class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> answer = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0 && i % 5 == 0) {
                answer.add("FizzBuzz");
            } else if (i % 3 == 0) {
                answer.add("Fizz");
            } else if (i % 5 == 0) {
                answer.add("Buzz");
            } else {
                answer.add(String.valueOf(i));
            }
        }
        return answer;
    }
}

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