C/C++ | LeetCode

Задача: 936. Stamping The Sequence Сложность: hard Вам даны две строки stamp и target. Изначально имеется строка s длины target.length со всеми s[i] == '?'. За один ход вы можете поместить штамп над s и заменить каждую букву в s на соответствующую букву из штампа. Например, если штамп = "abc" и target = "abcba", то s изначально будет "?????". За один ход вы можете: поместить штамп в индекс 0 s, чтобы получить "abc??", поместить штамп в индекс 1 s, чтобы получить "?abc?", или поместить штамп в индекс 2 s, чтобы получить "??abc". Обратите внимание, что штамп должен полностью находиться в границах s, чтобы штамповать (то есть вы не можете поместить штамп в индекс 3 s). Мы хотим преобразовать s в цель, используя не более 10 * target.length ходов. Верните массив индекса самой левой буквы, которая штампуется на каждом ходу. Если мы не можем получить цель из s за 10 * target.length оборотов, верните пустой массив Пример:

Input: stamp = "abc", target = "ababc"
Output: [0,2]

👨‍💻 Алгоритм: 1⃣Инициализировать переменные: s как массив символов '?', длиной target.length. res как список для хранения результатов. done как массив булевых значений для отслеживания того, какие позиции уже штампованы. target как массив символов для удобства. 2⃣Использовать функцию canStamp для проверки, можно ли штамповать stamp в target начиная с индекса i. Использовать функцию doStamp для штампования stamp в target начиная с индекса i. Повторять шаги, пока штампы возможны или достигнут максимум ходов (10 * target.length): Перебрать все возможные начальные позиции для штампа. Проверить, можно ли штамповать в текущей позиции. Если можно, штамповать и добавить индекс в res. 3⃣Если все символы в s соответствуют символам в target, вернуть массив res в обратном порядке. Иначе, вернуть пустой массив. 😎 Решение:

class Solution {
public:
    vector<int> movesToStamp(string stamp, string target) {
        vector<int> res;
        vector<bool> done(target.size(), false);
        string t = target;
        string s = stamp;
        int m = s.size(), n = t.size();
        
        auto canStamp = [&](int i) {
            for (int j = 0; j < m; j++) {
                if (t[i + j] != '?' && t[i + j] != s[j]) {
                    return false;
                }
            }
            return true;
        };
        
        auto doStamp = [&](int i) {
            for (int j = 0; j < m; j++) {
                t[i + j] = '?';
            }
            res.push_back(i);
            done[i] = true;
        };
        
        bool changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i <= n - m; i++) {
                if (!done[i] && canStamp(i)) {
                    doStamp(i);
                    changed = true;
                }
            }
        }
        
        for (char c : t) {
            if (c != '?') {
                return {};
            }
        }
        
        reverse(res.begin(), res.end());
        return res;
    }
};

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

Стартуй в бизнесе на ИЗЗЗИ вместе со Сбером Открой счёт за 0 рублей и получи: ✅ До 100 000 бонусов СберБизнес Спасибо на полезные сервисы ✅ Избавление от рутины: бесплатная бухгалтерия для бизнеса на 6 месяцев Это твой знак начать своё дело! Узнать больше Финансовые услуги оказывает: ПАО Сбербанк. #реклама sberbank.com О рекламодателе

Задача: 426. Convert Binary Search Tree to Sorted Doubly Linked List Сложность: medium Преобразуйте двоичное дерево поиска в отсортированный кольцевой двусвязный список на месте. Вы можете считать, что указатели "влево" и "вправо" аналогичны указателям на предшественника и последователя в двусвязном списке. Для кольцевого двусвязного списка предшественник первого элемента является последним элементом, а последователь последнего элемента является первым элементом. Мы хотим выполнить преобразование на месте. После преобразования левый указатель узла дерева должен указывать на его предшественника, а правый указатель должен указывать на его последователя. Вы должны вернуть указатель на самый маленький элемент списка. Пример:

Input: root = [4,2,5,1,3]
Output: [1,2,3,4,5]
Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

👨‍💻 Алгоритм: 1⃣Инициализируйте первые и последние узлы как null. 2⃣Вызовите стандартную вспомогательную рекурсивную функцию helper(root): Если узел не равен null: Вызовите рекурсию для левого поддерева helper(node.left). Если последний узел не равен null, свяжите последний узел и текущий узел. Иначе инициализируйте первый узел. Пометьте текущий узел как последний: last = node. Вызовите рекурсию для правого поддерева helper(node.right). 3⃣Свяжите первые и последние узлы, чтобы замкнуть кольцевой двусвязный список, затем верните первый узел. 😎 Решение:

class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};

class Solution {
public:
    Node* first = NULL;
    Node* last = NULL;

    void helper(Node* node) {
        if (node != NULL) {
            helper(node->left);

            if (last != NULL) {
                last->right = node;
                node->left = last;
            } else {
                first = node;
            }
            last = node;

            helper(node->right);
        }
    }

    Node* treeToDoublyList(Node* root) {
        if (root == NULL) return NULL;

        helper(root);

        last->right = first;
        first->left = last;
        return first;
    }
};

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

Освойте профессию Системный аналитик с нуля за 7 месяцев Освойте высокооплачиваемую IT-профессию без программирования. Выдаём диплом, помогаем с трудоустройством. Excel, BPMN, UML, Python, SQL, API Преимущества обучения в Академии Eduson: 🎓 22 реальных бизнес-кейса 🎓 официальный государственный диплом 🎓 рассрочка 0% на 24 мес. 🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать доход уже во время обучения! Получить скидку #реклама 16+ mrqz.me О рекламодателе

Задача: 318. Maximum Product of Word Lengths Сложность: medium Дан массив строк words, верните максимальное значение произведения длины word[i] на длину word[j], где два слова не имеют общих букв. Если таких двух слов не существует, верните 0. Пример:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

👨‍💻 Алгоритм: 1⃣Предварительная обработка масок и длин Вычислите битовые маски для всех слов и сохраните их в массиве masks. Сохраните длины всех слов в массиве lens. 2⃣Сравнение слов и проверка общих букв Сравните каждое слово с каждым последующим словом. Если два слова не имеют общих букв (проверка с использованием масок: (masks[i] & masks[j]) == 0), обновите максимальное произведение maxProd. 3⃣Возврат результата Верните максимальное значение произведения maxProd. 😎 Решение:

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = words.size();
        vector<int> masks(n);
        vector<int> lens(n);
        
        for (int i = 0; i < n; i++) {
            int bitmask = 0;
            for (char ch : words[i]) {
                bitmask |= 1 << (ch - 'a');
            }
            masks[i] = bitmask;
            lens[i] = words[i].size();
        }
        
        int maxVal = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    maxVal = max(maxVal, lens[i] * lens[j]);
                }
            }
        }
        return maxVal;
    }
};

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

Задача: 665. Non-decreasing Array Сложность: medium Дан массив nums из n целых чисел. Ваша задача - проверить, можно ли сделать его неубывающим, изменив не более одного элемента. Мы определяем массив как неубывающий, если для каждого i (индексация с 0), такого что 0 <= i <= n - 2, выполняется условие nums[i] <= nums[i + 1]. Пример:

Input: nums = [4,2,3]
Output: true
Explanation: You could modify the first 4 to 1 to get a non-decreasing array.

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Завести переменную count для подсчета числа изменений. Проверить последовательность чисел в массиве nums. 2⃣Проверка условий: Если nums[i] > nums[i + 1], то увеличиваем count. Если count превышает 1, возвращаем false, так как больше одного изменения недопустимо. Если nums[i - 1] > nums[i + 1] и nums[i] > nums[i + 2], то возвращаем false. 3⃣вВозврат результата: Если количество изменений не превышает 1, вернуть true. 😎 Решение:

class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        int count = 0;
        
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < nums[i - 1]) {
                if (count > 0) {
                    return false;
                }
                count++;
                if (i == 1 || nums[i] >= nums[i - 2]) {
                    nums[i - 1] = nums[i];
                } else {
                    nums[i] = nums[i - 1];
                }
            }
        }
        
        return true;
    }
};

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

Получи грант на обучение в Центральном университете Центральный университет выдает гранты на 4 года обучения в бакалавриате. Грант покрывает до 100% стоимости обучения. Участвуй в отборе, чтобы получить грант. Получи доступ к уникальным активностям для абитуриентов. Для выпускников 10-х, 11-х классов и колледжей. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 289. Game of Life Сложность: medium Согласно статье Википедии: "Игра Жизнь, также известная просто как Жизнь, — это клеточный автомат, созданный британским математиком Джоном Хортоном Конуэем в 1970 году." Доска состоит из сетки клеток размером m x n, где каждая клетка имеет начальное состояние: живая (представляется числом 1) или мёртвая (представляется числом 0). Каждая клетка взаимодействует с восемью соседями (по горизонтали, вертикали и диагоналям) согласно следующим четырём правилам (взято из вышеупомянутой статьи Википедии): Любая живая клетка с менее чем двумя живыми соседями умирает, как будто из-за недостатка населения. Любая живая клетка с двумя или тремя живыми соседями остаётся живой до следующего поколения. Любая живая клетка с более чем тремя живыми соседями умирает, как будто из-за перенаселения. Любая мёртвая клетка с ровно тремя живыми соседями становится живой, как будто вследствие размножения. Следующее состояние создаётся путем одновременного применения вышеупомянутых правил ко всем клеткам в текущем состоянии, где рождения и смерти происходят одновременно. Дано текущее состояние сетки m x n, верните следующее состояние. Пример:

Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

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

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        vector<int> neighbors = {0, 1, -1};
        int rows = board.size();
        int cols = board[0].size();

        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                int liveNeighbors = 0;
                for (int i : neighbors) {
                    for (int j : neighbors) {
                        if (!(i == 0 && j == 0)) {
                            int r = row + i;
                            int c = col + j;
                            if (r >= 0 && r < rows && c >= 0 && c < cols && abs(board[r][c]) == 1) {
                                liveNeighbors++;
                            }
                        }
                    }
                }

                if (board[row][col] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    board[row][col] = -1;
                }
                if (board[row][col] == 0 && liveNeighbors == 3) {
                    board[row][col] = 2;
                }
            }
        }

        for (int row = 0; row < rows; ++row) {
            for (int col = 0; col < cols; ++col) {
                board[row][col] = (board[row][col] > 0) ? 1 : 0;
            }
        }
    }
};

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

Data и ML для бизнеса. Большая конференция Яндекса Узнайте, как ускорить создание продуктов, упростить процессы и снизить расходы. Зарегистрироваться #реклама 16+ yandex.cloud О рекламодателе Реклама на Яндексе

Задача: 682. Baseball Game Сложность: medium Вы ведете учет очков в бейсбольной игре с необычными правилами. В начале игры у вас пустая запись. Вам дается список строк operations, где operations[i] — это i-я операция, которую вы должны применить к записи, и она может быть одной из следующих: Целое число x. Записать новый счет, равный x. '+'. Записать новый счет, который является суммой двух предыдущих очков. 'D'. Записать новый счет, который в два раза больше предыдущего очка. 'C'. Аннулировать предыдущее очко, удалив его из записи. Верните сумму всех очков в записи после применения всех операций. Тестовые случаи сформированы таким образом, что ответ и все промежуточные вычисления умещаются в 32-битное целое число, и что все операции корректны. Пример:

Input: ops = ["5","2","C","D","+"]
Output: 30
Explanation:
"5" - Add 5 to the record, record is now [5].
"2" - Add 2 to the record, record is now [5, 2].
"C" - Invalidate and remove the previous score, record is now [5].
"D" - Add 2 * 5 = 10 to the record, record is now [5, 10].
"+" - Add 5 + 10 = 15 to the record, record is now [5, 10, 15].
The total sum is 5 + 10 + 15 = 30.

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

class Solution {
public:
    int calPoints(vector<string>& ops) {
        stack<int> stack;

        for (string op : ops) {
            if (op == "+") {
                int top = stack.top();
                stack.pop();
                int newTop = top + stack.top();
                stack.push(top);
                stack.push(newTop);
            } else if (op == "C") {
                stack.pop();
            } else if (op == "D") {
                stack.push(2 * stack.top());
            } else {
                stack.push(stoi(op));
            }
        }

        int ans = 0;
        while (!stack.empty()) {
            ans += stack.top();
            stack.pop();
        }
        return ans;
    }
};

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

Битрикс24 дропнул новую фичу — онлайн-доски Теперь к вашему рабочему мессенджеру, видеозвонкам и таскам добавился еще один маст-хэв инструмент. Все это бесплатно и в одном комплекте. Офисные стикеры, берегитесь.😊 Узнать больше #реклама 16+ bitrix24.ru О рекламодателе

Задача: 186. Reverse Words in a String II Сложность: medium Дан массив символов s, переверните порядок слов. Слово определяется как последовательность символов, не являющихся пробелами. Слова в s разделены одним пробелом. Решение должно быть in-place, без использования дополнительной памяти. Пример:

Input: s = ["a"] Output: ["a"]

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

class Solution {
public:
    void reverseWords(vector<char>& s) {
        reverse(s.begin(), s.end());
        int start = 0, end = 0;
        int n = s.size();

        while (start < n) {
            while (end < n && s[end] != ' ')
                end++;
            reverse(s.begin() + start, s.begin() + end);
            end++;
            start = end;
        }
    }
};

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

Подключите спутниковый интернет за городом. Доступно Интернет там, где нужно - для офиса или загородного дома. Мы предлагаем: 👍Высокую скорость до 100 Мбит/с. 👍Доступные цены на оборудование и установку. 👍Выгодные тарифы, как для частных домовладельцев, так и для коллективных подключений. 👍Надежное подключение во всех регионах России. Подобрать подходящий вам тариф и оставить заявку на подключение - по ссылке ниже! Узнать больше #реклама radiointernet1.ru О рекламодателе

Задача: 1429. First Unique Number Сложность: medium У вас есть очередь целых чисел, необходимо извлечь первый уникальный элемент из очереди. Реализуйте класс FirstUnique: - FirstUnique(int[] nums) Инициализирует объект числами в очереди. - int showFirstUnique() возвращает значение первого уникального элемента в очереди и возвращает -1, если такого элемента нет. - void add(int value) вставляет значение в очередь. Пример:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output: 
[null,2,null,2,null,3,null,-1]
Explanation: 
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5);            // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2);            // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1

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

#include <unordered_map>
#include <unordered_set>
#include <list>

class FirstUnique {
public:
    FirstUnique(vector<int>& nums) {
        for (int num : nums) {
            add(num);
        }
    }
    
    int showFirstUnique() {
        if (!queue.empty()) {
            return queue.front();
        }
        return -1;
    }
    
    void add(int value) {
        if (isUnique.find(value) == isUnique.end()) {
            isUnique[value] = true;
            queue.push_back(value);
        } else if (isUnique[value]) {
            isUnique[value] = false;
            queue.remove(value);
        }
    }
    
private:
    list<int> queue;
    unordered_map<int, bool> isUnique;
};

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

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

Задача: 211. Design Add and Search Words Data Structure Сложность: medium Необходимо реализовать структуру данных, которая позволяет: addWord(word) — добавлять слова search(word) — искать слова с поддержкой символа ".", обозначающего любую букву Пример:

pgsqlКопироватьРедактироватьWordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // false
wordDictionary.search("bad"); // true
wordDictionary.search(".ad"); // true
wordDictionary.search("b.."); // true

👨‍💻 Алгоритм: 1⃣Добавление слова (addWord) Используем структуру Trie (префиксное дерево). Если буква из слова отсутствует в текущем узле, создаём новую. После вставки всех букв устанавливаем флаг word = true. 2⃣Поиск слова (search) Запускаем рекурсивную функцию searchInNode(word, node). Если текущий символ — ., пробуем все возможные пути в дереве. Если обычный символ — продолжаем по соответствующей ветке. Если путь закончился, проверяем флаг word. 3⃣Обработка подстановки (.) Поддержка символа . реализуется через рекурсивный вызов searchInNode для всех дочерних узлов. 😎 Решение:

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool word = false;
};

class WordDictionary {
    TrieNode* trie;

public:
    WordDictionary() { trie = new TrieNode(); }

    void addWord(string word) {
        TrieNode* node = trie;
        for (char ch : word) {
            if (!node->children.count(ch)) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->word = true;
    }

    bool searchInNode(string word, TrieNode* node) {
        for (int i = 0; i < word.length(); ++i) {
            char ch = word[i];
            if (!node->children.count(ch)) {
                if (ch == '.') {
                    for (auto x : node->children) {
                        TrieNode* child = x.second;
                        if (searchInNode(word.substr(i + 1), child)) {
                            return true;
                        }
                    }
                }
                return false;
            } else {
                node = node->children[ch];
            }
        }
        return node->word;
    }

    bool search(string word) { return searchInNode(word, trie); }
};

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

Задача: 1202. Smallest String With Swaps Сложность: medium Вам дана строка s и массив пар индексов в строке pairs, где pairs[i] = [a, b] указывает на 2 индекса (начиная с 0) в строке. Вы можете менять местами символы в любой паре индексов в заданных парах любое количество раз. Верните лексикографически наименьшую строку, которую можно получить после выполнения перестановок. Пример:

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination: 
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"

👨‍💻 Алгоритм: 1⃣Создание списка смежности: Итеративно пройдитесь по парам и создайте список смежности adj, где adj[source] содержит все смежные вершины вершины source. 2⃣Обход графа и сбор индексов и символов: Итеративно пройдитесь по индексам от 0 до s.size() - 1. Для каждого индекса vertex: - выполните DFS, если вершина еще не посещена (visited[vertex] = false). - во время выполнения DFS сохраняйте vertex в список indices и символ s[vertex] в список characters. 3⃣Сортировка и построение результирующей строки: Отсортируйте списки indices и characters. Пройдитесь по индексам и символам, и разместите i-й символ в i-й индекс результирующей строки smallestString. Верните smallestString. 😎 Решение:

class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        int n = s.size();
        vector<vector<int>> adj(n);
        for (auto& p : pairs) {
            adj[p[0]].push_back(p[1]);
            adj[p[1]].push_back(p[0]);
        }

        vector<bool> visited(n, false);
        vector<char> sArray(s.begin(), s.end());
        
        function<void(int, vector<int>&, vector<char>&)> dfs = [&](int node, vector<int>& indices, vector<char>& chars) {
            visited[node] = true;
            indices.push_back(node);
            chars.push_back(sArray[node]);
            for (int neighbor : adj[node]) {
                if (!visited[neighbor]) {
                    dfs(neighbor, indices, chars);
                }
            }
        };

        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                vector<int> indices;
                vector<char> chars;
                dfs(i, indices, chars);
                sort(indices.begin(), indices.end());
                sort(chars.begin(), chars.end());
                for (int j = 0; j < indices.size(); ++j) {
                    sArray[indices[j]] = chars[j];
                }
            }
        }

        return string(sArray.begin(), sArray.end());
    }
};

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

Высшее образование онлайн — поменяйте жизнь в 2025 году! ✅Набор в мае: от 6700 ₽/мес.* Московский технологический институт предлагает: — Высшее образование в московском вузе без выезда на сессии — Полностью дистанционный онлайн-формат — Возможность обучаться дома, на работе, в путешествии — Диплом государственного образца — Более 60 направлений на выбор (IT, инженерные, экономические, педагогические, управленческие и другие) — 5 способов оплаты обучения — Поддержка персонального куратора: от поступления до получения диплома Узнать больше #реклама 16+ mti-vuz.ru О рекламодателе

Задача: 74. Search a 2D Matrix Сложность: medium Вам дана матрица из целых чисел размером m на n с следующими двумя свойствами: Каждая строка отсортирована в порядке не убывания. Первое число каждой строки больше последнего числа предыдущей строки. Дано целое число target. Верните true, если target присутствует в матрице, и false в противном случае. Вы должны написать решение с временной сложностью O(log(m * n)). Пример:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

👨‍💻 Алгоритм: 1⃣Инициализируйте индексы слева и справа: left = 0 и right = m * n - 1. 2⃣Пока left <= right: вычисляйте pivot_idx = (left + right) / 2. 3⃣Получите координаты элемента: row = pivot_idx // n, col = pivot_idx % n, затем сравните pivot_element = matrix[row][col] с target, чтобы решить, в какой части продолжать поиск. 😎 Решение:

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if (m == 0)
            return false;

        int n = matrix[0].size();
        int left = 0, right = m * n - 1;
        int pivotIdx, pivotElement;
        while (left <= right) {
            pivotIdx = (left + right) / 2;
            pivotElement = matrix[pivotIdx / n][pivotIdx % n];
            if (target == pivotElement)
                return true;
            else {
                if (target < pivotElement)
                    right = pivotIdx - 1;
                else
                    left = pivotIdx + 1;
            }
        }
        return false;
    }
};

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

Задача: 826. Most Profit Assigning Work Сложность: medium У вас есть n заданий и m рабочих. Вам даны три массива: difficulty, profit и worker, где: difficulty[i] и profit[i] — сложность и прибыль i-го задания, worker[j] — способность j-го рабочего (т.е. j-й рабочий может выполнить задание со сложностью не больше worker[j]). Каждому рабочему можно назначить не более одного задания, но одно задание может быть выполнено несколько раз. Например, если три рабочих выполняют одно и то же задание с оплатой $1, общая прибыль составит $3. Если рабочий не может выполнить ни одно задание, его прибыль равна $0. Верните максимальную прибыль, которую можно получить после распределения рабочих по заданиям. Пример:

Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.

👨‍💻 Алгоритм: 1⃣Создание и сортировка профиля работы Инициализируйте массив пар jobProfile с {0, 0}. Для каждого задания добавьте {difficulty[i], profit[i]} в jobProfile. Отсортируйте jobProfile по возрастанию сложности. 2⃣Обновление максимальной прибыли для каждой сложности Обновите значение прибыли каждой сложности, чтобы оно было максимальным из текущего значения и предыдущего значения прибыли. 3⃣Вычисление максимальной прибыли Для каждой способности рабочего используйте бинарный поиск, чтобы найти задание с наибольшей прибылью, которую может выполнить этот рабочий. Суммируйте полученную прибыль для всех рабочих и верните ее. 😎 Решение:

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        vector<pair<int, int>> jobProfile = {{0, 0}};
        for (int i = 0; i < difficulty.size(); ++i) {
            jobProfile.push_back({difficulty[i], profit[i]});
        }
        sort(jobProfile.begin(), jobProfile.end());
        
        for (int i = 1; i < jobProfile.size(); ++i) {
            jobProfile[i].second = max(jobProfile[i].second, jobProfile[i - 1].second);
        }
        
        int netProfit = 0;
        for (int ability : worker) {
            int l = 0, r = jobProfile.size() - 1, jobProfit = 0;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (jobProfile[mid].first <= ability) {
                    jobProfit = max(jobProfit, jobProfile[mid].second);
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            netProfit += jobProfit;
        }
        return netProfit;
    }
};

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