C/C++ | LeetCode

Теперь AI сам создает сайты ИИшка в Битрикс24 берёт на себя весь процесс: структура, дизайн, контент — всё создаётся автоматически. Сделайте один запрос AI-помощнику, и через 30 секунд он создаст свой вариант полностью работающего сайта. Узнать больше #реклама sites-24.bitrix24.ru О рекламодателе

Задача: 765. Couples Holding Hands Сложность: hard Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки. Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1). Верните минимальное количество перестановок, чтобы каждая пара сидела рядом. Перестановка состоит из выбора любых двух человек, которые встают и меняются местами. Пример:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

👨‍💻 Алгоритм: 1⃣Мы могли бы предположить без доказательства, что решение, при котором мы делаем людей на каждом диване счастливыми по порядку, является оптимальным. Это предположение сильнее, чем гипотеза о жадном подходе, но кажется разумным, поскольку при каждом ходе мы делаем хотя бы одну пару счастливой. 2⃣При таком предположении, для какого-то дивана с несчастливыми людьми X и Y, мы либо заменяем Y на партнера X, либо заменяем X на партнера Y. Для каждой из двух возможностей мы можем попробовать оба варианта, используя подход с возвратом. 3⃣Для каждого дивана с двумя возможностями (т.е. оба человека на диване несчастливы) мы попробуем первый вариант, найдем ответ как ans1, затем отменим наш ход и попробуем второй вариант, найдем связанный ответ как ans2, отменим наш ход и затем вернем наименьший ответ. 😎 Решение:

class Solution {
public:
    int N;
    vector<vector<int>> pairs;

    int minSwapsCouples(vector<int>& row) {
        N = row.size() / 2;
        pairs.resize(N, vector<int>(2));
        for (int i = 0; i < N; ++i) {
            pairs[i][0] = row[2 * i] / 2;
            pairs[i][1] = row[2 * i + 1] / 2;
        }
        return solve(0);
    }

    void swap(int a, int b, int c, int d) {
        int t = pairs[a][b];
        pairs[a][b] = pairs[c][d];
        pairs[c][d] = t;
    }

    int solve(int i) {
        if (i == N) return 0;
        int x = pairs[i][0], y = pairs[i][1];
        if (x == y) return solve(i + 1);

        int jx = 0, kx = 0, jy = 0, ky = 0;
        for (int j = i + 1; j < N; ++j) {
            for (int k = 0; k <= 1; ++k) {
                if (pairs[j][k] == x) { jx = j; kx = k; }
                if (pairs[j][k] == y) { jy = j; ky = k; }
            }
        }

        swap(i, 1, jx, kx);
        int ans1 = 1 + solve(i + 1);
        swap(i, 1, jx, kx);

        swap(i, 0, jy, ky);
        int ans2 = 1 + solve(i + 1);
        swap(i, 0, jy, ky);

        return min(ans1, ans2);
    }
};

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

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

Задача: 1382. Balance a Binary Search Tree Сложность: medium Дан корень бинарного дерева поиска. Верните сбалансированное бинарное дерево поиска с теми же значениями узлов. Если существует более одного ответа, верните любой из них. Бинарное дерево поиска считается сбалансированным, если глубина двух поддеревьев каждого узла никогда не отличается более чем на 1. Пример:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.

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

class Solution {
public:
    TreeNode* balanceBST(TreeNode* root) {
        if (!root) return nullptr;

        TreeNode* vineHead = new TreeNode(0);
        vineHead->right = root;
        TreeNode* current = vineHead;

        while (current->right) {
            if (current->right->left) {
                rightRotate(current, current->right);
            } else {
                current = current->right;
            }
        }

        int nodeCount = 0;
        current = vineHead->right;
        while (current) {
            ++nodeCount;
            current = current->right;
        }

        int m = pow(2, floor(log2(nodeCount + 1))) - 1;
        makeRotations(vineHead, nodeCount - m);
        while (m > 1) {
            m /= 2;
            makeRotations(vineHead, m);
        }

        TreeNode* balancedRoot = vineHead->right;
        delete vineHead;
        return balancedRoot;
    }

private:
    void rightRotate(TreeNode* parent, TreeNode* node) {
        TreeNode* tmp = node->left;
        node->left = tmp->right;
        tmp->right = node;
        parent->right = tmp;
    }

    void leftRotate(TreeNode* parent, TreeNode* node) {
        TreeNode* tmp = node->right;
        node->right = tmp->left;
        tmp->left = node;
        parent->right = tmp;
    }

    void makeRotations(TreeNode* vineHead, int count) {
        TreeNode* current = vineHead;
        for (int i = 0; i < count; ++i) {
            TreeNode* tmp = current->right;
            leftRotate(current, tmp);
            current = current->right;
        }
    }
};

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

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

Задача: 282. Expression Add Operators Сложность: hard Дана строка num, содержащая только цифры, и целевое число target. Необходимо вернуть все возможные варианты вставки операторов +, -, * так, чтобы выражение вычислялось в target. Ведущие нули в операндах недопустимы. Пример:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]

👨‍💻 Алгоритм 1⃣Инициализация Запускаем рекурсивную функцию, передавая текущие параметры: индекс, предыдущий операнд, текущий операнд, текущее значение и список с операциями. 2⃣Обработка каждого символа На каждом шаге рассматриваем, хотим ли мы продолжать накапливать цифры текущего операнда, либо уже вставляем оператор и переходим к следующей части выражения. 3⃣Учет всех операторов Рассматриваем операции +, - и *, для каждой пересчитываем значение с учетом порядка операций. Используем previousOperand для корректного учета * в выражении. 😎 Решение

class Solution {
private:
    vector<string> answer;
    string digits;
    long long target;

    void recurse(int index, long long prevOperand, long long currentOperand, long long value, vector<string>& ops) {
        if (index == digits.size()) {
            if (value == target && currentOperand == 0) {
                string expression = accumulate(ops.begin(), ops.end(), string(""));
                answer.push_back(expression);
            }
            return;
        }

        currentOperand = currentOperand * 10 + (digits[index] - '0');
        string currentValRep = to_string(currentOperand);

        if (currentOperand > 0) {
            recurse(index + 1, prevOperand, currentOperand, value, ops);
        }

        // +
        ops.push_back("+");
        ops.push_back(currentValRep);
        recurse(index + 1, currentOperand, 0, value + currentOperand, ops);
        ops.pop_back(); ops.pop_back();

        if (!ops.empty()) {
            // -
            ops.push_back("-");
            ops.push_back(currentValRep);
            recurse(index + 1, -currentOperand, 0, value - currentOperand, ops);
            ops.pop_back(); ops.pop_back();

            // *
            ops.push_back("*");
            ops.push_back(currentValRep);
            recurse(index + 1, prevOperand * currentOperand, 0, value - prevOperand + (prevOperand * currentOperand), ops);
            ops.pop_back(); ops.pop_back();
        }
    }

public:
    vector<string> addOperators(string num, int target) {
        if (num.empty()) return {};
        this->digits = num;
        this->target = target;
        vector<string> ops;
        recurse(0, 0, 0, 0, ops);
        return answer;
    }
};

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

Сколько приложений нужно вашей команде для работы? Всего один сервис — Битрикс24! А внутри десятки инструментов для совместной работы и бизнеса. Читайте подробнее в карточках. Регистрируйтесь сейчас, чтобы забрать их все себе бесплатно😊 Зарегистрироваться #реклама 16+ office-online.bitrix24.ru О рекламодателе

Задача: 462. Minimum Moves to Equal Array Elements II Сложность: medium Дан массив целых чисел nums размера n, вернуть минимальное количество ходов, необходимых для того, чтобы сделать все элементы массива равными. В одном ходе вы можете увеличить или уменьшить элемент массива на 1. Тестовые случаи составлены так, что ответ поместится в 32-битное целое число. Пример:

Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

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

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        long ans = LONG_MAX;
        int minval = INT_MAX;
        int maxval = INT_MIN;
        for (int num : nums) {
            minval = min(minval, num);
            maxval = max(maxval, num);
        }
        for (int i = minval; i <= maxval; i++) {
            long sum = 0;
            for (int num : nums) {
                sum += abs(num - i);
            }
            ans = min(ans, sum);
        }
        return (int) ans;
    }
};

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

Получи грант до 1,2 млн руб. на обучение в магистратуре Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой? Поступай в магистратуру Центрального университета! - 4 офлайн программы по востребованным направлениям ИТ - Онлайн-программа по машинному обучению - 300 мест с грантами до 1,2 млн руб. - Вечерние занятия и учеба по выходным — удобно совмещать с работой - Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса - Возможность стажировок и трудоустройства в ведущих компаниях - Государственный диплом за 2 года Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии. Оставляй заявку на грант уже сейчас! Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

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

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

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

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

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

Офисные башни JOIS от MR Office в 10 мин от Москва-Сити JOIS - это современные башни класса А от нового бренда, объединяющего все офисные объекты MR Group. Проект премиального бизнес-центра включает две башни: 1) 43-этажный небоскреб MAST с офисами от 96 м² и возможностью приобретения офисных помещений по отдельности, а также целыми этажами или блоками 2) Башня CREDO представляет из себя единый офис площадью 22 000 м² Главные преимущества будущего проекта: ✨Ландшафтный парк площадью 1,3 Га и пешеходный маршрут более 2,3 км ✨Расположение в 5 минутах до ТТК и 10 минутах от Москва-сити ✨3-уровневый подземный паркинг, рассчитанный на 400 машиномест ✨Отделка Shell&Core - оптимальное решение для создания эксклюзивного интерьера ✨Рассрочка 0% на приобретение коммерческой недвижимости Узнать больше Проектная декларация на сайте https://наш.дом.рф/. Застройщик: ООО СЗ Л2-ДЕВЕЛОПМЕНТ #реклама mr-group.ru О рекламодателе

Задача: 421. Maximum XOR of Two Numbers in an Array Сложность: medium Дан целочисленный массив nums, верните максимальный результат nums[i] XOR nums[j], где 0 <= i <= j < n. Пример:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

👨‍💻 Алгоритм: 1⃣Вычислите количество битов L для использования. Это длина максимального числа в двоичном представлении. Инициализируйте max_xor = 0. 2⃣Запустите цикл от i = L−1 до i = 0 (от самого левого бита L−1 до самого правого бита 0): Сдвигайте max_xor влево, чтобы освободить следующий бит. Инициализируйте переменную curr_xor = max_xor | 1, установив 1 в самом правом бите max_xor. Теперь проверьте, можно ли выполнить curr_xor, используя доступные префиксы. 3⃣Вычислите все возможные префиксы длины L−i, итерируя по nums: Поместите в HashSet префиксы префикс текущего числа длиной L−i: num >> i. Итерируйте по всем префиксам и проверьте, можно ли выполнить curr_xor, используя два из них: p1 ^ p2 == curr_xor. Используя свойство самопреобразования XOR p1 ^ p2 ^ p2 = p1, можно переписать это как p1 == curr_xor ^ p2 и просто проверить для каждого p, если curr_xor ^ p есть в префиксах. Если так, установите max_xor равным curr_xor, т.е. установите 1-бит в самом правом бите. В противном случае, пусть max_xor оставит 0-бит в самом правом бите. 😎 Решение:

#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int maxNum = nums[0];
        for (int num : nums) maxNum = max(maxNum, num);
        int L = 32 - __builtin_clz(maxNum);

        int maxXor = 0, currXor;
        unordered_set<int> prefixes;
        for (int i = L - 1; i >= 0; --i) {
            maxXor <<= 1;
            currXor = maxXor | 1;
            prefixes.clear();
            for (int num : nums) prefixes.insert(num >> i);
            for (int p : prefixes) {
                if (prefixes.count(currXor ^ p)) {
                    maxXor = currXor;
                    break;
                }
            }
        }
        return maxXor;
    }
};

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

Получи грант на обучение в Центральном университете Прояви себя, получи грант до 2,8 млн на обучение ИТ и бизнесу в вузе. Для школьников 10-х и 11-х классов, СПО. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 329. Longest Increasing Path in a Matrix Сложность: hard Дана матрица целых чисел размером m x n. Верните длину самого длинного возрастающего пути в матрице. Из каждой ячейки можно перемещаться в четырех направлениях: влево, вправо, вверх или вниз. Перемещение по диагонали или выход за границы матрицы (т.е. замкнутые переходы) не допускается. Пример:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

👨‍💻 Алгоритм: 1⃣Инициализация и создание матрицы: Инициализируйте размеры матрицы m и n. Создайте матрицу matrix с добавленными границами (нулевыми значениями) вокруг исходной матрицы, чтобы избежать выхода за пределы при обработке. Рассчитайте количество исходящих связей (outdegrees) для каждой клетки и сохраните их в outdegree. 2⃣Поиск начальных листьев: Найдите все клетки с нулевыми исходящими связями и добавьте их в список leaves. Эти клетки будут начальной точкой для "слоевого удаления". 3⃣Удаление слоев: Повторяйте процесс удаления клеток уровня за уровнем в порядке топологической сортировки, пока не останется листьев. Обновляйте количество исходящих связей и добавляйте новые листья на следующем уровне. Подсчитывайте количество уровней, что в итоге даст длину самого длинного возрастающего пути. 😎 Решение:

class Solution {
private:
    static constexpr int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public:
    int longestIncreasingPath(vector<vector<int>>& grid) {
        int m = grid.size();
        if (m == 0) return 0;
        int n = grid[0].size();
        vector<vector<int>> matrix(m + 2, vector<int>(n + 2));
        vector<vector<int>> outdegree(m + 2, vector<int>(n + 2));

        for (int i = 0; i < m; ++i) {
            copy(grid[i].begin(), grid[i].end(), matrix[i + 1].begin() + 1);
        }

        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                for (auto& d : dir) {
                    if (matrix[i][j] < matrix[i + d[0]][j + d[1]]) {
                        outdegree[i][j]++;
                    }
                }
            }
        }

        vector<pair<int, int>> leaves;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (outdegree[i][j] == 0) leaves.emplace_back(i, j);
            }
        }

        int height = 0;
        while (!leaves.empty()) {
            ++height;
            vector<pair<int, int>> newLeaves;
            for (auto& node : leaves) {
                for (auto& d : dir) {
                    int x = node.first + d[0], y = node.second + d[1];
                    if (matrix[node.first][node.second] > matrix[x][y]) {
                        if (--outdegree[x][y] == 0) {
                            newLeaves.emplace_back(x, y);
                        }
                    }
                }
            }
            leaves.swap(newLeaves);
        }

        return height;
    }
};

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

Задача: 1248. Count Number of Nice Subarrays Сложность: medium Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать. Пример:

Input: arr = [1,2]
Output: 2

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

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }

private:
    int atMost(vector<int>& nums, int k) {
        int res = 0, left = 0, count = 0;
        for (int right = 0; right < nums.size(); right++) {
            if (nums[right] % 2 == 1) count++;
            while (count > k) {
                if (nums[left++] % 2 == 1) count--;
            }
            res += right - left + 1;
        }
        return res;
    }
};

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

Хочешь новую профессию? Тогда по-взрослому: Психология — это не магия, не эзотерика и не «послушаю подругу за чашкой чая». Это профессия. С методами, практикой, реальными людьми и ответственностью. И ты можешь её освоить за 12 месяцев — без воды. Что конкретно ты получаешь: – 1200 часов системного обучения – 450 часов реальной практики: тренажёры, клиенты, супервизии – Занятия в мини-группах с наставниками – Диплом о проф. переподготовке + международный диплом MBA – Запуск частной практики уже в процессе обучения Всё обучение — онлайн. Гибко, но не халтурно. Через 12 месяцев — ты не в «поиске себя», а в новой профессии. С дипломом. С навыками. С первыми клиентами. С направлением. Посмотри программу. Реши — идёшь или нет. ✅ Начни учиться бесплатно прямо сегодня! Зарегистрироваться #реклама 16+ psy.talentsy.ru О рекламодателе

Задача: 345. Reverse Vowels of a String Сложность: easy Дана строка s, переверните только все гласные в строке и верните её. Гласные: 'a', 'e', 'i', 'o', 'u', а также их верхние регистры. Пример:

Input: s = "hello"
Output: "holle"

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

class Solution {
public:
    string reverseVowels(string s) {
        unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
        int left = 0, right = s.size() - 1;
        
        while (left < right) {
            if (vowels.find(s[left]) == vowels.end()) {
                left++;
            } else if (vowels.find(s[right]) == vowels.end()) {
                right--;
            } else {
                swap(s[left], s[right]);
                left++;
                right--;
            }
        }
        
        return s;
    }
};

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

Обучение трейдингу для новичков и профессиналов Изучайте слайды с основными темами, смотрите видео и практикуйтесь. Торгуйте на рынке как профи! Зарегистрироваться #реклама 16+ fxproru.pro О рекламодателе

Задача: 1302. Deepest Leaves Sum Сложность: medium Дано корень бинарного дерева, вернуть сумму значений его самых глубоких листьев. Пример:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

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

class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
        int deepestSum = 0, depth = 0, currDepth;
        stack<pair<TreeNode*, int>> stack;
        stack.push({root, 0});

        while (!stack.empty()) {
            auto [node, currDepth] = stack.top();
            stack.pop();

            if (!node->left && !node->right) {
                if (depth < currDepth) {
                    deepestSum = node->val;
                    depth = currDepth;
                } else if (depth == currDepth) {
                    deepestSum += node->val;
                }
            } else {
                if (node->right) {
                    stack.push({node->right, currDepth + 1});
                }
                if (node->left) {
                    stack.push({node->left, currDepth + 1});
                }
            }
        }
        return deepestSum;
    }
};

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

Ищешь высокооплачиваемые проекты? Попробуй SkillStaff SkillStaff — это платформа для ИТ-специалистов, менеджеров и креаторов, которым мало одного оклада. Здесь можно найти клиентов, выполнять их проекты и увеличивать свой доход. - Проекты с гибким графиком: part time, full time, удаленка и гибрид - Ставка за час работы — та, что ты сам выбрал - Клиенты — ведущие бренды, проверенные с юридической точки зрения при регистрации на платформе - Оплата поступает ежемесячно на расчетный счет исполнителя - Удобный личный кабинет и функционал, автоматизирующий документооборот Все, что нужно для работы — иметь статус самозанятого или ИП, а платформа поможет со всеми нюансами. Регистрируйся прямо сейчас Зарегистрироваться #реклама 16+ skillstaff.ru О рекламодателе