Java | LeetCode

Задача: 297. Serialize and Deserialize Binary Tree Сложность: hard Сериализация — это процесс преобразования структуры данных или объекта в последовательность битов, чтобы их можно было сохранить в файле или буфере памяти или передать по сетевому соединению для последующего восстановления в той же или другой компьютерной среде. Разработайте алгоритм для сериализации и десериализации бинарного дерева. Нет ограничений на то, как ваш алгоритм сериализации/десериализации должен работать. Вам нужно просто гарантировать, что бинарное дерево может быть сериализовано в строку, и эта строка может быть десериализована в исходную структуру дерева. Уточнение: формат ввода/вывода такой же, как в LeetCode для сериализации бинарного дерева. Вам не обязательно придерживаться этого формата, так что будьте креативны и придумайте свои подходы. Пример:

    
        Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]{}
    

👨‍💻 Алгоритм: 1⃣Сериализация дерева: Используйте рекурсивный обход дерева в порядке root -> left subtree -> right subtree. Для каждого узла добавляйте его значение в строку сериализации. Если узел пустой, добавляйте "None". 2⃣Пример: Начните с корня, узел 1, строка сериализации становится "1,". Переходите к левому поддереву с корнем 2, строка сериализации становится "1,2,". Для узла 2, посетите его левый узел 3 ("1,2,3,None,None,") и правый узел 4 ("1,2,3,None,None,4,None,None"). Возвращайтесь к корню 1 и посетите его правое поддерево, узел 5 ("1,2,3,None,None,4,None,None,5,None,None,"). 3⃣Десериализация строки: Разделите строку на список значений. Используйте рекурсивную функцию для создания узлов дерева, извлекая значения из списка и восстанавливая структуру дерева. Если значение "None", узел пустой. 😎 Решение:

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

public class Codec {
    private void rserialize(TreeNode root, StringBuilder str) {
        if (root == null) {
            str.append("null,");
        } else {
            str.append(root.val).append(",");
            rserialize(root.left, str);
            rserialize(root.right, str);
        }
    }

    public String serialize(TreeNode root) {
        StringBuilder str = new StringBuilder();
        rserialize(root, str);
        return str.toString();
    }

    private TreeNode rdeserialize(LinkedList<String> data) {
        if (data.get(0).equals("null")) {
            data.remove(0);
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(data.remove(0)));
        root.left = rdeserialize(data);
        root.right = rdeserialize(data);
        return root;
    }{}
    

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

Открой мощь новых MSI с GeForce RTX 50 Серия NVIDIA GeForce RTX 50 в ноутбуках MSI — это квантовый скачок в мире мощности. Игры на максималках, 3D-рендер без ожиданий, монтаж видео в реальном времени и искусственный интеллект, работающий с небывалой скоростью. Эта техника создана не просто для задач — она их уничтожает. Будь в центре производительности нового поколения. MSI с RTX 50 — когда ты не хочешь ждать, а действуешь. Узнать больше #реклама msi.gm О рекламодателе

Задача: 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons Сложность: hard Вам даны три целых числа n, m и k. Рассмотрим следующий алгоритм для нахождения максимального элемента в массиве положительных целых чисел:

    
        maximum_value = -1
maximum_index = -1
search_cost = 0
n = arr.length
for (i = 0; i < n; i++){
      if (maximum_value  < arr[i]){
           maximum_value  = arr[i]
           maximum_index = i
           search_cost = search_cost + 1
      }
}
return maximum_index{}
    

Вам необходимо построить массив arr, который имеет следующие свойства: arr содержит ровно n целых чисел. 1 <= arr[i] <= m, где (0 <= i < n). После применения указанного алгоритма к arr, значение search_cost равно k. Верните количество способов построить массив arr с учетом указанных условий. Так как ответ может быть очень большим, ответ должен быть вычислен по модулю 10^9 + 7. Пример:

    
        Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]{}
    

👨‍💻 Алгоритм: 1⃣Инициализация и базовые случаи: Инициализируем 3D массив dp размером [n+1][m+1][k+1]. Устанавливаем базовые случаи: dp[n][...][0] = 1. 2⃣Итерация и обновление массива dp: Проходим в обратном порядке по индексам i от n-1 до 0, по maxSoFar от m до 0 и по remain от 0 до k. Для каждого из этих значений обновляем dp массив, используя предыдущие результаты для вычисления текущих значений. 3⃣Возврат результата: Возвращаем значение dp[0][0][k], которое является решением исходной задачи. 😎 Решение:

    
        class Solution {    
    public int numOfArrays(int n, int m, int k) {    
        int[][][] dp = new int[n + 1][m + 1][k + 1];
        int MOD = (int) 1e9 + 7;
        
        for (int num = 0; num < dp[0].length; num++) {
            dp[n][num][0] = 1;
        }
        
        for (int i = n - 1; i >= 0; i--) {
            for (int maxSoFar = m; maxSoFar >= 0; maxSoFar--) {
                for (int remain = 0; remain <= k; remain++) {
                    int ans = 0;
                    for (int num = 1; num <= maxSoFar; num++) {
                        ans = (ans + dp[i + 1][maxSoFar][remain]) % MOD;
                    }
                    
                    if (remain > 0) {
                        for (int num = maxSoFar + 1; num <= m; num++) {
                            ans = (ans + dp[i + 1][num][remain - 1]) % MOD;
                        }
                    }
                    
                    dp[i][maxSoFar][remain] = ans;
                }
            }
        }

        return dp[0][0][k];
    }
}{}
    

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

Задача: 565. Array Nesting Сложность: medium Дан массив целых чисел nums длиной n, где nums является перестановкой чисел в диапазоне [0, n - 1]. Вы должны построить множество s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ...} при соблюдении следующего правила: Первый элемент в s[k] начинается с выбора элемента nums[k] с индексом k. Следующий элемент в s[k] должен быть nums[nums[k]], затем nums[nums[nums[k]]], и так далее. Мы прекращаем добавлять элементы непосредственно перед тем, как в s[k] появится дубликат. Верните длину самого длинного множества s[k]. Пример:

    
        Input: nums = [5,4,0,3,1,6,2]
Output: 4
Explanation: 
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
One of the longest sets s[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}{}
    

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

    
        public class Solution {
    public int arrayNesting(int[] nums) {
        boolean[] visited = new boolean[nums.length];
        int maxLength = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                int start = i;
                int count = 0;
                while (!visited[start]) {
                    visited[start] = true;
                    start = nums[start];
                    count++;
                }
                maxLength = Math.max(maxLength, count);
            }
        }
        
        return maxLength;
    }
}{}
    

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

Задача: 157. Read N Characters Given Read4 Сложность: easy Предположим, что у вас есть файл, и вы можете читать файл только с помощью данного метода read4. Реализуйте метод для чтения n символов. Метод read4: API read4 читает четыре последовательных символа из файла, затем записывает эти символы в массив буфера buf4. Возвращаемое значение — количество фактически прочитанных символов. Обратите внимание, что у read4 есть собственный указатель файла, аналогично FILE *fp в C. Определение read4: Параметр: char[] buf4 Возвращает: int buf4[] — это назначение, а не источник. Результаты из read4 будут скопированы в buf4[]. Метод read: Используя метод read4, реализуйте метод read, который читает n символов из файла и сохраняет их в массиве буфера buf. Учтите, что вы не можете напрямую манипулировать файлом. Возвращаемое значение — количество фактически прочитанных символов. Определение read: Параметры: char[] buf, int n Возвращает: int buf[] — это назначение, а не источник. Вам нужно будет записать результаты в buf[]. Примечание: Учтите, что вы не можете напрямую манипулировать файлом. Файл доступен только для чтения с помощью read4, но не для read. Функция read будет вызываться только один раз для каждого тестового случая. Вы можете предполагать, что массив буфера назначения, buf, гарантированно имеет достаточно места для хранения n символов. Пример:

    
        Input: file = "abc", n = 4
Output: 3
Explanation: After calling your read method, buf should contain "abc". We read a total of 3 characters from the file, so return 3.
Note that "abc" is the file's content, not buf. buf is the destination buffer that you will have to write the results to.{}
    

👨‍💻 Алгоритм: 1⃣Инициализация и подготовка: Инициализируйте переменные: copiedChars = 0 для подсчета скопированных символов и readChars = 4 для подсчета прочитанных символов из файла. Начальное значение readChars установлено в 4, что позволяет использовать условие readChars != 4 в качестве маркера конца файла (EOF). Создайте внутренний буфер из 4 символов: buf4. 2⃣Чтение и копирование символов: Пока количество скопированных символов меньше N (copiedChars < n) и еще есть символы в файле (readChars == 4): Прочитайте символы из файла во внутренний буфер buf4 с помощью метода read4(buf4). Копируйте символы из внутреннего буфера buf4 в основной буфер buf по одному. Увеличивайте copiedChars после каждого скопированного символа. 3⃣Завершение процесса: Если количество скопированных символов достигло N (copiedChars == n), прервите процесс копирования. Верните copiedChars как результат функции, указывающий на количество успешно скопированных символов в основной буфер buf. 😎 Решение:

    
        public class Solution extends Reader4 {
    public int read(char[] buf, int n) {
        int copiedChars = 0, readChars = 4;
        char[] buf4 = new char[4];

        while (copiedChars < n && readChars == 4) {
            readChars = read4(buf4);

            for (int i = 0; i < readChars; ++i) {
                if (copiedChars == n) return copiedChars;
                buf[copiedChars] = buf4[i];
                ++copiedChars;
            }
        }
        return copiedChars;
    }
}{}
    

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

Задача: 152. Maximum Product Subarray Сложность: medium Дан массив целых чисел nums. Найдите подмассив, который имеет наибольший произведение, и верните это произведение. Тестовые случаи созданы таким образом, что ответ поместится в 32-битное целое число. Пример:

    
        Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.{}
    

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

    
        class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length == 0) return 0;

        int result = nums[0];

        for (int i = 0; i < nums.length; i++) {
            int accu = 1;
            for (int j = i; j < nums.length; j++) {
                accu *= nums[j];
                result = Math.max(result, accu);
            }
        }

        return result;
    }
}{}
    

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

Старт продаж санаторно-курортного комплекса в Крыму! ❤️Оазиз круглогодичного оздоровления и отдыха в Крыму в апартаментах премиум-класса! Инвестируйте в комплекс, соединяющий в себе оздоровление и отдых 5* и получайте пассивный доход на сдаче от 2.5 млн рублей в год! Мощная инфраструктура: - Первая береговая линия с собственным пляжем площадью 30 ГА! - Вход в море всегда пологий -Spa центр и круглогодичный бассейн -Панорамный ресторан на 16 этаже - Собственный санаторий на территории: ✨Включает в себя популярные программы оздоровления с применением местных лечебных факторов, таких как широко известные Сакские грязи А также: физиотерапия, массаж и многое другое! 🏠90% номеров с видом на морскую акваторию и горы Крыма! 📱Получите презентацию комплекса + инвестиционную стратегию от брокера! Получить предложение #реклама 16+ mrqz.me О рекламодателе

Задача: 1276. Number of Burgers with No Waste of Ingredients Сложность: medium Даны два целых числа tomatoSlices и cheeseSlices. Ингредиенты разных бургеров таковы: Jumbo Burger: 4 ломтика помидора и 1 ломтик сыра. Small Burger: 2 ломтика помидора и 1 ломтик сыра. Верните [total_jumbo, total_small] так, чтобы количество оставшихся tomatoSlices было равно 0, а количество оставшихся cheeseSlices было равно 0. Если невозможно сделать так, чтобы оставшиеся tomatoSlices и cheeseSlices были равны 0, верните []. Пример:

    
        Input: tomatoSlices = 16, cheeseSlices = 7
Output: [1,6]{}
    

👨‍💻 Алгоритм: 1⃣Проверьте, возможно ли решить задачу, убедившись, что tomatoSlices четно и находится в допустимых пределах. 2⃣Решите систему уравнений: 4J + 2S = tomatoSlices J + S = cheeseSlices 3⃣Если решение существует, верните его, иначе верните пустой список. 😎 Решение:

    
        public class Solution {
    public List<Integer> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        if (tomatoSlices % 2 != 0 || tomatoSlices < 2 * cheeseSlices || tomatoSlices > 4 * cheeseSlices) {
            return new ArrayList<>();
        }
        int total_jumbo = (tomatoSlices - 2 * cheeseSlices) / 2;
        int total_small = cheeseSlices - total_jumbo;
        return Arrays.asList(total_jumbo, total_small);
    }
}{}
    

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

👨👨👨👨👨👨👨👨👨👨 Каналы с Junior IT вакансиями и стажировками Подписывайся и забирай свой оффер 🤘 1. Стажировки и вакансии по России и миру 2. IT вакансии по СНГ 3. IT стажировки по СНГ 4. ИИ-ассистент для автооткликов 5. DIGITAL и IT стажировки и вакансии 6. IT стажировки в топовых компаниях мира 7. Удалённые IT вакансии и стажировки 8. Python вакансии и стажировки 9. БИГТЕХ вакансии и стажировки 10. Design вакансии и стажировки 11. QA вакансии и стажировки 12. Junior вакансии и стажировки 13. Frontend вакансии и вопросы собесов 14. Вакансии и стажировки для аналитиков 15. Вакансии в русских стартапах за границей 16. Вакансии и стажировки для DevOps 17. Вакансии, которых нет на ХХ.РУ

Задача: 1498. Number of Subsequences That Satisfy the Given Sum Condition Сложность: medium Вам дан массив целых чисел nums и целое число target. Верните количество непустых подпоследовательностей массива nums, таких что сумма минимального и максимального элемента в них меньше или равна target. Так как ответ может быть слишком большим, верните его по модулю 10^9 + 7. Пример:

    
        Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9){}
    

👨‍💻 Алгоритм: 1⃣Инициализация и подготовка: Инициализируйте переменные answer равным 0 и n как длину массива nums. Отсортируйте массив nums. Подготовьте массив power для хранения степеней двойки до n по модулю 10^9+7. 2⃣Итерация и бинарный поиск: Для каждого индекса left от 0 до n - 1 выполните бинарный поиск, чтобы найти самый правый индекс right, где nums[right] <= target - nums[left]. Если left <= right, добавьте количество допустимых подпоследовательностей к answer. 3⃣Возврат результата: Верните answer по модулю 10^9+7. 😎 Решение:

    
        class Solution {
    public static int binarySearchRightmost(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
    
    public int numSubseq(int[] nums, int target) {
        int n = nums.length;
        int mod = 1_000_000_007;
        Arrays.sort(nums);
        
        int[] power = new int[n];
        power[0] = 1;
        for (int i = 1; i < n; ++i) {
            power[i] = (power[i - 1] * 2) % mod;
        }
        
        int answer = 0;

        for (int left = 0; left < n; left++) {
            int right = binarySearchRightmost(nums, target - nums[left]) - 1;
            if (right >= left) {
                answer += power[right - left];
                answer %= mod;
            }
        }
        return answer;
    }
}{}
    

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