Java | LeetCode

Задача: 310. Minimum Height Trees Сложность: medium Дерево — это неориентированный граф, в котором любые две вершины соединены ровно одним путем. Другими словами, любое связное граф без простых циклов является деревом. Дано дерево из n узлов, помеченных от 0 до n - 1, и массив из n - 1 ребер, где edges[i] = [ai, bi] указывает на наличие неориентированного ребра между узлами ai и bi в дереве. Вы можете выбрать любой узел дерева в качестве корня. Когда вы выбираете узел x в качестве корня, дерево имеет высоту h. Среди всех возможных корневых деревьев те, которые имеют минимальную высоту (то есть min(h)), называются деревьями с минимальной высотой (MHT). Верните список всех меток корней MHT. Вы можете вернуть ответ в любом порядке. Высота корневого дерева — это количество ребер на самом длинном нисходящем пути между корнем и листом. Пример:

    
        Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.{}
    

👨‍💻 Алгоритм: 1⃣Создание списка смежности Создайте список смежности, представляющий граф. 2⃣Удаление листьев Начните с удаления всех листьев. Лист — это узел с одной гранью. В каждой итерации удаляйте текущие листья и обновляйте список смежности. Новые листья будут вершинами, которые стали листьями после удаления предыдущих листьев. 3⃣Повторение процесса Повторяйте процесс до тех пор, пока не останется два или менее узлов. Эти узлы будут корнями деревьев с минимальной высотой (MHT). 😎 Решение:

    
        public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return Collections.singletonList(0);
        
        List<Set<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new HashSet<>());
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }
        
        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (adj.get(i).size() == 1) leaves.add(i);
        }
        
        int remainingNodes = n;
        while (remainingNodes > 2) {
            remainingNodes -= leaves.size();
            List<Integer> newLeaves = new ArrayList<>();
            for (int leaf : leaves) {
                int neighbor = adj.get(leaf).iterator().next();
                adj.get(neighbor).remove(leaf);
                if (adj.get(neighbor).size() == 1) newLeaves.add(neighbor);
            }
            leaves = newLeaves;
        }
        
        return leaves;
    }
}{}
    

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

Вы готовы получить код молодости? Сыворотка Double Serum нового поколения эффективно борется с признаками старения кожи и прицельно воздействует на более чем 50 биологических маркеров, обеспечивая комплексный антивозрастной эффект. Двойная текстура имитирует гидролипидную мантию кожи, поддерживая ее естественный баланс. Подходит даже чувствительной коже. ✨Усиленное воздействие на жизненно важные функции кожи ✨27 мощных ингредиентов ✨95% ингредиентов натурального происхождения День за днем сыворотка сокращает признаки старения, заметно разглаживает кожу и улучшает ее состояние. Теперь вы знаете, как повернуть время вспять! Узнать больше #реклама ozon.ru О рекламодателе

Задача: 641. Design Circular Deque Сложность: medium Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае. Пример:

    
        Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]{}
    

👨‍💻 Алгоритм: 1⃣Инициализация и проверка состояний: Реализуйте конструктор для инициализации кольцевой двусторонней очереди заданного размера и методы для проверки пустоты и полноты очереди. 2⃣Операции вставки: Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры. 3⃣Операции удаления: Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди. 😎 Решение:

    
        public class MyCircularDeque {
    private int[] deque;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    public MyCircularDeque(int k) {
        this.capacity = k;
        this.deque = new int[k];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }

    public boolean insertFront(int value) {
        if (isFull()) return false;
        front = (front - 1 + capacity) % capacity;
        deque[front] = value;
        size++;
        return true;
    }

    public boolean insertLast(int value) {
        if (isFull()) return false;
        deque[rear] = value;
        rear = (rear + 1) % capacity;
        size++;
        return true;
    }

    public boolean deleteFront() {
        if (isEmpty()) return false;
        front = (front + 1) % capacity;
        size--;
        return true;
    }

    public boolean deleteLast() {
        if (isEmpty()) return false;
        rear = (rear - 1 + capacity) % capacity;
        size--;
        return true;
    }

    public int getFront() {
        if (isEmpty()) return -1;
        return deque[front];
    }

    public int getRear() {
        if (isEmpty()) return -1;
        return deque[(rear - 1 + capacity) % capacity];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }
}{}
    

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

Задача: 680. Valid Palindrome II Сложность: easy Дана строка s, вернуть true, если s может быть палиндромом после удаления не более одного символа из нее. Пример:

    
        Input: s = "aba"
Output: true{}
    

👨‍💻 Алгоритм: 1⃣Создайте вспомогательную функцию checkPalindrome, которая принимает строку s и два указателя i и j. Эта функция возвращает логическое значение, указывающее, является ли подстрока s.substring(i, j) палиндромом. 2⃣Инициализируйте два указателя: i = 0 и j = s.length() - 1. Пока i < j, проверьте, совпадают ли символы в индексах i и j. Если нет, это значит, что нам нужно удалить один из этих символов. 3⃣Попробуйте оба варианта, используя checkPalindrome. Верните true, если либо checkPalindrome(s, i, j - 1), либо checkPalindrome(s, i + 1, j) возвращает true. Если мы выходим из цикла while, это значит, что исходная строка является палиндромом. Поскольку нам не нужно было использовать удаление, следует вернуть true. 😎 Решение:

    
        class Solution {
    private boolean checkPalindrome(String s, int i, int j) {
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    
    public boolean validPalindrome(String s) {
        int i = 0;
        int j = s.length() - 1;
        
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return checkPalindrome(s, i, j - 1) || checkPalindrome(s, i + 1, j);
            }
            i++;
            j--;
        }
        
        return true;
    }
}{}
    

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

Задача: 1008. Construct Binary Search Tree from Preorder Traversal Сложность: medium Дается массив целых чисел preorder, который представляет собой обход BST (т.е, гарантируется, что для заданных тестовых случаев всегда можно найти дерево двоичного поиска с заданными требованиями. Дерево двоичного поиска - это двоичное дерево, в котором для каждого узла любой потомок Node.left имеет значение строго меньше, чем Node.val, а любой потомок Node.right имеет значение строго больше, чем Node.val. При обходе бинарного дерева в предварительном порядке сначала выводится значение узла, затем обход Node.left, затем обход Node.right. Пример:

    
        Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]{}
    

👨‍💻 Алгоритм: 1⃣Инициализация переменных и функций: Создайте класс узла дерева TreeNode с атрибутами val, left и right. Инициализируйте индекс, который будет отслеживать текущую позицию в массиве preorder. 2⃣Рекурсивная функция для построения дерева: Создайте рекурсивную функцию constructBST с аргументами preorder, lower и upper, которые будут ограничивать значения узлов для текущей ветви дерева. Если текущий индекс выходит за границы массива preorder, верните null. Получите текущее значение из preorder и проверьте, находится ли оно в пределах допустимого диапазона [lower, upper]. Если нет, верните null. 3⃣Создание узла и рекурсивное построение поддеревьев: Создайте новый узел с текущим значением и увеличьте индекс. Рекурсивно вызовите функцию constructBST для создания левого поддерева с обновленным верхним пределом (upper равным значению текущего узла). Рекурсивно вызовите функцию constructBST для создания правого поддерева с обновленным нижним пределом (lower равным значению текущего узла). Верните созданный узел. 😎 Решение:

    
        public class Solution {
    private int index = 0;

    public TreeNode bstFromPreorder(int[] preorder) {
        return constructBST(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private TreeNode constructBST(int[] preorder, int lower, int upper) {
        if (index == preorder.length) {
            return null;
        }

        int val = preorder[index];
        if (val < lower || val > upper) {
            return null;
        }

        index++;
        TreeNode root = new TreeNode(val);
        root.left = constructBST(preorder, lower, val);
        root.right = constructBST(preorder, val, upper);
        return root;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}{}
    

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

Задача: 1031. Maximum Sum of Two Non-Overlapping Subarrays Сложность: medium Если задан целочисленный массив nums и два целых числа firstLen и secondLen, верните максимальную сумму элементов в двух непересекающихся подмассивах с длинами firstLen и secondLen. Массив с длиной firstLen может находиться до или после массива с длиной secondLen, но они должны быть непересекающимися. Подмассив - это смежная часть массива. Пример:

    
        Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20{}
    

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

    
        public class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        return Math.max(maxSumNonOverlap(nums, firstLen, secondLen), maxSumNonOverlap(reverse(nums), secondLen, firstLen));
    }
    
    private int maxSumNonOverlap(int[] nums, int firstLen, int secondLen) {
        int n = nums.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        int[] maxFirst = new int[n];
        for (int i = firstLen - 1; i < n; ++i) {
            maxFirst[i] = Math.max((i > 0 ? maxFirst[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - firstLen]);
        }
        
        int[] maxSecond = new int[n];
        for (int i = secondLen - 1; i < n; ++i) {
            maxSecond[i] = Math.max((i > 0 ? maxSecond[i - 1] : 0), prefix[i + 1] - prefix[i + 1 - secondLen]);
        }
        
        int maxSum = 0;
        for (int i = firstLen + secondLen - 1; i < n; ++i) {
            maxSum = Math.max(maxSum, maxFirst[i - secondLen] + (prefix[i + 1] - prefix[i + 1 - secondLen]));
        }
        
        return maxSum;
    }
    
    private int[] reverse(int[] nums) {
        int n = nums.length;
        int[] reversed = new int[n];
        for (int i = 0; i < n; ++i) {
            reversed[i] = nums[n - i - 1];
        }
        return reversed;
    }
}{}
    

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

Задача: 425. Word Squares Сложность: hard Дан массив уникальных строк words, верните все квадраты слов, которые можно построить из этих слов. Одно и то же слово из words можно использовать несколько раз. Вы можете вернуть ответ в любом порядке. Последовательность строк образует допустимый квадрат слов, если k-я строка и k-й столбец читаются одинаково, где 0 <= k < max(количество строк, количество столбцов). Например, последовательность слов ["ball", "area", "lead", "lady"] образует квадрат слов, потому что каждое слово читается одинаково как по горизонтали, так и по вертикали. Пример:

    
        Input: words = ["area","lead","wall","lady","ball"]
Output: [["ball","area","lead","lady"],["wall","area","lead","lady"]]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).{}
    

👨‍💻 Алгоритм: 1⃣Постройте хеш-таблицу из входных слов. Функция buildPrefixHashTable(words) создает хеш-таблицу, где ключами являются префиксы, а значениями - списки слов, начинающихся с этих префиксов. 2⃣При помощи функции getWordsWithPrefix(prefix) осуществляйте запросы к хеш-таблице для получения всех слов, обладающих данным префиксом. Это ускоряет поиск подходящих слов для построения квадрата слов. 3⃣Используйте алгоритм с возвратом для построения квадрата слов. В каждый момент времени проверьте, совпадают ли строки и столбцы. Если они совпадают, продолжайте добавлять слова; если нет, вернитесь к предыдущему состоянию и попробуйте другое слово. 😎 Решение:

    
        class Solution {
    int N = 0;
    String[] words = null;
    HashMap<String, List<String>> prefixHashTable = null;

    public List<List<String>> wordSquares(String[] words) {
        this.words = words;
        this.N = words[0].length();

        List<List<String>> results = new ArrayList<>();
        this.buildPrefixHashTable(words);

        for (String word : words) {
            LinkedList<String> wordSquares = new LinkedList<>();
            wordSquares.addLast(word);
            this.backtracking(1, wordSquares, results);
        }
        return results;
    }

    protected void backtracking(int step, LinkedList<String> wordSquares, List<List<String>> results) {
        if (step == N) {
            results.add(new ArrayList<>(wordSquares));
            return;
        }

        StringBuilder prefix = new StringBuilder();
        for (String word : wordSquares) {
            prefix.append(word.charAt(step));
        }

        for (String candidate : this.getWordsWithPrefix(prefix.toString())) {
            wordSquares.addLast(candidate);
            this.backtracking(step + 1, wordSquares, results);
            wordSquares.removeLast();
        }
    }

    protected void buildPrefixHashTable(String[] words) {
        this.prefixHashTable = new HashMap<>();

        for (String word : words) {
            for (int i = 1; i < this.N; ++i) {
                String prefix = word.substring(0, i);
                List<String> wordList = this.prefixHashTable.get(prefix);
                if (wordList == null) {
                    wordList = new ArrayList<>();
                    wordList.add(word);
                    this.prefixHashTable.put(prefix, wordList);
                } else {
                    wordList.add(word);
                }
            }
        }
    }

    protected List<String> getWordsWithPrefix(String prefix) {
        List<String> wordList = this.prefixHashTable.get(prefix);
        return (wordList != null ? wordList : new ArrayList<>());
    }
}{}
    

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

Гайд для маркетологов по эффективным онлайн-встречам Как CMO, PR и digital-маркетологам повысить результативность брейнштормов, совещаний и планерок с командой с помощью онлайн-встреч? Гайд МТС Линк: 37 страниц полезных материалов, чек-листов и кейсов для эффективных видеовстреч и совещаний. ✅ В гайде: - Как создать постоянную ссылку на регулярные встречи с подрядчиками, командой или агентствами и подключаться в 2 клика; - Как управлять встречей и завершить ее четкими договоренностями с ИИ-расшифровкой голоса в текст; - Как проводить кастдевы, брейнштормы и формулировать гипотезы с помощью 15+ шаблонов в онлайн-досках МТС Линк; - Как разом пригласить всех участников на синк таким образом, чтобы все пришли. Бонус внутри: 5 способов не выгореть от бесконечных синков. ✨ Скачайте гайд бесплатно по ссылке Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 164. Maximum Gap Сложность: easy Дан массив целых чисел nums. Верните максимальную разницу между двумя последовательными элементами в его отсортированной форме. Если массив содержит менее двух элементов, верните 0. Необходимо написать алгоритм, который работает за линейное время и использует линейное дополнительное пространство. Пример:

    
        Input: nums = [3,6,9,1]
Output: 3
Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.{}
    

👨‍💻 Алгоритм: 1⃣Инициализация: Определите минимальное и максимальное значения в массиве для расчета возможного максимального интервала (разрыва) между элементами в идеально распределенном массиве. Вычислите размер ведра (bucket size), необходимый для размещения всех элементов массива так, чтобы если массив был равномерно распределен, каждый ведер должен содержать хотя бы один элемент. Размер ведра = (max_value - min_value) / (количество элементов - 1). 2⃣Размещение элементов в ведрах: Создайте ведра для хранения минимальных и максимальных значений каждого ведра. Используйте формулу для распределения каждого элемента в соответствующем ведре на основе его значения. Игнорируйте пустые ведра при расчете максимального интервала. 3⃣Вычисление максимального интервала: Пройдите через ведра и вычислите максимальный интервал, сравнивая минимальное значение текущего непустого ведра с максимальным значением предыдущего непустого ведра. Максимальный интервал будет наибольшей разницей между "минимальными" и "максимальными" значениями последовательных непустых ведер. 😎 Решение:

    
        public class Solution {
    public int maximumGap(int[] nums) {
        if (
            nums == null || nums.length < 2
        ) return 0; 
        Arrays.sort(nums);

        int maxGap = 0;

        for (int i = 0; i < nums.length - 1; i++) maxGap = Math.max(
            nums[i + 1] - nums[i],
            maxGap
        );

        return maxGap;
    }
}{}
    

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

Задача: 1274. Number of Ships in a Rectangle Сложность: hard (Эта задача является интерактивной.) Каждый корабль находится в целочисленной точке моря, представленной картезианской плоскостью, и каждая целочисленная точка может содержать не более 1 корабля. У вас есть функция Sea.hasShips(topRight, bottomLeft), которая принимает две точки в качестве аргументов и возвращает true, если в прямоугольнике, представленном этими двумя точками, есть хотя бы один корабль, включая на границе. Учитывая две точки: правый верхний и левый нижний углы прямоугольника, верните количество кораблей в этом прямоугольнике. Гарантируется, что в прямоугольнике находится не более 10 кораблей. Решения, содержащие более 400 обращений к hasShips, будут оцениваться как "Неправильный ответ". Кроме того, любые решения, пытающиеся обойти судью, приведут к дисквалификации. Пример:

    
        Input: 
ships = [[1,1],[2,2],[3,3],[5,5]], topRight = [4,4], bottomLeft = [0,0]
Output: 3{}
    

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

    
        public class Solution {
    public int countShips(Sea sea, Point topRight, Point bottomLeft) {
        if (!sea.hasShips(topRight, bottomLeft)) {
            return 0;
        }
        if (topRight.x == bottomLeft.x && topRight.y == bottomLeft.y) {
            return 1;
        }
        int midX = (topRight.x + bottomLeft.x) / 2;
        int midY = (topRight.y + bottomLeft.y) / 2;
        return countShips(sea, new Point(midX, midY), bottomLeft) +
               countShips(sea, topRight, new Point(midX + 1, midY + 1)) +
               countShips(sea, new Point(midX, topRight.y), new Point(bottomLeft.x, midY + 1)) +
               countShips(sea, new Point(topRight.x, midY), new Point(midX + 1, bottomLeft.y));
    }
}{}
    

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