Java | LeetCode

Задача: 1261. Find Elements in a Contaminated Binary Tree Сложность: medium Дано двоичное дерево со следующими правилами: root.val == 0 Если treeNode.val == x и treeNode.left != null, то treeNode.left.val == 2 * x + 1 Если treeNode.val == x и treeNode.right != null, то treeNode.right.val == 2 * x + 2 Теперь двоичное дерево загрязнено, то есть все treeNode.val были изменены на -1. Реализация класса FindElements: FindElements(TreeNode* root) Инициализирует объект с загрязненным двоичным деревом и восстанавливает его. bool find(int target) Возвращает true, если целевое значение существует в восстановленном двоичном дереве. Пример:

    
        Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output
[null,false,true]{}
    

👨‍💻 Алгоритм: 1⃣Восстановление дерева: Начните с корневого узла, установите его значение на 0. Затем рекурсивно восстановите значения для всех узлов, используя правила left.val = 2 * parent.val + 1 и right.val = 2 * parent.val + 2. 2⃣Сохранение значений: Используйте структуру данных, такую как множество (set), для хранения всех восстановленных значений узлов. 3⃣Поиск значений: Реализуйте метод поиска, который проверяет, содержится ли целевое значение в множестве восстановленных значений. 😎 Решение:

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

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

public class FindElements {
    private TreeNode root;
    private Set<Integer> values = new HashSet<>();
    
    public FindElements(TreeNode root) {
        this.root = root;
        root.val = 0;
        values.add(0);
        recover(root);
    }
    
    private void recover(TreeNode node) {
        if (node.left != null) {
            node.left.val = 2 * node.val + 1;
            values.add(node.left.val);
            recover(node.left);
        }
        if (node.right != null) {
            node.right.val = 2 * node.val + 2;
            values.add(node.right.val);
            recover(node.right);
        }
    }
    
    public boolean find(int target) {
        return values.contains(target);
    }
}{}
    

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

Ищу желающих заполнять карточки товаров на ВБ! Работа полностью на удаленке с зп до150 000 рублей в месяц. Без опыта, нужен только телефон, занятость 3-6 часов в день. Всему обучат на бесплатном курсе и после возьму на работу: ✅ 3 дня уроков по 30 минут ✅ Домашки с проверкой и оплатой бонусами ✅ Плачу 10 тыс за каждую выполненную домашку Все кто пройдет курс, получат сертификат от школы с образовательной лицензией. ⚡ Набор заканчивается завтра. 👍 Для регистрации жмите кнопку "Зарегистрироваться": Зарегистрироваться #реклама 16+ course.wildmanager.ru О рекламодателе

Задача: 1663. Smallest String With A Given Numeric Value Сложность: medium Числовое значение строчной буквы определяется ее позицией (начиная с 1) в алфавите, поэтому числовое значение a равно 1, числовое значение b равно 2, числовое значение c равно 3 и так далее. Числовое значение строки, состоящей из строчных букв, определяется как сумма числовых значений ее символов. Например, числовое значение строки "abe" равно 1 + 2 + 5 = 8. Вам даны два целых числа n и k. Верните лексикографически наименьшую строку длиной n с числовым значением, равным k. Обратите внимание, что строка x лексикографически меньше строки y, если x идет перед y в словарном порядке, то есть либо x является префиксом y, либо, если i - первая позиция, где x[i] != y[i], то x[i] идет перед y[i] в алфавитном порядке. Пример:

    
        Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.{}
    

👨‍💻 Алгоритм: 1⃣Построить строку или массив символов result для хранения выбранных символов для каждой позиции. 2⃣Итерация от позиции 1 до n и заполнение символом каждой позиции: Найти позиции, которые нужно заполнить, исключая текущую позицию, задаваемую переменной positionsLeft как n - position - 1. Если значение k больше, чем positionsLeft * 26, зарезервировать числовое значение 26 (символ z) для всех оставшихся позиций positionsLeft. Вычислить значение текущей позиции, заданное переменной add, как k - (positionsLeft * 26). Вычесть рассчитанное значение add из k, чтобы найти оставшееся значение k после заполнения текущей позиции. Иначе, заполнить текущую позицию символом a, имеющим числовое значение 1. Вычесть 1 из k, чтобы найти оставшееся значение k после заполнения текущей позиции. 3⃣Повторять процесс, пока все позиции не будут заполнены. 😎 Решение:

    
        class Solution {
    public String getSmallestString(int n, int k) {
        char[] result = new char[n];
        for (int position = 0; position < n; position++) {
            int positionsLeft = (n - position - 1);
            if (k > positionsLeft * 26) {
                int add = k - (positionsLeft * 26);
                result[position] = (char) ('a' + add - 1);
                k -= add;
            } else {
                result[position] = 'a';
                k--;
            }
        }
        return new String(result);
    }
}{}
    

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

📺 Уникальная база IT собеседований 456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 679. 24 Game Сложность: hard Дан массив целых чисел cards длиной 4. У вас есть четыре карты, каждая из которых содержит число в диапазоне от 1 до 9. Вам нужно расположить числа на этих картах в математическом выражении, используя операторы ['+', '-', '*', '/'] и скобки '(' и ')' так, чтобы получить значение 24. Вы ограничены следующими правилами: Оператор деления '/' представляет собой реальное деление, а не целочисленное деление. Например, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12. Каждая операция выполняется между двумя числами. В частности, мы не можем использовать '-' как унарный оператор. Например, если cards = [1, 1, 1, 1], выражение "-1 - 1 - 1 - 1" не допускается. Вы не можете объединять числа вместе. Например, если cards = [1, 2, 1, 2], выражение "12 + 12" недопустимо. Вернуть true, если вы можете получить такое выражение, которое оценивается в 24, и false в противном случае. Пример:

    
        Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24{}
    

👨‍💻 Алгоритм: 1⃣Создайте функцию generatePossibleResults(a, b), которая возвращает массив результатов всех возможных математических операций над двумя числами. 2⃣ Создайте функцию checkIfResultReached(list), чтобы проверить, можем ли мы достичь результата 24, используя текущий массив list. Сначала проверьте базовые условия: если размер массива равен 1, верните true, если результат равен 24, иначе верните false. 3⃣Если размер массива больше 1, выберите любые два числа из списка, выполните все математические операции над ними, создайте новый список с обновленными элементами и снова вызовите рекурсивную функцию с этим новым списком. Если ни одна комбинация не приводит к результату 24, верните false. Вызовите checkIfResultReached с исходным списком карт. 😎 Решение:

    
        import java.util.*;

class Solution {
    public List<Double> generatePossibleResults(double a, double b) {
        List<Double> res = new ArrayList<>(Arrays.asList(a + b, a - b, b - a, a * b));
        if (a != 0) res.add(b / a);
        if (b != 0) res.add(a / b);
        return res;
    }

    public boolean checkIfResultReached(List<Double> list) {
        if (list.size() == 1) return Math.abs(list.get(0) - 24) <= 0.1;

        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                List<Double> newList = new ArrayList<>();
                for (int k = 0; k < list.size(); k++) {
                    if (k != i && k != j) newList.add(list.get(k));
                }
                for (double res : generatePossibleResults(list.get(i), list.get(j))) {
                    newList.add(res);
                    if (checkIfResultReached(newList)) return true;
                    newList.remove(newList.size() - 1);
                }
            }
        }
        return false;
    }

    public boolean judgePoint24(int[] cards) {
        List<Double> list = new ArrayList<>();
        for (int card : cards) {
            list.add((double) card);
        }
        return checkIfResultReached(list);
    }
}{}
    

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

Ищу желающих выполнять задачи с помощью ИИ! Работа полностью на удаленке с зп до 150 000 рублей в месяц. Без опыта, нужен только телефон, занятость 3-6 часов в день. Всему обучат на бесплатном курсе и после возьму на работу: ✅ 3 дня уроков по 30 минут ✅ Домашки с проверкой и оплатой бонусами ✅ Плачу 10 тыс за каждую выполненную домашку Все кто пройдет курс, получат сертификат от школы с образовательной лицензией. ⚡ Набор заканчивается завтра. 👍 Для регистрации жмите кнопку "Зарегистрироваться": Зарегистрироваться #реклама 16+ ganstaagency.com О рекламодателе

Задача: 84. Largest Rectangle in Histogram Сложность: hard Дан массив целых чисел heights, представляющий высоту столбцов гистограммы, где ширина каждого столбца равна 1. Верните площадь наибольшего прямоугольника в гистограмме. Пример:

    
        Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.{}
    

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

    
        public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxarea = 0;
        for (int i = 0; i < heights.length; i++) {
            for (int j = i; j < heights.length; j++) {
                int minheight = Integer.MAX_VALUE;
                for (int k = i; k <= j; k++) minheight = Math.min(
                    minheight,
                    heights[k]
                );
                maxarea = Math.max(maxarea, minheight * (j - i + 1));
            }
        }
        return maxarea;
    }
}{}
    

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

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

Задача: 367. Valid Perfect Square Сложность: easy Дано положительное целое число num, вернуть true, если num является идеальным квадратом, или false в противном случае. Идеальный квадрат — это целое число, являющееся квадратом целого числа. Другими словами, это произведение некоторого целого числа на само себя. Вы не должны использовать какие-либо встроенные библиотечные функции, такие как sqrt. Пример:

    
        Input: num = 16
Output: true
Explanation: We return true because 4 * 4 = 16 and 4 is an integer.{}
    

👨‍💻 Алгоритм: 1⃣Если num < 2, вернуть True. Установить левую границу в 2, а правую границу в num / 2. 2⃣Пока left <= right, взять x = (left + right) / 2, вычислить guess_squared = x * x и сравнить его с num: Если guess_squared == num, вернуть True. Если guess_squared > num, сдвинуть правую границу right = x - 1. В противном случае сдвинуть левую границу left = x + 1. 3⃣Если вышли из цикла, вернуть False. 😎 Решение:

    
        class Solution {
    public boolean isPerfectSquare(int num) {
        if (num < 2) {
            return true;
        }

        long x = num / 2;
        while (x * x > num) {
            x = (x + num / x) / 2;
        }
        return x * x == num;
    }
}{}
    

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

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