C/C++ | LeetCode

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по 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;
    }
};

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

Теперь 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;
    }
};

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