C/C++ | LeetCode

Задача: 739. Daily Temperatures Сложность: medium Задав массив целых чисел temperature, представляющих дневные температуры, верните массив answer, такой, что answer[i] - это количество дней, которые нужно подождать после i-го дня, чтобы температура стала теплее. Если в будущем не существует дня, для которого это возможно, сохраните answer[i] == 0. Пример:

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

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

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int n = T.size();
        vector<int> answer(n, 0);
        stack<int> stack;
        
        for (int i = 0; i < n; i++) {
            while (!stack.empty() && T[i] > T[stack.top()]) {
                int j = stack.top();
                stack.pop();
                answer[j] = i - j;
            }
            stack.push(i);
        }
        
        return answer;
    }
};

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

Задача: 40. Combination Sum II Сложность: medium Дан массив candidates и число target. Найдите все уникальные комбинации, где сумма элементов равна target. Каждое число можно использовать только один раз. Пример:

Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [[1,1,6],[1,2,5],[1,7],[2,6]]

👨‍💻 Алгоритм: 1⃣Отсортировать и подсчитать количество каждого уникального элемента, чтобы избежать дубликатов. 2⃣Запустить рекурсивный backtrack, на каждом шаге выбирая доступный элемент, уменьшая его частоту и остаток target. 3⃣Если remain == 0 — сохранить комбинацию; иначе — откатить шаг (уменьшение глубины, восстановление частоты и удаление элемента из комбинации). 😎 Решение:

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> results;
        vector<int> comb;
        map<int, int> counter;
        for (int candidate : candidates) {
            counter[candidate]++;
        }
        vector<pair<int, int>> counterList(counter.begin(), counter.end());
        backtrack(comb, target, 0, counterList, results);
        return results;
    }

private:
    void backtrack(vector<int>& comb, int remain, int curr,
                   vector<pair<int, int>>& counter,
                   vector<vector<int>>& results) {
        if (remain == 0) {
            results.push_back(comb);
            return;
        } else if (remain < 0) {
            return;
        }

        for (int nextCurr = curr; nextCurr < counter.size(); ++nextCurr) {
            auto& [candidate, freq] = counter[nextCurr];
            if (freq == 0) continue;

            comb.push_back(candidate);
            --freq;

            backtrack(comb, remain - candidate, nextCurr, counter, results);

            ++freq;
            comb.pop_back();
        }
    }
};

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

Задача: 258. Add Digits Сложность: easy Дано целое число num. Необходимо многократно складывать его цифры, пока не получится однозначное число, и вернуть его. Пример:

Input: num = 38
Output: 2
Объяснение: 3 + 8 = 11 → 1 + 1 = 2

👨‍💻 Алгоритм: 1⃣Используем переменную digital_root, в которую будем поэтапно добавлять цифры num. 2⃣В цикле: Добавляем num % 10 к digital_root Делим num на 10 (удаляем последнюю цифру) Если num == 0 и digital_root > 9, значит, число всё ещё не однозначное — присваиваем digital_root в num и обнуляем digital_root, продолжая цикл. 3⃣Как только число становится однозначным, возвращаем его. 😎 Решение:

class Solution {
public:
    int addDigits(int num) {
        int digital_root = 0;
        while (num > 0) {
            digital_root += num % 10;
            num /= 10;
            if (num == 0 && digital_root > 9) {
                num = digital_root;
                digital_root = 0;
            }
        }
        return digital_root;
    }
};

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

Задача: 1530. Number of Good Leaf Nodes Pairs Сложность: medium Вам дан корень бинарного дерева и целое число distance. Пара двух различных листовых узлов бинарного дерева называется хорошей, если длина кратчайшего пути между ними меньше или равна distance. Верните количество хороших пар листовых узлов в дереве. Пример:

Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.

👨‍💻 Алгоритм: 1⃣Инициализируйте список смежности для преобразования дерева в граф и множество для хранения листовых узлов. Используйте вспомогательный метод traverseTree для обхода дерева, чтобы построить граф и найти листовые узлы. В параметрах поддерживайте текущий узел, а также родительский узел. Если текущий узел является листом, добавьте его в множество. В списке смежности добавьте текущий узел в список соседей родительского узла и наоборот. Рекурсивно вызовите traverseTree для левого и правого дочернего узла текущего узла. 2⃣Инициализируйте переменную ans для подсчета количества хороших пар листовых узлов. Итеративно переберите каждый листовой узел в множестве. Запустите BFS для текущего листового узла. BFS можно прервать досрочно, как только будут обнаружены все узлы, находящиеся на расстоянии от текущего листового узла. Увеличьте ans для каждого листового узла, найденного в каждом запуске BFS. 3⃣Верните ans / 2. Мы считаем каждую пару дважды, поэтому нужно разделить на 2, чтобы получить фактическое количество. 😎 Решение:

class Solution {
public:
    int countPairs(TreeNode* root, int distance) {
        unordered_map<TreeNode*, vector<TreeNode*>> graph;
        unordered_set<TreeNode*> leafNodes;
        traverseTree(root, nullptr, graph, leafNodes);
        int ans = 0;
        for (auto leaf : leafNodes) {
            queue<TreeNode*> bfsQueue;
            unordered_set<TreeNode*> seen;
            bfsQueue.push(leaf);
            seen.insert(leaf);
            for (int i = 0; i <= distance; ++i) {
                int size = bfsQueue.size();
                for (int j = 0; j < size; ++j) {
                    TreeNode* currNode = bfsQueue.front();
                    bfsQueue.pop();
                    if (leafNodes.count(currNode) && currNode != leaf) {
                        ++ans;
                    }
                    for (auto neighbor : graph[currNode]) {
                        if (!seen.count(neighbor)) {
                            bfsQueue.push(neighbor);
                            seen.insert(neighbor);
                        }
                    }
                }
            }
        }
        return ans / 2;
    }

private:
    void traverseTree(TreeNode* currNode, TreeNode* prevNode,
                      unordered_map<TreeNode*, vector<TreeNode*>>& graph, unordered_set<TreeNode*>& leafNodes) {
        if (!currNode) {
            return;
        }
        if (!currNode->left && !currNode->right) {
            leafNodes.insert(currNode);
        }
        if (prevNode) {
            graph[prevNode].push_back(currNode);
            graph[currNode].push_back(prevNode);
        }
        traverseTree(currNode->left, currNode, graph, leafNodes);
        traverseTree(currNode->right, currNode, graph, leafNodes);
    }
};

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

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

Задача: 1539. Kth Missing Positive Number Сложность: easy Дан массив arr из положительных целых чисел, отсортированных в строго возрастающем порядке, и целое число k. Верните k-й положительный целочисленный элемент, который отсутствует в этом массиве. Пример:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

👨‍💻 Алгоритм: 1⃣Проверьте, является ли k-й отсутствующий номер меньше первого элемента массива. Если это так, верните k. Уменьшите k на количество положительных чисел, отсутствующих до начала массива: k -= arr[0] - 1. 2⃣Итерируйтесь по элементам массива. На каждом шаге вычисляйте количество отсутствующих положительных чисел между i+1-м и i-м элементами: currMissing = arr[i + 1] - arr[i] - 1. Сравните k с currMissing. Если k <= currMissing, то число для возврата находится между arr[i + 1] и arr[i], и вы можете его вернуть: arr[i] + k. В противном случае уменьшите k на currMissing и продолжайте. 3⃣Если элемент, который нужно вернуть, больше последнего элемента массива, верните его: arr[n - 1] + k. 😎 Решение:

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        if (k <= arr[0] - 1) {
            return k;
        }
        k -= arr[0] - 1;
        int n = arr.size();
        for (int i = 0; i < n - 1; ++i) {
            int currMissing = arr[i + 1] - arr[i] - 1;
            if (k <= currMissing) {
                return arr[i] + k;
            }
            k -= currMissing;
        }
        return arr[n - 1] + k;
    }
};

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

Как получить максимальный доход от недвижимости? Инвестиционные квартиры в Лимасоле 📅 Вебинар: 2 октября 19:00 по Мск Вебинар точно для вас, если: ✅ Вы хотите инвестировать в недвижимость с прогнозируемым потенциалом. ✅ Получить стабильный и высокий доход в евро. ✅ Рассматриваете Кипр для инвестиций, ПМЖ, релокации семьи или спокойной жизни у моря. ✅Цените эксклюзивные предложения, которых нет в открытом доступе. Ждем вас на вебинаре! Зарегистрироваться #реклама 16+ webinar.tranio.ru О рекламодателе

Задача: 531. Lonely Pixel I Сложность: medium Дано изображение размером m x n, состоящее из чёрных ('B') и белых ('W') пикселей. Верните количество чёрных одиночных пикселей. Чёрный одиночный пиксель — это символ 'B', расположенный в такой позиции, где в той же строке и в том же столбце нет других чёрных пикселей. Пример:

Input: picture = [["W","W","B"],["W","B","W"],["B","W","W"]]
Output: 3
Explanation: All the three 'B's are black lonely pixels.

👨‍💻 Алгоритм: 1⃣ Подсчёт количества чёрных пикселей в строках и столбцах: Пройдите по всей матрице picture, для каждой чёрной клетки (x, y) увеличивайте rowCount[x] и colCount[y] на 1. 2⃣ Поиск одиночных чёрных пикселей: Снова пройдите по всей матрице и для каждой чёрной клетки (x, y) проверьте значения rowCount[x] и colCount[y]. Если оба значения равны 1, увеличьте переменную answer на 1. 3⃣ Возврат результата: Верните answer. 😎 Решение:

class Solution {
public:
    int findLonelyPixel(vector<vector<char>>& picture) {
        int n = picture.size();
        int m = picture[0].size();
        
        vector<int> rowCount(n, 0);
        vector<int> columnCount(m, 0);
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (picture[i][j] == 'B') {
                    rowCount[i]++;
                    columnCount[j]++;
                }
            }
        }
        
        int answer = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (picture[i][j] == 'B' && rowCount[i] == 1 && columnCount[j] == 1) {
                    answer++;
                }
            }
        }
        
        return answer;
    }
};

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

Задача: 1376. Time Needed to Inform All Employees Сложность: medium В компании работает n сотрудников, каждому из которых присвоен уникальный идентификатор от 0 до n - 1. Руководитель компании имеет идентификатор headID. У каждого сотрудника есть один непосредственный начальник, указанный в массиве manager, где manager[i] — это непосредственный начальник i-го сотрудника, manager[headID] = -1. Также гарантируется, что отношения подчинения образуют древовидную структуру. Руководитель компании хочет сообщить всем сотрудникам компании срочную новость. Он сообщит своим непосредственным подчиненным, а они сообщат своим подчиненным и так далее, пока все сотрудники не узнают о срочной новости. i-й сотрудник нуждается в informTime[i] минутах, чтобы сообщить всем своим непосредственным подчиненным (т.е. через informTime[i] минут все его непосредственные подчиненные могут начать распространять новость). Верните количество минут, необходимых для того, чтобы сообщить всем сотрудникам о срочной новости. Пример:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

👨‍💻 Алгоритм: 1⃣Создайте список смежности adjList; индекс i будет хранить смежные узлы для сотрудника с идентификатором i. 2⃣Итерируйте по сотрудникам от 0 до N - 1, и для каждого сотрудника i добавляйте ребро manager[i] -> i, если manager[i] не равен -1. 3⃣Начните выполнение DFS с узла headID и временем 0 для каждого узла как curr. Обновите максимальное время maxTime, сравнив его с текущим временем. Итерируйте по смежным узлам curr и для каждого смежного узла выполните DFS с временем time + informTime[curr]. Когда DFS завершится, верните maxTime. 😎 Решение:

class Solution {
public:
    int maxTime = INT_MIN;
    
    void DFS(vector<int> adjList[], vector<int>& informTime, int curr, int time) {
        maxTime = max(maxTime, time);
        for (int adjacent : adjList[curr]) { 
            DFS(adjList, informTime, adjacent, time + informTime[curr]);
        }
    }
    
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        vector<int> adjList[n];
        for (int i = 0; i < n; i++) {
            if (manager[i] != -1) {
                adjList[manager[i]].push_back(i);
            }
        }
        DFS(adjList, informTime, headID, 0);
        return maxTime;
    }
};

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

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

Задача: 380. Insert Delete GetRandom O(1) Сложность: medium Реализуйте класс RandomizedSet: RandomizedSet(): Инициализирует объект RandomizedSet. bool insert(int val): Вставляет элемент val в множество, если его там нет. Возвращает true, если элемент отсутствовал, и false в противном случае. bool remove(int val): Удаляет элемент val из множества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае. int getRandom(): Возвращает случайный элемент из текущего множества элементов (гарантируется, что по крайней мере один элемент существует при вызове этого метода). Каждый элемент должен иметь равную вероятность быть возвращенным. Вы должны реализовать функции класса таким образом, чтобы каждая функция работала в среднем за O(1) по времени. Пример:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

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

using namespace std;

class RandomizedSet {
public:
    RandomizedSet() {}

    bool insert(int val) {
        if (dict.find(val) != dict.end()) {
            return false;
        }
        dict[val] = list.size();
        list.push_back(val);
        return true;
    }

    bool remove(int val) {
        if (dict.find(val) == dict.end()) {
            return false;
        }
        int index = dict[val];
        int lastElement = list.back();
        list[index] = lastElement;
        dict[lastElement] = index;
        list.pop_back();
        dict.erase(val);
        return true;
    }

    int getRandom() {
        int randomIndex = rand() % list.size();
        return list[randomIndex];
    }

private:
    unordered_map<int, int> dict;
    vector<int> list;
};

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

Задача: 267. Palindrome Permutation II Сложность: medium Пример:

Input: s = "aabb"
Output: ["abba","baab"]

👨‍💻 Алгоритм: 1⃣Подсчёт частоты символов Создаем хеш-таблицу частот. Если количество символов с нечетной частотой больше 1 — палиндром невозможен. 2⃣Формирование первой половины Из каждого символа берём его частоту пополам и формируем строку half. Символ с нечетной частотой (если есть) сохраняем как центральный. 3⃣Генерация палиндромов С помощью backtracking создаём все уникальные перестановки строки half, дополняем их зеркально. Если есть центральный символ — добавляем его в середину. 😎 Решение:

class Solution {
private:
    void backtrack(string& half, vector<bool>& used, string& path, string& mid, vector<string>& res) {
        if (path.size() == half.size()) {
            string rev = path;
            reverse(rev.begin(), rev.end());
            res.push_back(path + mid + rev);
            return;
        }

        for (int i = 0; i < half.size(); ++i) {
            if (used[i]) continue;
            if (i > 0 && half[i] == half[i - 1] && !used[i - 1]) continue;

            used[i] = true;
            path.push_back(half[i]);
            backtrack(half, used, path, mid, res);
            path.pop_back();
            used[i] = false;
        }
    }

public:
    vector<string> generatePalindromes(string s) {
        unordered_map<char, int> freq;
        for (char c : s) freq[c]++;

        int oddCount = 0;
        string mid = "", half = "";
        for (auto& [ch, count] : freq) {
            if (count % 2 != 0) {
                oddCount++;
                mid = ch;
            }
            half += string(count / 2, ch);
        }

        if (oddCount > 1) return {};

        sort(half.begin(), half.end());
        vector<string> res;
        vector<bool> used(half.size(), false);
        string path;
        backtrack(half, used, path, mid, res);
        return res;
    }
};

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

Обучение психологии телесной терапии, гипнозу, ДПДГ, КПТ Если вы психолог, но: Клиенты приходят редко Расписание полупустое Доход не растет 👍Вам нужен не новый диплом, а система! "Психология для психологов" — это: Работающие современные терапевтические стратегии Работающие инструменты продвижения Системные методы работы я клиентами Пошаговый план развития практики Узнайте о льготах и скидках прямо сейчас✅ Узнать больше #реклама 16+ psi-ddt.ru О рекламодателе

Задача: 16. 3Sum Closest Сложность: medium Дан массив целых чисел nums и целое число target. Найди такую тройку чисел в массиве, сумма которых наиболее близка к target, и верни эту сумму. Гарантируется, что только одно решение существует. Пример:

Input: nums = [-1,2,1,-4], target = 1
Output: 2

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

class Solution { 
public: 
    int threeSumClosest(vector<int>& nums, int target) { 
        sort(nums.begin(), nums.end()); 
        int sum = nums[0] + nums[1] + nums[2]; 
        int sum1 = 0; 
        
        for (int i = 0; i < nums.size(); i++) { 
            int front = i + 1; 
            int back = nums.size() - 1; 
            
            while (front < back) { 
                sum1 = nums[i] + nums[front] + nums[back]; 
                
                if (abs(sum1 - target) <= abs(sum - target)) { 
                    sum = sum1; 
                } 
                
                if (sum1 > target)  
                    back--; 
                else if (sum1 < target)  
                    front++; 
                else 
                    return sum1; 
            } 
        } 
        return sum; 
    } 
};

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

Задача: 88. Merge Sorted Array Сложность: easy Даны два отсортированных массива nums1 и nums2, а также числа m и n, обозначающие количество значимых элементов в них. Необходимо слить nums2 в nums1, получив отсортированный массив на месте. nums1 имеет размер m + n, где последние n элементов — нули-заполнители. Пример:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

👨‍💻 Алгоритм: 1⃣Создаем копию первых m элементов nums1 → nums1Copy. Инициализируем два указателя p1 = 0, p2 = 0 — для чтения nums1Copy и nums2. 2⃣Используем один указатель p для записи в nums1. Пока p < m + n, на каждой итерации сравниваем nums1Copy[p1] и nums2[p2]. 3⃣Меньшее из значений записываем в nums1[p]. Увеличиваем соответствующий указатель. Если один из массивов исчерпан, продолжаем с оставшегося. 😎 Решение:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> nums1Copy(nums1.begin(), nums1.begin() + m);
        int p1 = 0;
        int p2 = 0;

        for (int p = 0; p < m + n; p++) {
            if (p2 >= n || (p1 < m && nums1Copy[p1] < nums2[p2])) {
                nums1[p] = nums1Copy[p1++];
            } else {
                nums1[p] = nums2[p2++];
            }
        }
    }
};

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

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

Задача: 94. Binary Tree Inorder Traversal Сложность: easy Дан корень бинарного дерева. Верните обход значений его узлов в симметричном порядке (inorder): лево → корень → право Пример:

Input: root = [1,null,2,3]
Output: [1,3,2]

👨‍💻 Алгоритм: 1⃣Определим вспомогательную функцию helper, которая выполняет рекурсивный обход дерева. 2⃣Если текущий узел root не равен NULL, сначала вызываем helper(root->left), затем добавляем root->val, после чего вызываем helper(root->right). 3⃣Используем вектор res для хранения результата обхода. 😎 Решение:

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        helper(root, res);
        return res;
    }

    void helper(TreeNode* root, vector<int>& res) {
        if (root != NULL) {
            helper(root->left, res);
            res.push_back(root->val);
            helper(root->right, res);
        }
    }
};

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

Задача: 1028. Recover a Tree From Preorder Traversal Сложность: hard Мы запускаем предварительный поиск в глубину (DFS) на корне двоичного дерева. На каждый узел в этом обходе мы выводим D тире (где D - глубина этого узла), а затем выводим значение этого узла.Если глубина узла равна D, то глубина его ближайшего потомка равна D + 1.Глубина корневого узла равна 0. Если у узла есть только один ребенок, то этот ребенок гарантированно является левым ребенком. Учитывая выходной обход этого обхода, восстановите дерево и верните его корень. Пример:

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

👨‍💻 Алгоритм: 1⃣Разбор строки: Пройдите по строке, чтобы определить уровни узлов и их значения. Используйте два счетчика: один для отслеживания текущего уровня (количество тире), второй для значения узла. 2⃣Создание узлов: Создайте новые узлы на основе уровня и значения из строки. Для каждого нового узла найдите его родительский узел из стека и добавьте узел как левого или правого ребенка. 3⃣Построение дерева: Используйте стек для отслеживания текущих узлов на каждом уровне глубины. Когда узел создан, добавьте его в стек. Если узел завершен, уберите его из стека. 😎 Решение:

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* recoverFromPreorder(string S) {
        stack<TreeNode*> stk;
        for (int i = 0; i < S.size();) {
            int level = 0;
            while (i < S.size() && S[i] == '-') {
                level++;
                i++;
            }
            
            int value = 0;
            while (i < S.size() && isdigit(S[i])) {
                value = value * 10 + (S[i] - '0');
                i++;
            }
            
            TreeNode* node = new TreeNode(value);
            if (level == stk.size()) {
                if (!stk.empty()) {
                    stk.top()->left = node;
                }
            } else {
                while (level != stk.size()) {
                    stk.pop();
                }
                stk.top()->right = node;
            }
            stk.push(node);
        }
        
        while (stk.size() > 1) {
            stk.pop();
        }
        
        return stk.top();
    }
};

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

Так хочу отдыхать... Весь день - люди, шум, задачи. А потом - тишина. Только ты, плед, сериал и тот самый диван. Не просто мебель - место, где ты перезагружаешься. С Divan BOSS отдыхать хочется чаще. Мягкий, глубокий, стильный - он создан, чтобы тело расслабилось, а в голове стало легче. ❤️С промокодом BOSSKINO - до 5000 ₽ скидка прямо сейчас! Диван, который выбираешь для себя, а не "на случай гостей". Получить скидку #реклама divanboss.ru О рекламодателе

Задача: 976. Largest Perimeter Triangle Сложность: easy Дан целочисленный массив nums. Верните наибольший периметр треугольника с ненулевой площадью, образованный из трех этих длин. Если невозможно образовать треугольник с ненулевой площадью, верните 0. Пример:

Input: nums = [1,2,1,10]
Output: 0
Explanation: 
You cannot use the side lengths 1, 1, and 2 to form a triangle.
You cannot use the side lengths 1, 1, and 10 to form a triangle.
You cannot use the side lengths 1, 2, and 10 to form a triangle.
As we cannot use any three side lengths to form a triangle of non-zero area, we return 0.

👨‍💻 Алгоритм: 1⃣Отсортируйте массив nums в порядке возрастания. 2⃣Для каждого элемента c в массиве, начиная с конца: Выберите два наибольших возможных значения a и b, которые находятся перед c в отсортированном массиве (т.е. значения, смежные с c). Проверьте, образуют ли a, b и c треугольник (условие треугольника: a + b > c). Если образуют, верните их сумму как периметр треугольника. 3⃣Если не удалось найти такие значения, верните 0. 😎 Решение:

class Solution {
public:
    int largestPerimeter(vector<int>& A) {
        sort(A.begin(), A.end());
        for (int i = A.size() - 3; i >= 0; --i)
            if (A[i] + A[i + 1] > A[i + 2])
                return A[i] + A[i + 1] + A[i + 2];
        return 0;
    }
};

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