C/C++ | LeetCode

Задача: 908. Smallest Range I Сложность: easy Вам дан целочисленный массив nums и целое число k. За одну операцию вы можете выбрать любой индекс i, где 0 <= i < nums.length, и изменить nums[i] на nums[i] + x, где x - целое число из диапазона [-k, k]. Эту операцию можно применять не более одного раза для каждого индекса i. Оценка nums - это разница между максимальным и минимальным элементами в nums. Верните минимальную оценку nums после применения указанной операции не более одного раза для каждого индекса в нем. Пример:

Input: nums = [1], k = 0
Output: 0

👨‍💻 Алгоритм: 1⃣Найти минимальное и максимальное значения массива nums. 2⃣Рассчитать потенциальные новые минимальные и максимальные значения после применения операции. 3⃣Вычислить минимальную оценку, сравнивая разницу между всеми возможными новыми минимальными и максимальными значениями. 😎 Решение:

class Solution {
public:
    int smallestRangeI(vector<int>& nums, int k) {
        int minVal = *min_element(nums.begin(), nums.end());
        int maxVal = *max_element(nums.begin(), nums.end());
        return max(0, (maxVal - k) - (minVal + k));
    }
};

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

Задача: 1190. Reverse Substrings Between Each Pair of Parentheses Сложность: medium Дана строка s, состоящая из строчных букв английского алфавита и скобок. Переверните строки в каждой паре соответствующих скобок, начиная с самой внутренней. Ваш результат не должен содержать скобок. Пример:

Input: s = "(abcd)"
Output: "dcba"

👨‍💻 Алгоритм: 1⃣Инициализируйте пустой стек openParenthesesIndices для отслеживания начальных точек разворота и пустую строку result для построения выходного результата. 2⃣Для каждого символа currentChar во входной строке: Если это '(', добавьте длину строки result в openParenthesesIndices, чтобы отметить потенциальную начальную точку разворота. Если это ')', извлеките значение из openParenthesesIndices и переверните result от извлеченного индекса для выполнения необходимого разворота. В противном случае добавьте currentChar к result для построения строки. 3⃣Верните result как окончательную строку со всеми примененными разворотами. 😎 Решение:

class Solution {
public:
    string reverseParentheses(string s) {
        stack<int> openParenthesesIndices;
        string result;

        for (char currentChar : s) {
            if (currentChar == '(') {
                openParenthesesIndices.push(result.size());
            } else if (currentChar == ')') {
                int start = openParenthesesIndices.top();
                openParenthesesIndices.pop();
                reverse(result.begin() + start, result.end());
            } else {
                result.push_back(currentChar);
            }
        }

        return result;
    }
};

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

Задача: 536. Construct Binary Tree from String Сложность: medium Вам нужно построить бинарное дерево из строки, состоящей из круглых скобок и целых чисел. Весь ввод представляет собой бинарное дерево. Он содержит целое число, за которым следуют ноль, одна или две пары круглых скобок. Целое число представляет значение корня, а пара круглых скобок содержит дочернее бинарное дерево с той же структурой. Вы всегда начинаете строить левый дочерний узел родителя сначала, если он существует. Пример:

Input: s = "4(2(3)(1))(6(5))"
Output: [4,2,6,3,1,5]

👨‍💻 Алгоритм: 1⃣ Извлечение числа: Определите функцию getNumber, которая извлекает целое число из текущей строки, начиная с указанного индекса. Учтите знак числа, если он есть. 2⃣ Построение поддерева: Определите рекурсивную функцию str2treeInternal, которая принимает строку и текущий индекс в качестве входных данных и возвращает пару: узел TreeNode и следующий индекс для обработки. Внутри функции извлеките значение для корневого узла текущего поддерева, создайте узел, а затем рекурсивно постройте левое и правое поддеревья, если они существуют. 3⃣ Основная функция: Определите основную функцию str2tree, которая вызывает рекурсивную функцию str2treeInternal и возвращает построенное дерево. 😎 Решение:

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

class Solution {
public:
    TreeNode* str2tree(string s) {
        return str2treeInternal(s, 0).first;
    }

private:
    pair<int, int> getNumber(const string& s, int index) {
        bool isNegative = false;
        if (s[index] == '-') {
            isNegative = true;
            index++;
        }
        int number = 0;
        while (index < s.size() && isdigit(s[index])) {
            number = number * 10 + (s[index] - '0');
            index++;
        }
        return {isNegative ? -number : number, index};
    }

    pair<TreeNode*, int> str2treeInternal(const string& s, int index) {
        if (index == s.size()) return {nullptr, index};

        auto numberData = getNumber(s, index);
        int value = numberData.first;
        index = numberData.second;

        TreeNode* node = new TreeNode(value);

        if (index < s.size() && s[index] == '(') {
            auto leftData = str2treeInternal(s, index + 1);
            node->left = leftData.first;
            index = leftData.second;
        }

        if (index < s.size() && s[index] == '(') {
            auto rightData = str2treeInternal(s, index + 1);
            node->right = rightData.first;
            index = rightData.second;
        }

        return {node, index < s.size() && s[index] == ')' ? index + 1 : index};
    }
};

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

Задача: 679. 24 Game Сложность: hard Дан массив целых чисел cards длиной 4. У вас есть четыре карты, каждая из которых содержит число в диапазоне от 1 до 9. Вам нужно расположить числа на этих картах в математическом выражении, используя операторы ['+', '-', '*', '/'] и скобки '(' и ')' так, чтобы получить значение 24. Вы ограничены следующими правилами: Оператор деления '/' представляет собой реальное деление, а не целочисленное деление. Например, 4 / (1 - 2 / 3) = 4 / (1 / 3) = 12. Каждая операция выполняется между двумя числами. В частности, мы не можем использовать '-' как унарный оператор. Например, если cards = [1, 1, 1, 1], выражение "-1 - 1 - 1 - 1" не допускается. Вы не можете объединять числа вместе. Например, если cards = [1, 2, 1, 2], выражение "12 + 12" недопустимо. Вернуть true, если вы можете получить такое выражение, которое оценивается в 24, и false в противном случае. Пример:

Input: cards = [4,1,8,7]
Output: true
Explanation: (8-4) * (7-1) = 24

👨‍💻 Алгоритм: 1⃣Создайте функцию generatePossibleResults(a, b), которая возвращает массив результатов всех возможных математических операций над двумя числами. 2⃣ Создайте функцию checkIfResultReached(list), чтобы проверить, можем ли мы достичь результата 24, используя текущий массив list. Сначала проверьте базовые условия: если размер массива равен 1, верните true, если результат равен 24, иначе верните false. 3⃣Если размер массива больше 1, выберите любые два числа из списка, выполните все математические операции над ними, создайте новый список с обновленными элементами и снова вызовите рекурсивную функцию с этим новым списком. Если ни одна комбинация не приводит к результату 24, верните false. Вызовите checkIfResultReached с исходным списком карт. 😎 Решение:

class Solution {
public:
    vector<double> generatePossibleResults(double a, double b) {
        vector<double> res = { a + b, a - b, b - a, a * b };
        if (a != 0) res.push_back(b / a);
        if (b != 0) res.push_back(a / b);
        return res;
    }

    bool checkIfResultReached(vector<double> list) {
        if (list.size() == 1) return abs(list[0] - 24) <= 0.1;

        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                vector<double> newList;
                for (int k = 0; k < list.size(); k++) {
                    if (k != i && k != j) newList.push_back(list[k]);
                }
                for (double res : generatePossibleResults(list[i], list[j])) {
                    newList.push_back(res);
                    if (checkIfResultReached(newList)) return true;
                    newList.pop_back();
                }
            }
        }
        return false;
    }

    bool judgePoint24(vector<int>& cards) {
        vector<double> list(cards.begin(), cards.end());
        return checkIfResultReached(list);
    }
};

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

Где вести задачи и проекты? В Битрикс24 ✅ Бесплатный онлайн-сервис для бизнеса и совместной работы. — Удобный планировщик задач для всей команды с чек-листами и комментариями. — Популярные проектные методики: канбан, скрам, диаграмма ганта. — Видеозвонки в один клик из чата. — Календарь и слоты для совместного планирования. — Умный ИИ-помощник для постановки четких тз. Полный комплект для эффективности вашей команды. Ставьте первую задачу прямо сейчас⚡ Начать #реклама 16+ task-24.bitrix24.ru О рекламодателе

Задача: 75. Sort Colors Сложность: medium Дан массив nums, содержащий n объектов, окрашенных в красный, белый или синий цвет. Отсортируйте их на месте так, чтобы объекты одного цвета находились рядом, а цвета шли в порядке: красный (0), белый (1), синий (2). Запрещено использовать встроенные функции сортировки. Пример:

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

👨‍💻 Алгоритм: 1⃣Инициализация указателя p0 = 0, отвечающего за край для нулей. 2⃣Инициализация указателя p2 = n - 1, отвечающего за край для двоек. 3⃣Индекс текущего элемента: curr = 0. Пока curr <= p2: если nums[curr] == 0 → меняем с nums[p0], сдвигаем p0 и curr вправо если nums[curr] == 2 → меняем с nums[p2], сдвигаем p2 влево если nums[curr] == 1 → просто двигаем curr 😎 Решение:

class Solution {
public:
  void sortColors(vector<int>& nums) {
    int p0 = 0, curr = 0;
    int p2 = nums.size() - 1;

    while (curr <= p2) {
      if (nums[curr] == 0) {
        swap(nums[curr++], nums[p0++]);
      }
      else if (nums[curr] == 2) {
        swap(nums[curr], nums[p2--]);
      }
      else curr++;
    }
  }
};

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

⏳ Осталось 20 мест Акция со скидкой 50% для первых 500 пользователей easyoffer подходит к концу 🔥 Узнай вопросы и задачи с собеседований в конкретных компаниях 🔥 Получи лучшие ответы и видео-примеры от middle/senior специалистов 🔥 Обходи фильтры ATS, добавив топ30 ключевых слов в свое резюме 🔥 Экономь время с помощью автоматических откликов 🔥 Подготовься идеально к интервью с тренажёрами и симуляторами Успей забрать место по акции: 👉 https://easyoffer.ru/pro

Задача: 509. Fibonacci Number Сложность: easy Числа Фибоначчи, обычно обозначаемые как F(n), образуют последовательность, называемую последовательностью Фибоначчи, так что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть, F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), для n > 1. Дано n, вычислите F(n). Пример:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

👨‍💻 Алгоритм: 1⃣Проверка начального условия Если N <= 1, вернуть N. 2⃣Инициализация переменных Инициализируйте current значением 0. Инициализируйте prev1 значением 1, что будет представлять fib(N-1) при вычислении текущего значения. Инициализируйте prev2 значением 0, что будет представлять fib(N-2) при вычислении текущего значения. 3⃣Итерация и вычисление Итерация от 2 до N включительно. На каждой итерации: установите current как сумму prev1 и prev2. Обновите prev2 значением prev1. Обновите prev1 значением current. Вернуть значение current после завершения итерации. 😎 Решение:

class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        int current = 0, prev1 = 1, prev2 = 0;
        for (int i = 2; i <= N; ++i) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return current;
    }
};

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

Гайд для РОПов по проведению эффективных вебинаров Как руководителям отделов продаж увеличить количество успешных сделок при том же объеме лидов с помощью вебинаров? Гайд от МТС Линк по обучающим вебинарам для отделов продаж. ✅ В гайде: - Как эффективнее прокачивать скиллы менеджеров и закрывать больше сделок за меньшие сроки; - Как организовать тренинг так, чтобы участники действительно подключились и дошли до финального модуля; - Как выявить слабого менеджера и улучшить его показатели; - Как сэкономить время на организации вебинара и пригласить всех участников в 2 клика. Бонус внутри: 5 прикладных советов по контролю внимания участников во время вебинара ✨ Скачайте гайд бесплатно по ссылке Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 899. Orderly Queue Сложность: hard Вам дана строка s и целое число k. Вы можете выбрать одну из первых k букв s и добавить ее в конец строки. Верните лексикографически наименьшую строку, которая может получиться после применения указанного шага за любое количество ходов. Пример:

Input: s = "cba", k = 1
Output: "acb"

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

class Solution {
public:
    string orderlyQueue(string s, int k) {
        if (k == 1) {
            string minString = s;
            for (int i = 1; i < s.length(); i++) {
                string rotated = s.substr(i) + s.substr(0, i);
                if (rotated < minString) {
                    minString = rotated;
                }
            }
            return minString;
        } else {
            sort(s.begin(), s.end());
            return s;
        }
    }
};

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

👩‍💻 C# вакансии всех грейдов: удалёнка, реклок, щедрый оффер! Только с прямыми контактами в Telegram! Ноль автоотказов — живой диалог и быстрые объективные решения. 👩‍💻 C# 👩‍💻 Python 👩‍💻 Java 👣 Go 🤖 ML & DS 👩‍💻 DevOps 🔎 QA 👩‍💻 Frontend 👩‍💻 Node.js 🖥 SQL 👩‍💻 UX/UI 🖼️ PHP 👩‍💻 Mobile 📋 Analyst 💼 1C 👨‍✈️ CyberSec 👩‍💻 IT HR Подпишись чтобы не упустить свой шанс получить лучший оффер!

Задача: 543. Diameter of Binary Tree Сложность: easy Учитывая корень бинарного дерева, вернуть длину диаметра дерева. Диаметр бинарного дерева — это длина самого длинного пути между любыми двумя узлами в дереве. Этот путь может проходить или не проходить через корень. Длина пути между двумя узлами представлена числом ребер между ними. Пример:

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

👨‍💻 Алгоритм: 1⃣Инициализируйте целочисленную переменную diameter для отслеживания самого длинного пути, найденного с помощью DFS. 2⃣Реализуйте рекурсивную функцию longestPath, которая принимает TreeNode в качестве входных данных и рекурсивно исследует дерево: Если узел равен None, вернуть 0. Рекурсивно исследовать левые и правые дочерние узлы, возвращая длины путей leftPath и rightPath. Если сумма leftPath и rightPath больше текущего diameter, обновить diameter. Вернуть большее из leftPath и rightPath плюс 1. 3⃣Вызвать longestPath с root. 😎 Решение:

class Solution {
    int diameter;
public:
    int diameterOfBinaryTree(TreeNode* root) {
        diameter = 0;
        longestPath(root);
        return diameter;
    }
    
private:
    int longestPath(TreeNode* node) {
        if (node == nullptr) return 0;
        
        int leftPath = longestPath(node->left);
        int rightPath = longestPath(node->right);
        
        diameter = std::max(diameter, leftPath + rightPath);
        
        return std::max(leftPath, rightPath) + 1;
    }
};

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

Задача: 230. Kth Smallest Element in a BST Сложность: medium Дан корень бинарного дерева поиска и целое число k. Верните k-ое по величине значение (нумерация с 1) среди всех значений узлов в дереве. Пример:

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

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

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> stack;
        
        while (true) {
            while (root != nullptr) {
                stack.push(root);
                root = root->left;
            }
            root = stack.top();
            stack.pop();
            if (--k == 0) return root->val;
            root = root->right;
        }
    }
};

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

Пасты Лесной Бальзам - удобно, выгодно, эффективно Покупайте зубные пасты Лесной Бальзам в удобных флаконах с дозатором 👍 Зубные пасты Лесной бальзам: ✅ укрепляют эмаль ✅ освежают дыхание ✅ подходят для всей семьи, в том числе для детей с 7 лет Выбирайте комплексную защиту полости рта от Лесного Бальзама и покупайте зубную пасту в три раза реже! 💰 Попробовать #реклама ozon.ru О рекламодателе

⏳ 90 акционных мест Акция со скидкой 50% для первых 500 пользователей easyoffer подходит к концу 🔥 Узнай вопросы и задачи с собеседований в конкретных компаниях 🔥 Получи лучшие ответы и видео-примеры от middle/senior специалистов 🔥 Обходи фильтры ATS, добавив топ30 ключевых слов в свое резюме 🔥 Экономь время с помощью автоматических откликов 🔥 Подготовься идеально к интервью с тренажёрами и симуляторами Успей забрать место по акции: 👉 https://easyoffer.ru/pro

Задача: 861. Score After Flipping Matrix Сложность: hard Дан целочисленный массив nums и целое число k. Верните длину самой короткой непустой подмассива nums, сумма которого составляет как минимум k. Если такого подмассива нет, верните -1. Подмассив — это непрерывная часть массива. Пример:

Input: nums = [1], k = 1
Output: 1

👨‍💻 Алгоритм: 1⃣Создайте "моноочередь" индексов P: дек индексов x_0, x_1, ..., так чтобы P[x_0], P[x_1], ... увеличивались. 2⃣При добавлении нового индекса y, удалите x_i из конца дека, чтобы P[x_0], P[x_1], ..., P[y] увеличивались. 3⃣Если P[y] >= P[x_0] + K, то (как описано ранее) мы больше не рассматриваем этот x_0 и удаляем его из начала дека. 😎 Решение:

class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        int N = A.size();
        vector<long> P(N + 1);
        for (int i = 0; i < N; ++i)
            P[i + 1] = P[i] + A[i];

        int ans = N + 1;
        deque<int> monoq;

        for (int y = 0; y < P.size(); ++y) {
            while (!monoq.empty() && P[y] <= P[monoq.back()])
                monoq.pop_back();
            while (!monoq.empty() && P[y] >= P[monoq.front()] + K)
                ans = min(ans, y - monoq.pop_front());
            monoq.push_back(y);
        }

        return ans < N + 1 ? ans : -1;
    }
};

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

Как списать долги? Бесплатно через МФЦ! Долги от 200 000₽. Поможем бесплатно списать долг и расторгнуть все кредитные договоры! Узнать больше #реклама нет-кредит.рф О рекламодателе

Задача: 660. Remove 9 Сложность: hard Начните с целого числа 1, уберите любое число, которое содержит 9, такое как 9, 19, 29... Теперь у вас будет новая последовательность целых чисел [1, 2, 3, 4, 5, 6, 7, 8, 10, 11, ...]. Дано целое число n, верните n-е (начиная с 1) целое число в новой последовательности. Пример:

Input: n = 9
Output: 10

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

class Solution {
public:
    int newInteger(int n) {
        int count = 0;
        int num = 0;
        while (count < n) {
            num++;
            if (to_string(num).find('9') == string::npos) {
                count++;
            }
        }
        return num;
    }
};

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

Задача: 1503. Last Moment Before All Ants Fall Out of a Plank Сложность: medium У нас есть деревянная доска длиной n единиц. Некоторые муравьи ходят по доске, каждый муравей движется со скоростью 1 единица в секунду. Некоторые муравьи движутся влево, другие движутся вправо. Когда два муравья, движущиеся в разных направлениях, встречаются в какой-то точке, они меняют свои направления и продолжают двигаться дальше. Предполагается, что изменение направлений не занимает дополнительного времени. Когда муравей достигает одного из концов доски в момент времени t, он сразу же падает с доски. Дано целое число n и два целых массива left и right, обозначающие позиции муравьев, движущихся влево и вправо соответственно. Верните момент, когда последний(е) муравей(и) падает(ют) с доски. Пример:

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
The last moment when an ant was on the plank is t = 4 seconds. After that, it falls immediately out of the plank. (i.e., We can say that at t = 4.0000000001, there are no ants on the plank).

👨‍💻 Алгоритм: 1⃣Инициализируйте переменную ans значением 0. 2⃣Итерация по массиву left и обновление ans значением num, если оно больше текущего значения ans. 3⃣Итерация по массиву right и обновление ans значением n - num, если оно больше текущего значения ans. Верните значение ans. 😎 Решение:

class Solution {
public:
    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
        int ans = 0;
        for (int num : left) {
            ans = max(ans, num);
        }
        for (int num : right) {
            ans = max(ans, n - num);
        }
        return ans;
    }
};

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

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