C/C++ | LeetCode

В турагентство на удаленку требуются стажеры Клиентов предоставим. Можно без опыта и совмещая с основной работой или декретом. С нас обучение с гарантированной стажировкой. Доход после обучения: от 50 000₽ до 220 000₽. Оплата в процессе обучения зависит от вашей вовлеченности. Задачи: Помогать людям организовывать путешествия: подбор самых выгодных предложений на отдых со скидкой до 50% в новых сервисах бронирования. Условия: ✅ Без опыта — обучение с нуля за 2 месяца, первые выплаты в среднем в течение 2 недель; ✅Удаленная работа или совмещение с офисом (по желанию, зависит от вашего города). Хотите проверить, подойдет ли это вам? Регистрируйтесь на бесплатный вводный урок, на котором узнаете: — как подбирать туры для себя и близких с выгодой до 40% — как получать комиссию 7-10% с каждого тура. Узнать больше #реклама 16+ via-tourism-school.space О рекламодателе

Задача: 1071. Greatest Common Divisor of Strings Сложность: easy Для двух строк s и t мы говорим, что "t делит s", если и только если s = t + t + t + ... + t (т.е. t соединена сама с собой один или более раз). Даны две строки str1 и str2, верните наибольшую строку x, такую что x делит и str1, и str2. Пример:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

👨‍💻 Алгоритм: 1⃣Найдите более короткую строку среди str1 и str2, для простоты пусть это будет str1. 2⃣Начните с base = str1 и проверьте, состоят ли обе строки str1 и str2 из множителей строки base. Если это так, верните base. В противном случае, попробуйте более короткую строку, удалив последний символ из base. 3⃣Если вы проверили все префиксные строки и не нашли строку GCD, верните "". 😎 Решение:

class Solution {
public:
    bool valid(string str1, string str2, int k) {
        int len1 = str1.size(), len2 = str2.size();
        if (len1 % k > 0 || len2 % k > 0) {
            return false;
        } else {
            string base = str1.substr(0, k);
            int n1 = len1 / k, n2 = len2 / k;
            return str1 == joinWords(base, n1) && str2 == joinWords(base, n2);
        }
    }
    string joinWords(string str, int k) {
        string ans = "";
        for (int i = 0; i < k; ++i) {
            ans += str;
        }
        return ans;
    }
    string gcdOfStrings(string str1, string str2) {
        int len1 = str1.length(), len2 = str2.length();
        for (int i = min(len1, len2); i >= 1; --i) {
            if (valid(str1, str2, i)) {
                return str1.substr(0, i);
            }
        }
        return "";
    }
};

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

Задача: 1258. Synonymous Sentences Сложность: medium Вам дан список эквивалентных пар строк synonyms, где synonyms[i] = [si, ti] означает, что si и ti являются эквивалентными строками. Вам также дан текст предложения. Верните все возможные синонимичные предложения, отсортированные лексикографически. Пример:

Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"
Output: ["I am cheerful today but was sad yesterday","I am cheerful today but was sorrow yesterday","I am happy today but was sad yesterday","I am happy today but was sorrow yesterday","I am joy today but was sad yesterday","I am joy today but was sorrow yesterday"]

👨‍💻 Алгоритм: 1⃣Построить граф синонимов, используя структуру данных, такую как Union-Find или просто с использованием DFS/BFS. 2⃣Пройти по каждому слову в предложении и найти все возможные синонимы. Сгенерировать все возможные комбинации предложений. 3⃣Отсортировать полученные предложения лексикографически. 😎 Решение:

class Solution {
public:
    vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
        unordered_map<string, set<string>> graph;
        for (const auto& pair : synonyms) {
            graph[pair[0]].insert(pair[1]);
            graph[pair[1]].insert(pair[0]);
        }

        vector<string> words = split(text, ' ');
        vector<vector<string>> synonymGroups;
        for (const string& word : words) {
            synonymGroups.push_back(findSynonyms(graph, word));
        }

        vector<string> sentences;
        string sentence;
        generate(sentences, synonymGroups, sentence, 0);
        sort(sentences.begin(), sentences.end());
        return sentences;
    }

private:
    vector<string> split(const string& str, char delimiter) {
        vector<string> tokens;
        string token;
        istringstream tokenStream(str);
        while (getline(tokenStream, token, delimiter)) {
            tokens.push_back(token);
        }
        return tokens;
    }

    vector<string> findSynonyms(unordered_map<string, set<string>>& graph, const string& word) {
        set<string> synonyms;
        stack<string> stack;
        stack.push(word);
        while (!stack.empty()) {
            string w = stack.top();
            stack.pop();
            if (synonyms.insert(w).second) {
                for (const string& neighbor : graph[w]) {
                    stack.push(neighbor);
                }
            }
        }
        return vector<string>(synonyms.begin(), synonyms.end());
    }

    void generate(vector<string>& sentences, const vector<vector<string>>& groups, string& sentence, int index) {
        if (index == groups.size()) {
            sentences.push_back(sentence.substr(1));
            return;
        }
        for (const string& word : groups[index]) {
            string original = sentence;
            sentence += " " + word;
            generate(sentences, groups, sentence, index + 1);
            sentence = original;
        }
    }
};

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

Задача: 683. K Empty Slots Сложность: hard У вас есть n лампочек, расположенных в ряд и пронумерованных от 1 до n. Изначально все лампочки выключены. Каждый день мы включаем ровно одну лампочку, и через n дней все лампочки будут включены. Вам дан массив bulbs длины n, где bulbs[i] = x означает, что в (i+1)-й день мы включим лампочку в позиции x, где i индексируется с 0, а x индексируется с 1. Дано целое число k, верните минимальный номер дня, такой что существует две включенные лампочки, между которыми ровно k выключенных лампочек. Если такого дня не существует, верните -1. Пример:

Input: bulbs = [1,3,2], k = 1
Output: 2
Explanation:
On the first day: bulbs[0] = 1, first bulb is turned on: [1,0,0]
On the second day: bulbs[1] = 3, third bulb is turned on: [1,0,1]
On the third day: bulbs[2] = 2, second bulb is turned on: [1,1,1]
We return 2 because on the second day, there were two on bulbs with one off bulb between them.

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

#include <set>
#include <vector>

class Solution {
public:
    int kEmptySlots(std::vector<int>& flowers, int k) {
        std::set<int> active;
        int day = 0;
        
        for (int flower : flowers) {
            day++;
            active.insert(flower);
            auto lower = active.lower_bound(flower);
            auto higher = active.upper_bound(flower);
            
            if (lower != active.begin() && flower - *std::prev(lower) - 1 == k) {
                return day;
            }
            if (higher != active.end() && *higher - flower - 1 == k) {
                return day;
            }
        }
        return -1;
    }
};

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

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

Задача: 333. Largest BST Subtree Сложность: medium Дан корень бинарного дерева, найдите самое большое поддерево, которое также является деревом бинарного поиска (BST), где "самое большое" означает поддерево с наибольшим количеством узлов. Дерево бинарного поиска (BST) — это дерево, в котором все узлы соблюдают следующие свойства: Значения в левом поддереве меньше значения их родительского (корневого) узла. Значения в правом поддереве больше значения их родительского (корневого) узла. Примечание: Поддерево должно включать всех своих потомков. Пример:

Input: root = [10,5,15,1,8,null,7]
Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.

👨‍💻 Алгоритм: 1⃣Пост-упорядоченный обход дерева: Обходите каждую ноду дерева в пост-упорядоченном порядке (left-right-root). Это позволит гарантировать, что обе поддеревья ноды уже проверены на соответствие критериям BST перед проверкой самой ноды. 2⃣Проверка условий BST для каждой ноды: Для каждой ноды определите минимальное и максимальное значения в её левом и правом поддеревьях. Проверьте, удовлетворяет ли текущее поддерево условиям BST: - значение текущей ноды должно быть больше максимального значения в левом поддереве. - значение текущей ноды должно быть меньше минимального значения в правом поддереве. Если условия выполняются, вычислите размер текущего поддерева как сумму размеров левого и правого поддеревьев плюс 1 (для текущей ноды). 3⃣Возврат максимального размера BST: Если текущее поддерево не является BST, верните максимальный размер BST из его левого или правого поддерева. В конце рекурсивного обхода верните максимальный размер BST в дереве. 😎 Решение:

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

class NodeValue {
public:
    int minNode, maxNode, maxSize;
    
    NodeValue(int minNode, int maxNode, int maxSize) : 
        minNode(minNode), maxNode(maxNode), maxSize(maxSize) {}
};

class Solution {
public:
    NodeValue largestBSTSubtreeHelper(TreeNode* root) {
        if (root == nullptr) {
            return NodeValue(INT_MAX, INT_MIN, 0);
        }
        
        NodeValue left = largestBSTSubtreeHelper(root->left);
        NodeValue right = largestBSTSubtreeHelper(root->right);
        
        if (left.maxNode < root->val && root->val < right.minNode) {
            return NodeValue(min(root->val, left.minNode), max(root->val, right.maxNode), 
                             left.maxSize + right.maxSize + 1);
        }
        
        return NodeValue(INT_MIN, INT_MAX, max(left.maxSize, right.maxSize));
    }
    
    int largestBSTSubtree(TreeNode* root) {
        return largestBSTSubtreeHelper(root).maxSize;
    }
};

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

Задача: 1095. Find in Mountain Array Сложность: hard Массив arr является горным массивом тогда и только тогда, когда: Длина массива arr >= 3. Существует некоторое i с 0 < i < arr.length - 1 такое, что: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > ... > arr[arr.length - 1] Дан горный массив mountainArr, верните минимальный индекс, такой что mountainArr.get(index) == target. Если такого индекса не существует, верните -1. Вы не можете напрямую обращаться к массиву. Вы можете использовать интерфейс MountainArray: MountainArray.get(k) возвращает элемент массива на индексе k (индексация начинается с 0). MountainArray.length() возвращает длину массива. Решения, использующие более 100 вызовов MountainArray.get, будут оценены как неправильные. Также любые решения, которые пытаются обойти ограничение, будут дисквалифицированы. Пример:

Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

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

class Solution {
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int length = mountainArr.length();

        int low = 1, high = length - 2;
        while (low != high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        int peak = low;

        low = 0, high = peak;
        while (low < high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (mountainArr.get(low) == target) {
            return low;
        }

        low = peak + 1, high = length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) > target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (mountainArr.get(low) == target) {
            return low;
        }

        return -1;
    }
};

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

Методичка: как сделать онлайн-встречи эффективнее Надоело ждать коллег, которые постоянно забывают о встречах, а отсутствие повестки и потерянные договоренности мешают нормально работать? Команда МТС Линк собрала на 37 страницах полезные материалы, чек-листы и кейсы, которые помогают компаниям проводить эффективные совещания в онлайне с помощью сервиса Встречи. Из методички узнаете: - Как создать постоянную ссылку и подключаться на встречи в 2 клика, - Как делать заметки и работать с файлами, не переживая за качество связи и безопасность данных. - Как облегчает жизнь ИИ, который расшифровывает созвоны в текст и автоматически отправляет расшифровку на почту. Еще в методичке описаны 7 способов оценки текущей эффективности ваших онлайн-встреч. Получить гайд можно бесплатно на сайте. Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 1228. Missing Number In Arithmetic Progression Сложность: easy В массиве arr значения находились в арифметической прогрессии: значения arr[i + 1] - arr[i] равны для всех 0 <= i < arr.length - 1. Из массива arr было удалено значение, которое не было первым или последним значением в массиве. Дан массив arr, вернуть удаленное значение. Пример:

Input: arr = [5,7,11,13]
Output: 9
Explanation: The previous array was [5,7,9,11,13].

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

class Solution {
public:
    int missingNumber(vector<int>& arr) {
        int n = arr.size();
        int difference = (arr[n - 1] - arr[0]) / n;
        int expected = arr[0];

        for (int val : arr) {
            if (val != expected) {
                return expected;
            }
            expected += difference;
        }
        return expected;
    }
};

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

Как устроена работа команды контакт-центра Руководитель из Альфа-Банка рассказала о том, как не только организовать, но и замотивировать своих сотрудников на новые свершения. А ещё развеяла миф о стрессовой работе в контакт-центре. В новом выпуске вы узнаете: - Как сотрудники влияют на развитие внутренних процессов компании; - Что позволяет объединять команду даже на удалёнке; - Какие тренинги помогают решать конфликты с клиентами; - И как организована система наставничества и менторства в Альфа-Банке. Слушайте подкаст на любой доступной площадке и узнавайте ещё больше карьерных секретов. Слушать #реклама 16+ redbarn.ru О рекламодателе

Задача: 537. Complex Number Multiplication Сложность: medium Комплексное число можно представить в виде строки в формате "real+imaginaryi", где: real — это действительная часть и является целым числом в диапазоне [-100, 100]. imaginary — это мнимая часть и является целым числом в диапазоне [-100, 100]. i^2 == -1. Даны два комплексных числа num1 и num2 в виде строк, верните строку комплексного числа, представляющую их произведение. Пример:

Input: num1 = "1+1i", num2 = "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.

👨‍💻 Алгоритм: 1⃣ Извлечение реальной и мнимой частей: Разделите строки a и b на реальные и мнимые части, используя символы '+' и 'i'. 2⃣ Вычисление произведения: Переведите извлечённые части в целые числа. Используйте формулу для умножения комплексных чисел: (a+ib)×(x+iy)=ax−by+i(bx+ay). 3⃣ Формирование строки результата: Создайте строку в требуемом формате с реальной и мнимой частями произведения и верните её. 😎 Решение:

class Solution {
public:
    string complexNumberMultiply(string a, string b) {
        auto x = split(a);
        auto y = split(b);
        int a_real = stoi(x[0]);
        int a_img = stoi(x[1]);
        int b_real = stoi(y[0]);
        int b_img = stoi(y[1]);
        int realPart = a_real * b_real - a_img * b_img;
        int imaginaryPart = a_real * b_img + a_img * b_real;
        return to_string(realPart) + "+" + to_string(imaginaryPart) + "i";
    }

private:
    vector<string> split(const string &s) {
        size_t plus = s.find('+');
        size_t i = s.find('i');
        return {s.substr(0, plus), s.substr(plus + 1, i - plus - 1)};
    }
};

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

Задача: 1423. Maximum Points You Can Obtain from Cards Сложность: medium Есть несколько карт, расположенных в ряд, и у каждой карты есть определенное количество очков. Очки представлены в виде целочисленного массива cardPoints. За один шаг вы можете взять одну карту либо с начала, либо с конца ряда. Вы должны взять ровно k карт. Ваш результат - это сумма очков взятых карт. Дан целочисленный массив cardPoints и целое число k, верните максимальное количество очков, которое вы можете получить. Пример:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

👨‍💻 Алгоритм: 1⃣Инициализируйте два массива размера k + 1, frontSetOfCards и rearSetOfCards, чтобы хранить суммы очков, полученных при выборе первых i карт и последних i карт в массиве. 2⃣Рассчитайте префиксные суммы для первых k карт и последних k карт. 3⃣Итерируйте от 0 до k и вычисляйте возможное количество очков, выбирая i карт с начала массива и k - i карт с конца, обновляя максимальный результат при необходимости. 😎 Решение:

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int n = cardPoints.size();
        vector<int> frontSetOfCards(k + 1, 0);
        vector<int> rearSetOfCards(k + 1, 0);
        
        for (int i = 0; i < k; ++i) {
            frontSetOfCards[i + 1] = cardPoints[i] + frontSetOfCards[i];
            rearSetOfCards[i + 1] = cardPoints[n - i - 1] + rearSetOfCards[i];
        }
        
        int maxScore = 0;
        for (int i = 0; i <= k; ++i) {
            int currentScore = frontSetOfCards[i] + rearSetOfCards[k - i];
            maxScore = max(maxScore, currentScore);
        }
        
        return maxScore;
    }
};

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

СберМобайл - 50 Гб и 300 минут за 390 рублей! СберМобайл - дарим 30 Гб каждый месяц при переносе номера. Безлимит на мессенджеры. Защита от спама. eSIM за 5 минут. Подключайтесь. Перейти на сайт #реклама sbermobile.ru О рекламодателе

Задача: 811. Subdomain Visit Count Сложность: medium Веб-сайт с доменом "discuss.leetcode.com" состоит из различных поддоменов. На верхнем уровне у нас есть "com", на следующем уровне - "leetcode.com", и на самом нижнем уровне - "discuss.leetcode.com". Когда мы посещаем домен, такой как "discuss.leetcode.com", мы также автоматически посещаем родительские домены "leetcode.com" и "com". Домен с парным счетчиком - это домен, который имеет один из двух форматов "rep d1.d2.d3" или "rep d1.d2", где rep - это количество посещений домена, а d1.d2.d3 - это сам домен. Например, "9001 discuss.leetcode.com" - это домен с парным счетчиком, указывающий на то, что discuss.leetcode.com был посещен 9001 раз. Дан массив доменов с парными счетчиками cpdomains, верните массив доменов с парными счетчиками для каждого поддомена во входных данных. Вы можете вернуть ответ в любом порядке. Пример:

Input: cpdomains = ["9001 discuss.leetcode.com"]
Output: ["9001 leetcode.com","9001 discuss.leetcode.com","9001 com"]
Explanation: We only have one website domain: "discuss.leetcode.com".
As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

👨‍💻 Алгоритм: 1⃣Следуем указаниям из условия задачи. 2⃣Для адреса вида a.b.c, подсчитываем a.b.c, b.c и c. Для адреса вида x.y, подсчитываем x.y и y. 3⃣Для подсчета этих строк используем хеш-таблицу. Для разделения строк на требуемые части используем библиотечные функции split. 😎 Решение:

#include <vector>
#include <string>
#include <unordered_map>
#include <sstream>

using namespace std;

class Solution {
public:
    vector<string> subdomainVisits(vector<string>& cpdomains) {
        unordered_map<string, int> ans;
        for (const string& domain : cpdomains) {
            istringstream iss(domain);
            int count;
            string domain;
            iss >> count >> domain;
            vector<string> frags;
            istringstream fragStream(domain);
            string frag;
            while (getline(fragStream, frag, '.')) {
                frags.push_back(frag);
            }
            for (size_t i = 0; i < frags.size(); ++i) {
                string subdomain;
                for (size_t j = i; j < frags.size(); ++j) {
                    if (j > i) subdomain += ".";
                    subdomain += frags[j];
                }
                ans[subdomain] += count;
            }
        }
        vector<string> res;
        for (const auto& p : ans) {
            res.push_back(to_string(p.second) + " " + p.first);
        }
        return res;
    }
};

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

Получи грант до 1,2 млн руб. на обучение в магистратуре 4 офлайн программы, онлайн-магистратура по ML. Гранты до 1,2 млн руб. Стажировки, диплом гос. образца и фокус на твоей карьере в ЦУ Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 496. Next Greater Element I Сложность: easy Следующий больший элемент для некоторого элемента x в массиве — это первый больший элемент, который находится справа от x в том же массиве. Вам даны два различных целочисленных массива с индексами, начинающимися с 0: nums1 и nums2, где nums1 является подмножеством nums2. Для каждого 0 <= i < nums1.length найдите индекс j, такой что nums1[i] == nums2[j], и определите следующий больший элемент для nums2[j] в nums2. Если следующего большего элемента нет, то ответ для этого запроса — -1. Верните массив ans длиной nums1.length, где ans[i] — это следующий больший элемент, как описано выше. Пример:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

👨‍💻 Алгоритм: 1⃣Инициализация и поиск совпадений Создайте массив res для хранения результатов. Для каждого элемента nums1[i] найдите его индекс j в массиве nums2. 2⃣Поиск следующего большего элемента После нахождения индекса j в nums2 начните поиск элемента справа от nums2[j], который больше nums1[i]. Если такой элемент найден, добавьте его в res. 3⃣Заполнение результата Если следующий больший элемент не найден, добавьте -1 в соответствующую позицию res. Верните массив res. 😎 Решение:

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res(nums1.size(), -1);
        
        for (int i = 0; i < nums1.size(); i++) {
            bool found = false;
            for (int j = 0; j < nums2.size(); j++) {
                if (nums2[j] == nums1[i]) {
                    found = true;
                }
                if (found && nums2[j] > nums1[i]) {
                    res[i] = nums2[j];
                    break;
                }
            }
        }
        
        return res;
    }
};

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

Продолжение следует в «Летово Игра» ✨Стоит сделать первый шаг в «Летово» — и привычное лето превращается в межгалактическое приключение. Летающие тарелки на горизонте, учёные ловят таинственные сигналы, чтобы встать на защиту планеты, нужно быть готовым к новым открытиям и испытаниям. «Летово Игра» — это образовательная игра для подростков 10–17 лет, созданная на базе школы «Летово» лучшими педагогами и опытными игротехниками. Знания и навыки здесь осваиваются не за партой, а через действия, вызовы и работу в команде. Каждый день - это шаг в неизведанное: новые вызовы, важные задачи, совместные решения.😊 📅Смены длятся 10 дней и стартуют с 1 июля. Количество мест ограничено. Подать заявку #реклама 16+ letovogame.ru О рекламодателе

Задача: 540. Single Element in a Sorted Array Сложность: medium Дан отсортированный массив, состоящий только из целых чисел, где каждый элемент встречается ровно дважды, кроме одного элемента, который встречается ровно один раз. Верните единственный элемент, который встречается только один раз. Ваше решение должно работать за время O(log n) и использовать O(1) памяти. Пример:

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

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

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        for (int i = 0; i < nums.size() - 1; i += 2) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums.back();
    }
};

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

Внимание родителям учеников 5–11 классов! Если вы чувствуете, что традиционная школа не раскрывает потенциал вашего ребёнка — пришло время действовать. SOTKA.PREMIUM — элитная образовательная программа от онлайн-школы «Сотка», резидента «Сколково» и обладателя лицензии Министерства образования РФ. Что получает ваш ребенок: ✅ Персональный образовательный трек и занятия с ведущими педагогами страны ✅ Менторство от студентов МГУ, ВШЭ и других топ-вузов ✅ Развитие навыков будущего: от критического мышления до работы с нейросетями ✅ Участие в олимпиадах, проектах, летних выездных сборах и офлайн-лагере ⚡Главное: программа гарантирует поступление в ведущие вузы страны. Сейчас открыто всего 7 мест. При записи — бесплатная аналитика сильных сторон ребёнка в подарок. Записаться #реклама 16+ mrqz.me О рекламодателе

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

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

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

class Solution {
public:
    int mod = 1_000_000_007;

    int dfs(vector<int>& dp, int start, const string& s, int k) {
        if (dp[start] != 0) return dp[start];
        if (start == s.size()) return 1;
        if (s[start] == '0') return 0;

        long count = 0;
        for (int end = start; end < s.size(); ++end) {
            string currNumber = s.substr(start, end - start + 1);
            if (stol(currNumber) > k) break;
            count = (count + dfs(dp, end + 1, s, k)) % mod;
        }

        dp[start] = count;
        return count;
    }

    int numberOfArrays(string s, int k) {
        vector<int> dp(s.size() + 1);
        return dfs(dp, 0, s, k);
    }
};

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