uz
Feedback
Java | LeetCode

Java | LeetCode

Kanalga Telegram’da o‘tish

Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv

Ko'proq ko'rsatish
6 508
Obunachilar
-424 soatlar
-197 kun
-5330 kun
Postlar arxiv
Многофункциональные модули ввода / вывода ELHART Alpha X Нужно расширить ПЛК дополнительными входами/выходами? Ищете надежные
Многофункциональные модули ввода / вывода ELHART Alpha X Нужно расширить ПЛК дополнительными входами/выходами? Ищете надежные модули RS-485 с Modbus RTU? Линейка ELHART Alpha-X – это: - Более 10 модификаций дискретных, аналоговых и комбинированных модулей; - Единая карта регистров для всех модулей; - Компактный корпус, ширина 18мм; - Питание и интерфейс RS-485 по шине; - Возможность настройки с помощью интерактивного конфигуратора; - До 31 модуля на одной шине; ⚡ Настройка адреса и скорости dip-переключателями; ⚡ Встроенные счётчики и частотомеры до 4 кГц; ⚡ Гальваническая изоляция интерфейса, входов и выходов от питания; ⚡ Точность измерения для унифицированных сигналов 0,1%, для датчиков температуры 0,25%; ⚡ Разработка и производство в РФ; Для тех, кто ценит функциональность и качество. Полная техническая поддержка. Узнать больше #реклама kipservis.ru О рекламодателе

Задача: 1048. Longest String Chain Сложность: easy Вам дан массив слов, каждое из которых состоит из строчных английских букв. СловоА является предшественником словаВ тогда и только тогда, когда мы можем вставить ровно одну букву в любое место словаА, не меняя порядка остальных символов, чтобы оно стало равно словуВ. Например, "abc" является предшественником "abac", а "cba" не является предшественником "bcad". Цепочка слов - это последовательность слов [word1, word2, ..., wordk] с k >= 1, где word1 является предшественником word2, word2 является предшественником word3 и так далее. Одиночное слово тривиально является цепочкой слов с k == 1. Верните длину самой длинной возможной цепочки слов со словами, выбранными из заданного списка слов. Пример:
Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
👨‍💻 Алгоритм: 1⃣Отсортируй список слов по длине. 2⃣Используй динамическое программирование для вычисления длины самой длинной цепочки для каждого слова. 3⃣Верни максимальную длину среди всех цепочек. 😎 Решение:
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int longestStrChain(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        Map<String, Integer> dp = new HashMap<>();
        int longestChain = 1;
        
        for (String word : words) {
            dp.put(word, 1);
            for (int i = 0; i < word.length(); i++) {
                StringBuilder sb = new StringBuilder(word);
                String predecessor = sb.deleteCharAt(i).toString();
                if (dp.containsKey(predecessor)) {
                    dp.put(word, Math.max(dp.get(word), dp.get(predecessor) + 1));
                }
            }
            longestChain = Math.max(longestChain, dp.get(word));
        }
        
        return longestChain;
    }
}
Ставь 👍 и забирай 📚 Базу знаний

Ведем набор учеников 3-10 классов на новый учебный год! Московская школа программистов - это не курсы, а школа с государственной лицензией, которая обучает детей IT с 2001 года. Мы сотрудничаем с МФТИ, НИУ ВШЭ, Яндекс и Физтехпарк Что получит ребенок, в результате обучения: - Участие и победы в олимпиадах всероссийского и международного уровня - Поступление в престижные технические вузы России и работу в известных IT-компаниях: Apple, Google, Yandex, Nvidia и других - Практику на реальных IT-проектах - Усидчивость, целеустремленность и умение работать в команде - Сдача ЕГЭ/ОГЭ на высокие баллы Сейчас идет набор в виртуальный класс. В этом формате, дети в небольших группах обучаются с преподавателем онлайн в реальном времени. Эффективно как очно. Позаботьтесь о том, чтобы ребенок стал востребованным IT-специалистом! Зарегистрироваться #реклама 16+ vc.informatics.ru О рекламодателе

Задача: 783. Minimum Distance Between BST Nodes Сложность: easy Дан корень дерева поиска (BST). Верните минимальную разницу между значениями любых двух различных узлов в дереве. Пример:
Input: root = [4,2,6,1,3]
Output: 1
👨‍💻 Алгоритм: 1⃣Инициализируйте minDistance значением MAX_VALUE; это переменная для хранения минимальной разницы. 2⃣Выполните обход дерева поиска в порядке возрастания (in-order traversal) и сохраните узлы в списке inorderNodes. 3⃣Итеративно проходите по списку inorderNodes, начиная с индекса 1. Для каждого элемента на позиции i найдите разницу с элементом на индексе i - 1 и соответствующим образом обновите переменную minDistance. Верните minDistance. 😎 Решение:
class Solution {
    List<Integer> inorderNodes = new ArrayList<>();
    
    private void inorderTraversal(TreeNode root) {
        if (root == null) return;
        
        inorderTraversal(root.left);
        inorderNodes.add(root.val);
        inorderTraversal(root.right);
    }
    
    public int minDiffInBST(TreeNode root) {
        inorderTraversal(root);
        
        int minDistance = Integer.MAX_VALUE;
        for (int i = 1; i < inorderNodes.size(); i++) {
            minDistance = Math.min(minDistance, inorderNodes.get(i) - inorderNodes.get(i - 1));
        }
        
        return minDistance;
    }
}
Ставь 👍 и забирай 📚 Базу знаний

Repost from easyoffer
⏳ Осталось всего 14 дней до завершения краудфандинга Сейчас самое подходящее время подключиться, если вы ждали или откладывал
Осталось всего 14 дней до завершения краудфандинга Сейчас самое подходящее время подключиться, если вы ждали или откладывали: Все, кто поддержат проект сейчас, до релиза, получат: 🚀 PRO-доступ на 1 год по цене месячной подписки ➕ Бета-доступ к EasyOffer 2.0 (конец мая) 👉 Поддержать: https://planeta.ru/campaigns/easyoffer

Переход на микросервисы с Kubernetes: что нужно учесть? 24 апреля на бесплатном вебинаре от СберТеха «К микросервисам через п
Переход на микросервисы с Kubernetes: что нужно учесть? 24 апреля на бесплатном вебинаре от СберТеха «К микросервисам через построение управляемой контейнерной среды» поговорим о требованиях к контейнеризации и их реализации в продуктах Platform V DropApp и Platform V Synapse Service Mesh. Что обсудим: ⚡ Почему важно выбрать правильный дистрибутив Kubernetes ⚡ Что входит в Platform V DropApp и каковы его основные преимущества ⚡ Какие инструменты помогают в защите контейнерных сред ⚡ Какие дополнительные ценности дает service mesh А также поделимся опытом эксплуатации продуктов в высоконагруженных средах и расскажем, как использование решений от одного поставщика позволяет упростить жизнь продуктовых команд. Регистрируйтесь и приходите 24 апреля! Зарегистрироваться #реклама 16+ platformv.sbertech.ru О рекламодателе

Задача: 1039. Minimum Score Triangulation of Polygon Сложность: medium У вас есть выпуклый n-сторонний многоугольник, каждая вершина которого имеет целочисленное значение. Вам дан целочисленный массив values, где values[i] - это значение i-й вершины (т.е. по часовой стрелке). Вы должны триангулировать многоугольник на n - 2 треугольника. Для каждого треугольника значение этого треугольника равно произведению значений его вершин, а общий балл триангуляции равен сумме этих значений для всех n - 2 треугольников в триангуляции. Верните наименьший возможный общий балл, который вы можете получить с помощью некоторой триангуляции многоугольника. Пример:
Input: values = [1,2,3]
Output: 6
👨‍💻 Алгоритм: 1⃣Инициализация: Создаем двумерный массив dp, где dp[i][j] будет хранить минимальный возможный общий балл триангуляции многоугольника, состоящего из вершин от i до j. 2⃣Основное заполнение dp: Проходим по всем возможным длинам подмногоугольников, начиная с треугольников (длина 3) до всего многоугольника (длина n). Для каждого подмногоугольника находим минимальный возможный общий балл, проверяя все возможные треугольники, которые могут быть образованы из этого подмногоугольника. Заполнение dp для каждого подмногоугольника: Для каждого подмногоугольника от i до j, и для каждой возможной вершины k между i и j, обновляем значение dp[i][j], как сумму минимальных значений триангуляций левой и правой частей подмногоугольника, а также значения текущего треугольника, образованного вершинами i, k и j. 3⃣Возврат результата: Ответ будет в dp[0][n-1], который хранит минимальный возможный общий балл триангуляции для всего многоугольника. 😎 Решение:
public class Solution {
    public int minScoreTriangulation(int[] values) {
        int n = values.length;
        int[][] dp = new int[n][n];
        
        for (int length = 2; length < n; ++length) {
            for (int i = 0; i < n - length; ++i) {
                int j = i + length;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i + 1; k < j; ++k) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j] + values[i] * values[j] * values[k]);
                }
            }
        }
        
        return dp[0][n - 1];
    }
}
Ставь 👍 и забирай 📚 Базу знаний

Бесплатное льготное обучение: 3 месяца Ищем людей, которые хотят обучиться и работать в IT-сфере из дома В конце обучения вы
Бесплатное льготное обучение: 3 месяца Ищем людей, которые хотят обучиться и работать в IT-сфере из дома В конце обучения вы пройдете стажировку и устроитесь на работу с зп от 150.000 рублей Образование, место жительства, трудовой стаж — не важны! Для старта нужно: — пройти короткий тест — заполнить анкету На что можно рассчитывать, после обучения: ✅ удаленная работа ✅ зп от 150.000 рублей (потолка нет) ✅ стабильная подработка, если не хотите уходить с основной работы ⚡ Осталось всего 47 бесплатных мест. Успейте пройти тест и оставить заявку: Узнать больше #реклама 16+ technolium.ru О рекламодателе

Задача: 1015. Smallest Integer Divisible by K Сложность: medium Задано целое положительное число k, необходимо найти длину наименьшего целого положительного числа n, такого, что n делится на k, и n содержит только цифру 1. Верните длину n. Если такого n не существует, верните -1. Примечание: n может не поместиться в 64-битное знаковое целое число. Пример:
Input: k = 1
Output: 1
👨‍💻 Алгоритм: 1⃣Использование остатка для нахождения числа с цифрами 1: Создайте переменную num и установите ее равной 1. Создайте переменную length и установите ее равной 1 для отслеживания длины числа. 2⃣Итеративное нахождение числа: Используйте цикл, чтобы умножать num на 10 и добавлять 1 в каждой итерации, и каждый раз вычисляйте остаток от деления num на k. Увеличивайте length на 1 в каждой итерации. Если в какой-то итерации num % k == 0, верните length. 3⃣Проверка бесконечного цикла: Если цикл длится слишком долго (например, 10^6 итераций), верните -1, чтобы предотвратить бесконечный цикл для случаев, когда решение не существует. 😎 Решение:
public class Solution {
    public int smallestRepunitDivByK(int k) {
        int num = 1, length = 1;
        Set<Integer> seen = new HashSet<>();
        
        while (num % k != 0) {
            if (seen.contains(num % k)) {
                return -1;
            }
            seen.add(num % k);
            num = (num * 10 + 1) % k;
            length++;
        }
        
        return length;
    }
}
Ставь 👍 и забирай 📚 Базу знаний

Бесплатное льготное обучение: 3 месяца Ищем людей, которые хотят обучиться и работать в IT-сфере из дома В конце обучения вы
Бесплатное льготное обучение: 3 месяца Ищем людей, которые хотят обучиться и работать в IT-сфере из дома В конце обучения вы пройдете стажировку и устроитесь на работу с зп от 150.000 рублей Образование, место жительства, трудовой стаж — не важны! Для старта нужно: — пройти короткий тест — заполнить анкету На что можно рассчитывать, после обучения: ✅ удаленная работа ✅ зп от 150.000 рублей (потолка нет) ✅ стабильная подработка, если не хотите уходить с основной работы ⚡ Осталось всего 47 бесплатных мест. Успейте пройти тест и оставить заявку: Узнать больше #реклама 16+ technolium.ru О рекламодателе

Задача: 1469. Find All The Lonely Nodes Сложность: easy В бинарном дереве одиночный узел — это узел, который является единственным ребёнком своего родительского узла. Корень дерева не является одиночным, так как у него нет родительского узла. Дано корневое значение бинарного дерева. Верните массив, содержащий значения всех одиночных узлов в дереве. Верните список в любом порядке. Пример:
Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
Output: [6,2]
Explanation: Light blue nodes are lonely nodes.
Please remember that order doesn't matter, [2,6] is also an acceptable answer.
👨‍💻 Алгоритм: 1⃣Определите рекурсивную функцию DFS, которая принимает корень дерева, булеву переменную isLonely и список одиночных узлов ans в качестве аргументов. Если корень равен NULL, завершите выполнение функции. 2⃣Если isLonely равен true, добавьте значение корня в список ans. Рекурсивно обрабатывайте левого потомка корня, устанавливая флаг isLonely в true, если правый потомок равен NULL, и правого потомка, устанавливая флаг isLonely в true, если левый потомок равен NULL. 3⃣Вызовите DFS с корнем и false в качестве значения isLonely. Верните ans. 😎 Решение:
class Solution {
    void DFS(TreeNode root, boolean isLonely, List<Integer> ans) {
        if (root == null) {
            return;
        }
        
        if (isLonely) {
            ans.add(root.val);
        }
        
        DFS(root.left, root.right == null, ans);
        DFS(root.right, root.left == null, ans);
    }
    
    public List<Integer> getLonelyNodes(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        DFS(root, false, ans);

        return ans;
    }
}
Ставь 👍 и забирай 📚 Базу знаний

Крупнейший университет искусственного интеллекта Учим использовать ChatGPT в профессиональных целях, создавать нейро-сотрудни
Крупнейший университет искусственного интеллекта Учим использовать ChatGPT в профессиональных целях, создавать нейро-сотрудников и зарабатывать на искусственном интеллекте. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 838. Push Dominoes Сложность: medium Есть n домино, выстроенные в линию, и каждое домино стоит вертикально. Вначале мы одновременно толкаем некоторые домино либо влево, либо вправо. Через каждую секунду каждое падающее влево домино толкает соседнее домино слева. Точно так же домино, падающие вправо, толкают соседние домино, стоящие справа. Когда вертикальное домино оказывается под воздействием падающих домино с обеих сторон, оно остаётся неподвижным из-за баланса сил. В рамках этой задачи мы будем считать, что падающее домино не передаёт дополнительную силу падающему или уже упавшему домино. Вам дано строковое представление начального состояния домино: dominoes[i] = 'L', если i-е домино толкнули влево, dominoes[i] = 'R', если i-е домино толкнули вправо, и dominoes[i] = '.', если i-е домино не было толкнуто. Верните строку, представляющую конечное состояние. Пример:
Input: dominoes = ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."
👨‍💻 Алгоритм: 1⃣Пройдите по строке и сохраните индексы и символы не пустых домино в массивы. 2⃣Добавьте фиктивные домино 'L' в начале и 'R' в конце для упрощения логики. 3⃣Обработайте промежутки между соседними домино, обновляя их состояния согласно правилам. 😎 Решение:
class Solution {
    public String pushDominoes(String dominoes) {
        int N = dominoes.length();
        int[] indexes = new int[N+2];
        char[] symbols = new char[N+2];
        int len = 1;
        indexes[0] = -1;
        symbols[0] = 'L';

        for (int i = 0; i < N; ++i)
            if (dominoes.charAt(i) != '.') {
                indexes[len] = i;
                symbols[len++] = dominoes.charAt(i);
            }

        indexes[len] = N;
        symbols[len++] = 'R';

        char[] ans = dominoes.toCharArray();
        for (int index = 0; index < len - 1; ++index) {
            int i = indexes[index], j = indexes[index+1];
            char x = symbols[index], y = symbols[index+1];
            char write;
            if (x == y) {
                for (int k = i+1; k < j; ++k)
                    ans[k] = x;
            } else if (x > y) { // RL
                for (int k = i+1; k < j; ++k)
                    ans[k] = k-i == j-k ? '.' : k-i < j-k ? 'R' : 'L';
            }
        }

        return String.valueOf(ans);
    }
}
Ставь 👍 и забирай 📚 Базу знаний

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по AI! Освой искусственный инт
Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по AI! Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 1003. Check If Word Is Valid After Substitutions Сложность: medium Дана строка s, определите, является ли она допустимой. Строка s допустима, если, начиная с пустой строки t = "", вы можете преобразовать t в s, выполнив следующую операцию любое количество раз: вставить строку "abc" в любую позицию в t. Более формально, t становится tleft + "abc" + tright, где t == tleft + tright. Обратите внимание, что tleft и tright могут быть пустыми. Верните true, если s - допустимая строка, иначе верните false. Пример:
Input: s = "aabcbc"
Output: true
👨‍💻 Алгоритм: 1⃣Проверка допустимости длины строки: Проверьте, что длина строки s кратна 3. Если нет, верните false. 2⃣Использование стека для проверки: Инициализируйте пустой стек. Проходите по каждому символу строки s. Если текущий символ является 'c', проверьте, что два предыдущих символа в стеке - это 'b' и 'a' соответственно. Если это так, удалите 'b' и 'a' из стека. Если нет, верните false. Если текущий символ не 'c', добавьте его в стек. 3⃣Проверка остатка стека: В конце, если стек пуст, верните true. Иначе верните false. 😎 Решение:
public class Solution {
    public boolean isValid(String s) {
        if (s.length() % 3 != 0) return false;

        Stack<Character> stack = new Stack<>();
        for (char ch : s.toCharArray()) {
            if (ch == 'c') {
                if (stack.size() < 2 || stack.pop() != 'b' || stack.pop() != 'a') {
                    return false;
                }
            } else {
                stack.push(ch);
            }
        }

        return stack.isEmpty();
    }
}
Ставь 👍 и забирай 📚 Базу знаний

Онлайн-магистратура: Науки о данных и искусственный инт. День открытых дверей 9 апреля в 19:00 мск | Онлайн Эксперты Яндекса
+1
Онлайн-магистратура: Науки о данных и искусственный инт. День открытых дверей 9 апреля в 19:00 мск | Онлайн Эксперты Яндекса и МИФИ расскажут об очной онлайн-магистратуре для карьеры в IT. Всё о поступлении и обучении, выступления экспертов, ответы на вопросы. Выбирайте всё: работу и учёбу, навыки и диплом магистра. Записаться онлайн #реклама 16+ praktikum.yandex.ru О рекламодателе

Задача: 1035. Uncrossed Lines Сложность: medium Вам даны два целочисленных массива nums1 и nums2. Запишем целые числа nums1 и nums2 (в том порядке, в котором они даны) на двух отдельных горизонтальных линиях. Мы можем провести соединительные линии: прямую линию, соединяющую два числа nums1[i] и nums2[j] так, что: nums1[i] == nums2[j], и проведенная линия не пересекает никакую другую соединительную (негоризонтальную) линию. Обратите внимание, что соединительная линия не может пересекаться даже в конечных точках (т.е, каждое число может принадлежать только одной соединительной линии). Верните максимальное количество соединительных линий, которые мы можем нарисовать таким образом. Пример:
Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
👨‍💻 Алгоритм: 1⃣Определение задачи как задачи о нахождении наибольшей общей подпоследовательности (LCS): Эта задача является классической задачей динамического программирования, где нам нужно найти максимальную длину наибольшей общей подпоследовательности (LCS) между nums1 и nums2. 2⃣Построение таблицы динамического программирования: Создайте двумерный массив dp, где dp[i][j] будет представлять длину наибольшей общей подпоследовательности для подмассивов nums1[0..i-1] и nums2[0..j-1]. Инициализируйте первый ряд и первый столбец нулями, так как если один из массивов пуст, LCS также будет пустым. 3⃣Заполнение таблицы динамического программирования: Пройдите по элементам массивов nums1 и nums2. Если текущие элементы совпадают, увеличьте значение ячейки dp[i][j] на 1 от диагонального значения dp[i-1][j-1]. Если не совпадают, установите значение ячейки dp[i][j] как максимальное из значений dp[i-1][j] и dp[i][j-1]. Результат будет находиться в ячейке dp[nums1.length][nums2.length]. 😎 Решение:
import java.util.*;

public class Solution {
    public int[][] allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {
        List<int[]> cells = new ArrayList<>();
        
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                int distance = Math.abs(r - rCenter) + Math.abs(c - cCenter);
                cells.add(new int[] { distance, r, c });
            }
        }
        
        cells.sort((a, b) -> Integer.compare(a[0], b[0]));
        
        int[][] result = new int[cells.size()][2];
        for (int i = 0; i < cells.size(); ++i) {
            result[i][0] = cells.get(i)[1];
            result[i][1] = cells.get(i)[2];
        }
        
        return result;
    }
}
Ставь 👍 и забирай 📚 Базу знаний

🔍Тестовое собеседование на Middle Java-разработчика завтра 9 апреля(уже завтра!) в 19:00 по мск приходи онлайн на открытое с
🔍Тестовое собеседование на Middle Java-разработчика завтра 9 апреля(уже завтра!) в 19:00 по мск приходи онлайн на открытое собеседование, чтобы посмотреть на настоящее интервью на Middle Java-разработчика. Как это будет: 📂 Илья Аров, старший разработчик в Т1, будет задавать реальные вопросы и задачи разработчику-добровольцу 📂 Илья будет комментировать каждый ответ респондента, чтобы дать понять чего от вас ожидает собеседующий на интервью 📂 В конце можно будет задать любой вопрос Илье Это бесплатно. Эфир проходит в рамках менторской программы от ШОРТКАТ для Java-разработчиков, которые хотят повысить свой грейд, ЗП и прокачать скиллы. Переходи в нашего бота, чтобы получить ссылку на эфир → @shortcut_sh_bot Реклама. ООО "ШОРТКАТ", ИНН: 9731139396, erid: 2Vtzqx3FgGy

Торгуйте на бирже с Альфа Форекс! Альфа Форекс - лицензированный форекс дилер, которому доверяют! - Торги от 0.01 лота - 41 в
Торгуйте на бирже с Альфа Форекс! Альфа Форекс - лицензированный форекс дилер, которому доверяют! - Торги от 0.01 лота - 41 валютная пара - 0% ввод/вывод - Пополнение через СБП Регистрируйтесь и начните зарабатывать на курсах валют уже сегодня! 💰 Узнать больше Финансовые услуги оказывает: ООО «Альфа-Форекс», АО "АЛЬФА-БАНК". #реклама alfaforex.ru О рекламодателе

Задача: 1038. Binary Search Tree to Greater Sum Tree Сложность: medium Получив корень двоичного дерева поиска (BST), преобразуйте его в большее дерево таким образом, чтобы каждый ключ исходного BST был заменен на исходный ключ плюс сумма всех ключей, превышающих исходный ключ в BST. Напомним, что двоичное дерево поиска - это дерево, удовлетворяющее следующим ограничениям: левое поддерево узла содержит только узлы с ключами меньше, чем ключ узла. Правое поддерево узла содержит только узлы с ключами больше, чем ключ узла. И левое, и правое поддеревья должны быть двоичными деревьями поиска. Пример:
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
👨‍💻 Алгоритм: 1⃣Обратный обход in-order: Пройдите по дереву в порядке "правый, корень, левый" (обратный in-order обход). Это обеспечит посещение узлов в порядке убывания их значений. 2⃣Накопление суммы: Во время обхода поддерживайте переменную для хранения накопленной суммы. На каждом узле добавляйте значение узла к накопленной сумме и обновляйте значение узла этой накопленной суммой. 3⃣Преобразование узлов: Преобразуйте значение каждого узла в накопленную сумму. 😎 Решение:
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private int sum = 0;
    
    public TreeNode bstToGst(TreeNode root) {
        reverseInorder(root);
        return root;
    }
    
    private void reverseInorder(TreeNode node) {
        if (node == null) return;
        reverseInorder(node.right);
        sum += node.val;
        node.val = sum;
        reverseInorder(node.left);
    }
}
Ставь 👍 и забирай 📚 Базу знаний