Java | LeetCode

Партнёрская программа рекрутинга в Яндекс Еду Станьте партнёром Яндекс Еды по привлечению курьеров и получите кучу преимуществ: 💰Платим до 47 000 ₽ за успешного кандидата 📞Поддержка на всех этапах 📅Свободное расписание 📊Удобные инструменты для работы Приводите новых курьеров и получайте в среднем 250 000 ₽ в месяц! Зарегистрироваться #реклама 16+ eda.yandex.ru О рекламодателе

Задача: 124. Binary Tree Maximum Path Sum Сложность: hard Вам дан массив цен, где prices[i] — это цена данной акции в i-й день. Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить не более двух транзакций. Пример:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1

👨‍💻 Алгоритм: 1⃣Наивный способ — разделить массив на две части и в каждой найти ошибку. Но он потратил O(n²) времени, так как мы заново просматриваем массив для разделения каждой точки. 2⃣Оптимизируем с помощью динамического программирования: создаём два массива: leftProfits[i]— максимальная прибыль от 0 до i rightProfits[i]— максимальная прибыль от i до конца. Этот подход уменьшает сложность до O(n). 3⃣После расчета двух массивов суммируемая прибыль из левой и правой частей по каждому соединению: maxProfit = max(maxProfit, leftProfits[i] + rightProfits[i+1]) 😎 Решение:

class Solution {
    public int maxProfit(int[] prices) {
        int length = prices.length;
        if (length <= 1) return 0;

        int leftMin = prices[0];
        int rightMax = prices[length - 1];

        int[] leftProfits = new int[length];
        int[] rightProfits = new int[length + 1];

        for (int l = 1; l < length; ++l) {
            leftProfits[l] = Math.max(leftProfits[l - 1], prices[l] - leftMin);
            leftMin = Math.min(leftMin, prices[l]);

            int r = length - 1 - l;
            rightProfits[r] = Math.max(
                rightProfits[r + 1],
                rightMax - prices[r]
            );
            rightMax = Math.max(rightMax, prices[r]);
        }

        int maxProfit = 0;
        for (int i = 0; i < length; ++i) {
            maxProfit = Math.max(
                maxProfit,
                leftProfits[i] + rightProfits[i + 1]
            );
        }
        return maxProfit;
    }
}

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

REKONFA Live 6 ноября приглашаем всех, кто имеет отношение к маркетингу и рекламным технологиям, обсудить рынок, тренды, вызовы и их решения. С докладами на актуальные темы выступят лидеры индустрии и медийные спикеры. Принять участие можно офлайн и онлайн. Мероприятие бесплатное, нужно только зарегистрироваться. Зарегистрироваться #реклама 18+ ya.rekonfa.ru О рекламодателе

Задача: 1416. Restore The Array Сложность: hard Программа должна была напечатать массив целых чисел. Программа забыла напечатать пробелы, и массив напечатан как строка цифр s, и всё, что мы знаем, это что все числа в массиве были в диапазоне [1, k] и в массиве нет ведущих нулей. Учитывая строку s и целое число k, верните количество возможных массивов, которые могут быть напечатаны как s с использованием упомянутой программы. Так как ответ может быть очень большим, верните его по модулю 10^9 + 7. Пример:

Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]

👨‍💻 Алгоритм: 1⃣Создать массив dp размера m + 1, чтобы хранить значения dfs(x). 2⃣Для получения значения dfs(start), если dp[start] не равно нулю, вернуть его значение. Иначе: Если s[start] == 0, вернуть 0. Если start = m, вернуть 1. Инициализировать count = 0, чтобы считать количество возможных массивов. Перебрать все возможные конечные индексы end, и если s[start ~ end] представляет допустимое число, продолжить рекурсивный вызов dfs(end + 1) и обновить count как count += dfs(end + 1). Обновить dp[start] значением dfs(start). 3⃣Вернуть dfs(0). 😎 Решение:

class Solution {
    int mod = 1_000_000_007;

    private int dfs(int[] dp, int start, String s, int k) {
        if (dp[start] != 0)
            return dp[start];

        if (start == s.length())
            return 1;

        if (s.charAt(start) == '0')
            return 0;

        int count = 0;
        for (int end = start; end < s.length(); ++end) {
            String currNumber = s.substring(start, end + 1);
            if (Long.parseLong(currNumber) > k)
                break;
            count = (count + dfs(dp, end + 1, s, k)) % mod;
        }

        dp[start] = count;
        return count;
    }
    
    public int numberOfArrays(String s, int k) {
        int m = s.length();
        int[] dp = new int[m + 1];
        return dfs(dp, 0, s, k);
    }
}

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

Задача: 983. Minimum Cost For Tickets Сложность: medium Вы запланировали несколько поездок на поезде за год вперёд. Дни года, в которые вы будете путешествовать, заданы в виде целочисленного массива days. Каждый день — это целое число от 1 до 365. Билеты на поезд продаются тремя различными способами: однодневный билет продаётся за costs[0] долларов, семидневный билет продаётся за costs[1] долларов, и тридцатидневный билет продаётся за costs[2] долларов. Билеты позволяют путешествовать указанное количество дней подряд. Например, если мы покупаем семидневный билет на 2-й день, то мы можем путешествовать в течение 7 дней: 2, 3, 4, 5, 6, 7 и 8. Верните минимальное количество долларов, которое вам нужно, чтобы путешествовать каждый день, указанный в списке days. Пример:

Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation: For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total, you spent $11 and covered all the days of your travel.

👨‍💻 Алгоритм: 1⃣Создайте массив dp размером на один больше последнего дня, в который нужно путешествовать. Инициализируйте все значения -1, что означает, что ответ для этого дня ещё не был вычислен. Также создайте хэш-набор isTravelNeeded из days. 2⃣Создайте функцию solve, которая принимает аргумент currDay. Если currDay больше последнего дня, когда нужно путешествовать, просто верните 0, так как все дни уже покрыты. Если currDay отсутствует в isTravelNeeded, перейдите к currDay + 1. Если ответ для currDay в массиве dp не равен -1, это означает, что ответ уже был вычислен, поэтому просто верните его. 3⃣Найдите стоимость трёх билетов, которые можно использовать в этот день, добавьте соответствующую стоимость и обновите dp[currDay] соответственно в рекурсивном вызове. Вызовите solve, передав currDay = 1, и верните ответ. 😎 Решение:

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

class Solution {
    private Set<Integer> isTravelNeeded = new HashSet<>();
    
    private int solve(int[] dp, int[] days, int[] costs, int currDay) {
        if (currDay > days[days.length - 1]) {
            return 0;
        }
        
        if (!isTravelNeeded.contains(currDay)) {
            return solve(dp, days, costs, currDay + 1);
        }
        
        if (dp[currDay] != -1) {
            return dp[currDay];
        }
        
        int oneDay = costs[0] + solve(dp, days, costs, currDay + 1);
        int sevenDay = costs[1] + solve(dp, days, costs, currDay + 7);
        int thirtyDay = costs[2] + solve(dp, days, costs, currDay + 30);
        
        dp[currDay] = Math.min(oneDay, Math.min(sevenDay, thirtyDay));
        return dp[currDay];
    }
    
    public int mincostTickets(int[] days, int[] costs) {
        int lastDay = days[days.length - 1];
        int[] dp = new int[lastDay + 1];
        for (int i = 0; i <= lastDay; i++) {
            dp[i] = -1;
        }
        
        for (int day : days) {
            isTravelNeeded.add(day);
        }
        
        return solve(dp, days, costs, 1);
    }
}

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

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

Задача: 1005. Maximize Sum Of Array After K Negations Сложность: easy Учитывая целочисленный массив nums и целое число k, измените массив следующим образом: выберите индекс i и замените nums[i] на -nums[i]. Вы должны применить этот процесс ровно k раз. Вы можете выбрать один и тот же индекс i несколько раз. Верните наибольшую возможную сумму массива после его модификации таким образом. Пример:

Input: nums = [4,2,3], k = 1
Output: 5

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

import java.util.Arrays;

public class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        
        for (int i = 0; i < nums.length; i++) {
            if (k > 0 && nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        
        if (k % 2 == 1) {
            Arrays.sort(nums);
            nums[0] = -nums[0];
        }
        
        return Arrays.stream(nums).sum();
    }
}

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

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

Задача: 1044. Longest Duplicate Substring Сложность: hard Учитывая строку s, рассмотрите все дублированные подстроки: (смежные) подстроки s, которые встречаются 2 или более раз.Вхождения могут перекрываться. Верните любую дублированную подстроку, которая имеет наибольшую возможную длину.Если в s нет дублирующейся подстроки, ответом будет "". Пример:

Input: s = "banana"
Output: "ana"

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

public class Solution {
    public String longestDupSubstring(String s) {
        int n = s.length();
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) nums[i] = (int)s.charAt(i) - (int)'a';
        int a = 26;
        long modulus = (long)Math.pow(2, 32);
        
        int left = 1, right = n;
        String result = "";
        while (left < right) {
            int mid = (left + right) / 2;
            String dup = search(mid, a, modulus, n, nums);
            if (dup != null) {
                result = dup;
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return result;
    }

    private String search(int L, int a, long modulus, int n, int[] nums) {
        long h = 0;
        for (int i = 0; i < L; ++i) h = (h * a + nums[i]) % modulus;
        HashSet<Long> seen = new HashSet<>();
        seen.add(h);
        long aL = 1;
        for (int i = 1; i <= L; ++i) aL = (aL * a) % modulus;
        for (int start = 1; start < n - L + 1; ++start) {
            h = (h * a - nums[start - 1] * aL % modulus + modulus) % modulus;
            h = (h + nums[start + L - 1]) % modulus;
            if (seen.contains(h)) return s.substring(start, start + L);
            seen.add(h);
        }
        return null;
    }
}

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

Курс "Дизайн карточек для WB и Ozon". Бесплатно и с нуля Дизайнер карточек для маркетплейсов — востребованная и доходная профессия 💰 Научись ей бесплатно! - Бесплатный доступ - Разбор ДЗ от наставника - Мощные кейсы в портфолио Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

Задача: 379. Design Phone Directory Сложность: medium Создайте телефонный справочник, который изначально имеет maxNumbers пустых слотов для хранения номеров. Справочник должен хранить номера, проверять, пуст ли определенный слот, и освобождать данный слот. Реализуйте класс PhoneDirectory: PhoneDirectory(int maxNumbers) Инициализирует телефонный справочник с количеством доступных слотов maxNumbers. int get() Предоставляет номер, который никому не назначен. Возвращает -1, если номера недоступны. bool check(int number) Возвращает true, если слот доступен, и false в противном случае. void release(int number) Перераспределяет или освобождает номер слота. Пример:

Input
["PhoneDirectory", "get", "get", "check", "get", "check", "release", "check"]
[[3], [], [], [2], [], [2], [2], [2]]
Output
[null, 0, 1, true, 2, false, null, true]

👨‍💻 Алгоритм: 1⃣Инициализировать массив isSlotAvailable размером maxNumbers, установив значение true во всех индексах. 2⃣Метод get(): Проходить по массиву isSlotAvailable. Если найдется true на каком-либо индексе, установить isSlotAvailable[i] = false и вернуть i. Если доступных слотов нет, вернуть -1. Метод check(number): Вернуть значение isSlotAvailable[number]. 3⃣Метод release(number): Установить isSlotAvailable[number] = true. 😎 Решение:

public class PhoneDirectory {
    private boolean[] isSlotAvailable;

    public PhoneDirectory(int maxNumbers) {
        isSlotAvailable = new boolean[maxNumbers];
        for (int i = 0; i < maxNumbers; i++) {
            isSlotAvailable[i] = true;
        }
    }

    public int get() {
        for (int i = 0; i < isSlotAvailable.length; i++) {
            if (isSlotAvailable[i]) {
                isSlotAvailable[i] = false;
                return i;
            }
        }
        return -1;
    }

    public boolean check(int number) {
        return isSlotAvailable[number];
    }

    public void release(int number) {
        isSlotAvailable[number] = true;
    }
}

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

Задача: 59. Spiral Matrix II Сложность: medium Дано положительное целое число n. Сгенерируйте матрицу n на n, заполненную элементами от 1 до n^2 в спиральном порядке. Пример:

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

👨‍💻 Алгоритм: 1⃣Определение направлений движения: Для обхода матрицы используются четыре направления, формирующие слои. Создается массив dir, который хранит изменения координат x и y для каждого направления. Например, при движении слева направо (направление №1) координата x остается неизменной, а y увеличивается (x=0, y=1). При движении справа налево (направление №3) x остается неизменным, а y уменьшается (x=0, y=-1). 2⃣Перемещение по матрице: Переменные row и col представляют текущие координаты x и y соответственно. Они обновляются в зависимости от направления движения. Применяется предварительно определенный массив dir с изменениями координат x и y для каждого из четырех направлений. 3⃣Изменение направления: Направление изменяется, когда следующая строка или столбец в определенном направлении имеют ненулевое значение, что указывает на то, что они уже были пройдены. Переменная d представляет текущий индекс направления. Переход к следующему направлению в массиве dir осуществляется с использованием формулы (d+1)%4. Это позволяет вернуться к направлению 1 после завершения одного полного круга от направления 1 до направления 4. 😎 Решение:

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] result = new int[n][n];
        int cnt = 1;
        int dir[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
        int d = 0;
        int row = 0;
        int col = 0;
        while (cnt <= n * n) {
            result[row][col] = cnt++;
            int r = Math.floorMod(row + dir[d][0], n);
            int c = Math.floorMod(col + dir[d][1], n);

            if (result[r][c] != 0) d = (d + 1) % 4;

            row += dir[d][0];
            col += dir[d][1];
        }
        return result;
    }
}

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

Приглашаем на Yandex Neuro Scale В этом году главная конференция Yandex Cloud объединит разработчиков, архитекторов, инженеров и IT-руководителей, чтобы обменяться опытом и увидеть, как работают технологии, которые меняют индустрии. 7 тематических треков, 50+ докладов, реальные бизнес-кейсы и нетворкинг! ✨Участие бесплатное, нужно только зарегистрироваться!✨ Зарегистрироваться #реклама 16+ scale.yandex.cloud О рекламодателе Реклама на Яндексе

Задача: 668. Kth Smallest Number in Multiplication Table Сложность: hard Почти каждый использовал таблицу умножения. Таблица умножения размером m x n - это целочисленная матрица mat, где mat[i][j] == i * j (индексация начинается с 1). Даны три целых числа m, n и k. Верните k-й наименьший элемент в таблице умножения размером m x n. Пример:

Input: m = 3, n = 3, k = 5
Output: 3
Explanation: The 5th smallest number is 3.

👨‍💻 Алгоритм: 1⃣Установка границ поиска: Установите нижнюю границу left равной 1 и верхнюю границу right равной m * n. 2⃣Бинарный поиск: Используйте бинарный поиск, чтобы найти k-й наименьший элемент. Для каждого среднего значения mid, посчитайте количество элементов в таблице умножения, которые меньше или равны mid. 3⃣Проверка количества элементов: Если количество элементов меньше k, увеличьте нижнюю границу (left). Если количество элементов больше или равно k, уменьшите верхнюю границу (right). 😎 Решение:

public class Solution {
    public int findKthNumber(int m, int n, int k) {
        int left = 1, right = m * n;
        
        while (left < right) {
            int mid = (left + right) / 2;
            if (countLessEqual(m, n, mid) < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
    
    private int countLessEqual(int m, int n, int x) {
        int count = 0;
        for (int i = 1; i <= m; i++) {
            count += Math.min(x / i, n);
        }
        return count;
    }
}

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

Задача: 523. Continuous Subarray Sum Сложность: medium Дан целочисленный массив nums и целое число k. Верните true, если в nums есть хорошая подмассив, или false в противном случае. Хороший подмассив — это подмассив, который: имеет длину не менее двух, и сумма элементов подмассива является кратной k. Учтите: Подмассив — это непрерывная часть массива. Целое число x является кратным k, если существует целое число n такое, что x = n * k. Число 0 всегда является кратным k. Пример:

Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

👨‍💻 Алгоритм: 1⃣Инициализируйте целое число prefixMod = 0 и хеш-таблицу modSeen. Инициализируйте modSeen[0] значением -1, чтобы учесть начальное значение prefixMod. 2⃣Итеративно пройдите по всем элементам массива nums. 3⃣Вычислите prefixMod как (prefixMod + nums[i]) % k. Если prefixMod существует в хеш-таблице: Если размер самого длинного подмассива с модулем k составляет не менее 2, верните true. Если prefixMod не существует в хеш-таблице: Установите modSeen[prefixMod] = i. Если после завершения итерации не найден хороший подмассив, верните false. 😎 Решение:

import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int prefixMod = 0;
        Map<Integer, Integer> modSeen = new HashMap<>();
        modSeen.put(0, -1);
        
        for (int i = 0; i < nums.length; i++) {
            prefixMod = (prefixMod + nums[i]) % k;
            
            if (modSeen.containsKey(prefixMod)) {
                if (i - modSeen.get(prefixMod) > 1) {
                    return true;
                }
            } else {
                modSeen.put(prefixMod, i);
            }
        }
        
        return false;
    }
}

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

Задача: 1429. First Unique Number Сложность: medium У вас есть очередь целых чисел, необходимо извлечь первый уникальный элемент из очереди. Реализуйте класс FirstUnique: - FirstUnique(int[] nums) Инициализирует объект числами в очереди. - int showFirstUnique() возвращает значение первого уникального элемента в очереди и возвращает -1, если такого элемента нет. - void add(int value) вставляет значение в очередь. Пример:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output: 
[null,2,null,2,null,3,null,-1]
Explanation: 
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5);            // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2);            // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1

👨‍💻 Алгоритм: 1⃣Инициализируйте объект FirstUnique с числами в очереди, добавляя их в структуру данных для отслеживания уникальности и порядка. 2⃣Метод showFirstUnique возвращает значение первого уникального элемента в очереди, если таковой существует, или -1, если уникальных элементов нет. 3⃣Метод add добавляет новое значение в очередь. Если значение уже было добавлено ранее, обновляет его статус уникальности и удаляет его из множества уникальных значений, если оно больше не уникально. 😎 Решение:

class FirstUnique {
  
  private Set<Integer> setQueue = new LinkedHashSet<>();
  private Map<Integer, Boolean> isUnique = new HashMap<>();
  
  public FirstUnique(int[] nums) {
    for (int num : nums) {
      this.add(num);
    }
  }
    
  public int showFirstUnique() {
    if (!setQueue.isEmpty()) {
       return setQueue.iterator().next();
    }
    return -1;
  }
    
  public void add(int value) {
    if (!isUnique.containsKey(value)) {
      isUnique.put(value, true);
      setQueue.add(value);
    } else if (isUnique.get(value)) {
      isUnique.put(value, false);
      setQueue.remove(value);
    }
  }
}

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

Задача: 107. Binary Tree Level Order Traversal II Сложность: medium Дан корень бинарного дерева. Верните обход значений узлов снизу вверх по уровням (то есть слева направо, уровень за уровнем, от листа к корню). Пример:

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

👨‍💻 Алгоритм: 1⃣Инициализируйте список вывода levels. Длина этого списка определяет, какой уровень в данный момент обновляется. Вам следует сравнить этот уровень len(levels) с уровнем узла level, чтобы убедиться, что вы добавляете узел на правильный уровень. Если вы все еще находитесь на предыдущем уровне, добавьте новый уровень, вставив новый список в levels. 2⃣Добавьте значение узла в последний уровень в levels. 3⃣Рекурсивно обработайте дочерние узлы, если они не равны None, используя функцию helper(node.left / node.right, level + 1). 😎 Решение:

class Solution {
    List<List<Integer>> levels = new ArrayList<List<Integer>>();

    public void helper(TreeNode node, int level) {
        if (levels.size() == level) levels.add(new ArrayList<Integer>());
        levels.get(level).add(node.val);
        if (node.left != null) helper(node.left, level + 1);
        if (node.right != null) helper(node.right, level + 1);
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) return levels;
        helper(root, 0);
        Collections.reverse(levels);
        return levels;
    }
}

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

Задача: 520. Detect Capital Сложность: easy Мы определяем правильное использование заглавных букв в слове, когда выполняется одно из следующих условий: Все буквы в этом слове заглавные, как "USA". Все буквы в этом слове строчные, как "leetcode". Только первая буква в этом слове заглавная, как "Google". Дана строка word. Верните true, если использование заглавных букв в ней правильное. Пример:

Input: word = "USA"
Output: true

👨‍💻 Алгоритм: 1⃣Шаблон для первого случая в регулярном выражении: [A-Z]*, где [A-Z] соответствует одной заглавной букве от 'A' до 'Z', а * означает повторение предыдущего шаблона 0 или более раз. Этот шаблон представляет "Все заглавные буквы". 2⃣Шаблон для второго случая в регулярном выражении: [a-z]*, где [a-z] соответствует одной строчной букве от 'a' до 'z'. Этот шаблон представляет "Все строчные буквы". Шаблон для третьего случая в регулярном выражении: [A-Z][a-z]*, где первая буква заглавная, а остальные строчные. 3⃣Объедините эти три шаблона: [A-Z]*|[a-z]*|[A-Z][a-z]*, где | означает "или". Мы можем объединить второй и третий случай, получив . [a-z]*, где . соответствует любому символу. Итоговый шаблон: [A-Z]*|.[a-z]*. 😎 Решение:

import java.util.regex.*;

class Solution {
    public boolean detectCapitalUse(String word) {
        String pattern = "[A-Z]*|.[a-z]*";
        return Pattern.matches(pattern, word);
    }
}

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

Задача: 108. Convert Sorted Array to Binary Search Tree Сложность: easy Дан массив целых чисел nums, элементы которого отсортированы в порядке возрастания. Преобразуйте его в сбалансированное по высоте двоичное дерево поиска. Пример:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

👨‍💻 Алгоритм: 1⃣Инициализация функции помощника: Реализуйте функцию помощника helper(left, right), которая строит двоичное дерево поиска (BST) из элементов массива nums между индексами left и right. Если left > right, это означает, что элементов для построения поддерева нет, возвращаем None. 2⃣Выбор корня и разделение массива: Выберите элемент в середине для корня: p = (left + right) // 2. Инициализируйте корень: root = TreeNode(nums[p]). 3⃣Рекурсивное построение поддеревьев: Рекурсивно стройте левое поддерево: root.left = helper(left, p - 1). Рекурсивно стройте правое поддерево: root.right = helper(p + 1, right). В качестве результата возвращайте helper(0, len(nums) - 1), начиная с корня дерева. 😎 Решение:

class Solution {
    int[] nums;

    public TreeNode helper(int left, int right) {
        if (left > right) return null;

        int p = (left + right) / 2;
        TreeNode root = new TreeNode(nums[p]);
        root.left = helper(left, p - 1);
        root.right = helper(p + 1, right);
        return root;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        this.nums = nums;
        return helper(0, nums.length - 1);
    }
}

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

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