C/C++ | LeetCode

В Битрикс24 теперь можно сделать сайт за 30 секунд Серьёзно. Пишешь, что нужно, и AI сам всё собирает: тексты, картинки, оформление. ✨Никакой магии, просто умный помощник. Попробуйте — закайфуете от скорости! Попробовать #реклама 16+ sites-24.bitrix24.ru О рекламодателе

Задача: 328. Odd Even Linked List Сложность: medium Дан заголовок односвязного списка. Сгруппируйте все узлы с нечетными индексами вместе, а затем узлы с четными индексами, и верните упорядоченный список. Первый узел считается нечетным, второй узел — четным и так далее. Учтите, что относительный порядок внутри обеих групп (четной и нечетной) должен оставаться таким же, как в исходном списке. Вы должны решить задачу с дополнительной сложностью по памяти O(1) и временной сложностью O(n). Пример:

Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

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

class ListNode {
public:
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head) return nullptr;
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* evenHead = even;
        
        while (even && even->next) {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
    }
};

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

Задача: 377. Combination Sum IV Сложность: medium Дан массив различных целых чисел nums и целое число target. Верните количество возможных комбинаций, которые в сумме дают target. Тестовые случаи сгенерированы так, что ответ помещается в 32-битное целое число. Пример:

Input: nums = [9], target = 3
Output: 0

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

#include <vector>
#include <unordered_map>

class Solution {
private:
    std::unordered_map<int, int> memo;

public:
    int combinationSum4(std::vector<int>& nums, int target) {
        return combs(nums, target);
    }

private:
    int combs(std::vector<int>& nums, int remain) {
        if (remain == 0)
            return 1;
        if (memo.find(remain) != memo.end())
            return memo[remain];

        int result = 0;
        for (int num : nums) {
            if (remain - num >= 0)
                result += combs(nums, remain - num);
        }
        memo[remain] = result;
        return result;
    }
};

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

Специальность «Технологическое предпринимательство» 🎓Открыт набор в Университет IThub 2025-2026! Программа бакалавриата «Инноватика» Эта интенсивная программа создана для будущих основателей стартапов, инноваторов и технологических лидеров, которые хотят быстро войти в мир бизнеса и цифровых технологий. Она подойдёт амбициозным выпускникам колледжей, которые хотят запустить свой бизнес сразу после учёбы. 📚Практические навыки + стажировки и 💰трудоустройство! ✅День открытых дверей 22 июня! Перейти на сайт #реклама univer.ithub.ru О рекламодателе

Задача: 1135. Connecting Cities With Minimum Cost Сложность: medium Есть n городов, пронумерованных от 1 до n. Вам даны целое число n и массив connections, где connections[i] = [xi, yi, costi] указывает, что стоимость соединения города xi и города yi (двунаправленное соединение) равна costi. Верните минимальную стоимость для соединения всех n городов так, чтобы между каждой парой городов был хотя бы один путь. Если невозможно соединить все n городов, верните -1. Стоимость - это сумма использованных стоимостей соединений. Пример:

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.

👨‍💻 Алгоритм: 1⃣Сортировка рёбер: Отсортируйте все соединения (рёбра) в графе по их весам (стоимости) в порядке возрастания. 2⃣Итерация по рёбрам и объединение: Используйте структуру данных Disjoint Set (Union-Find) для проверки циклов и объединения поддеревьев. Для каждого ребра проверьте, принадлежат ли его концы разным поддеревьям, и если да, объедините их, добавив ребро в минимальное остовное дерево (MST). 3⃣Проверка соединённости: Подсчитайте количество рёбер в MST. Если оно меньше n-1, верните -1, так как соединить все города невозможно. Иначе верните суммарную стоимость рёбер в MST. 😎 Решение:

class DisjointSet {
    vector<int> parent;
public:
    DisjointSet(int n) : parent(n + 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void unionSet(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootY] = rootX;
        }
    }
};

class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& connections) {
        sort(connections.begin(), connections.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[2] < b[2];
        });

        DisjointSet disjointSet(n);
        int totalCost = 0;
        int edgesUsed = 0;

        for (const auto& connection : connections) {
            int x = connection[0];
            int y = connection[1];
            int cost = connection[2];

            if (disjointSet.find(x) != disjointSet.find(y)) {
                disjointSet.unionSet(x, y);
                totalCost += cost;
                edgesUsed++;
                if (edgesUsed == n - 1) {
                    return totalCost;
                }
            }
        }
        return edgesUsed == n - 1 ? totalCost : -1;
    }
};

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

Легендарная AIшница 3.0! Бесплатный онлайн-практикум 3 сезон масштабного онлайн-практикума про нейросети для бизнеса. 3 дня, в программе применение ИИ в продажах, маркетинге, HR и других бизнес-процессов Спикеры: Александр Горный, Сергей Нотевский, Павел Лебедев Регистрируйтесь бесплатно! Узнать больше #реклама 16+ ai-practicum.bitrix24.events О рекламодателе

📺 Уникальная база IT собеседований 456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 209. Minimum Size Subarray Sum Сложность: medium Дан массив положительных целых чисел nums и целое число target. Нужно найти минимальную длину подмассива, сумма которого больше или равна target. Если такого подмассива не существует — вернуть 0. Пример:

Input: target = 7, nums = [2,3,1,2,4,3] Output: 2
Пояснение: минимальный подмассив — [4,3]

👨‍💻 Алгоритм: 1⃣Инициализация указателей и суммы окна: Установим left = 0, sum = 0, res = INT_MAX. Указатели left и right формируют окно подмассива. 2⃣Проход по массиву (движение правого указателя): На каждом шаге прибавляем nums[right] к текущей сумме. Если sum >= target, пробуем сузить окно слева (двигаем left) и обновляем res. 3⃣Возврат ответа: Если res не изменился — возвращаем 0, иначе — res. 😎 Решение:

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0, sumOfCurrentWindow = 0;
        int res = INT_MAX;

        for(right = 0; right < nums.size(); right++) {
            sumOfCurrentWindow += nums[right];

            while (sumOfCurrentWindow >= target) {
                res = min(res, right - left + 1);
                sumOfCurrentWindow -= nums[left];
                left++;
            }
        }

        return res == INT_MAX ? 0 : res;
    }
};

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

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

Задача: 297. Serialize and Deserialize Binary Tree Сложность: hard Пример:

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

👨‍💻 Алгоритм: 1⃣Сериализация дерева Обход в порядке префикс (root → left → right). Если узел пустой, записываем "null,", иначе — значение узла и рекурсивно сериализуем левое и правое поддерево. 2⃣Десериализация строки Разбиваем строку по запятой и преобразуем в массив. Рекурсивно создаём дерево, доставая элементы из начала массива. Если встречается "null" — возвращаем nullptr. 3⃣Обратимость Алгоритм гарантирует, что deserialize(serialize(root)) восстановит дерево без потерь. 😎 Решение:

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

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

class Codec {
public:
    void rserialize(TreeNode* root, std::string& str) {
        if (root == nullptr) {
            str += "null,";
        } else {
            str += std::to_string(root->val) + ",";
            rserialize(root->left, str);
            rserialize(root->right, str);
        }
    }

    std::string serialize(TreeNode* root) {
        std::string str;
        rserialize(root, str);
        return str;
    }

    TreeNode* rdeserialize(std::vector<std::string>& data) {
        if (data[0] == "null") {
            data.erase(data.begin());
            return nullptr;
        }

        TreeNode* root = new TreeNode(std::stoi(data[0]));
        data.erase(data.begin());
        root->left = rdeserialize(data);
        root->right = rdeserialize(data);
        return root;
    }

    TreeNode* deserialize(std::string data) {
        std::vector<std::string> dataArray;
        std::string item;
        std::istringstream ss(data);
        while (std::getline(ss, item, ',')) {
            dataArray.push_back(item);
        }
        return rdeserialize(dataArray);
    }
};

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

Яндекс Музыка ваша за ответ на 1 вопрос Яндекс Музыка, Книги и Кинопоиск в одной подписке для вас и 3-х ваших близких. Попробуйте бесплатно👍 Попробовать #реклама 18+ mrqz.me О рекламодателе Реклама на Яндексе

Задача: 1402. Reducing Dishes Сложность: hard Шеф-повар собрал данные об уровне удовлетворенности от своих n блюд. Шеф может приготовить любое блюдо за 1 единицу времени. Коэффициент удовольствия от блюда определяется как время, затраченное на приготовление этого блюда вместе с предыдущими блюдами, умноженное на уровень удовлетворенности от этого блюда, то есть time[i] * satisfaction[i]. Верните максимальную сумму коэффициентов удовольствия, которую шеф-повар может получить после приготовления некоторого количества блюд. Блюда можно готовить в любом порядке, и шеф может отказаться от некоторых блюд, чтобы достичь максимального значения. Пример:

Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.

👨‍💻 Алгоритм: 1⃣Отсортируйте массив satisfaction в порядке возрастания. 2⃣Создайте таблицу мемоизации memo размером N x N и инициализируйте все значения -1, что будет означать, что ответ для всех состояний еще не рассчитан. 3⃣Реализуйте функцию, которая вызывается с параметрами index = 0 и time = 1, чтобы найти ответ: Если достигнут конец массива, т.е. index == satisfaction.length, верните 0, так как больше нет блюд для приготовления и нельзя получить дополнительное значение. Если значение в массиве memo для пары {index, time} не равно -1, верните это значение, так как это подразумевает, что данная подзадача уже была решена; поэтому рекурсивный вызов не требуется, и можно вернуть сохраненное значение из таблицы memo. Рассчитайте максимум из двух вариантов: добавьте значение коэффициента для данного блюда satisfaction[index] * time к рекурсивному результату с index = index + 1 и time = time + 1. Пропустите текущее блюдо и сделайте рекурсивный вызов для index = index + 1 и time = time. 😎 Решение:

class Solution {
public:
    int findMaxSatisfaction(vector<int>& satisfaction, vector<vector<int>>& memo, int index, int time) {
        if (index == satisfaction.size()) return 0;
        if (memo[index][time] != -1) return memo[index][time];

        return memo[index][time] = max(satisfaction[index] * time + findMaxSatisfaction(satisfaction, memo, index + 1, time + 1),
                                       findMaxSatisfaction(satisfaction, memo, index + 1, time));
    }

    int maxSatisfaction(vector<int>& satisfaction) {
        sort(satisfaction.begin(), satisfaction.end());
        vector<vector<int>> memo(satisfaction.size() + 1, vector<int>(satisfaction.size() + 1, -1));
        return findMaxSatisfaction(satisfaction, memo, 0, 1);
    }
};

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

Начните работу легко, даже если у вас лапки Работаете в программах 1С? Попробуйте современное решение! 1С:Фреш — это облачный сервис, который открывает доступ ко всем популярным программам 1С: Бухгалтерии, Рознице, Зарплата и управление персоналом и другим. Чем 1С:Фреш отличается от локальных версий программ: — Автообновление 1С всегда до последней версии, не нужно ждать специалистов; — Синхронизация данных между программами 1С; — Безопасность данных, вся информация передается в зашифрованном виде и доступна только вам. ⚡Зарегистрируйтесь, и получите 30 дней тестового доступа к полному функционалу! Зарегистрироваться #реклама 16+ pcs.ru О рекламодателе

Задача: 295. Find Median from Data Stream Сложность: hard Пример:

Input: ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
Output: [null, null, null, 1.5, null, 2.0]

👨‍💻 Алгоритм: 1⃣Используйте две кучи: max-heap (left) для хранения меньшей половины элементов и min-heap (right) для хранения большей половины. Это позволяет находить медиану за O(1) и вставлять за O(log n). 2⃣При добавлении числа: Если left пуст или num <= top(left), добавьте его в left. Иначе добавьте его в right. После добавления сбалансируйте размеры куч: если одна куча больше другой более чем на 1 элемент, переместите элемент из большей в меньшую. 3⃣Для вычисления медианы: Если размеры куч равны, верните среднее двух верхних элементов. Если одна куча больше, верните её верхний элемент как медиану. 😎 Решение:

#include <queue>

class MedianFinder {
private:
    priority_queue<int> left; // max-heap
    priority_queue<int, vector<int>, greater<int>> right; // min-heap

public:
    MedianFinder() {}

    void addNum(int num) {
        if (left.empty() || num <= left.top()) {
            left.push(num);
        } else {
            right.push(num);
        }

        if (left.size() > right.size() + 1) {
            right.push(left.top());
            left.pop();
        } else if (right.size() > left.size()) {
            left.push(right.top());
            right.pop();
        }
    }

    double findMedian() {
        if (left.size() == right.size()) {
            return (left.top() + right.top()) / 2.0;
        } else {
            return left.top();
        }
    }
};

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

Хватит тратить время на поиск IT вакансии впустую! Узнай топ-5 фишек для поиска оффера в зарубежной компании от лучших серчеров. Читай пост в телеграм канале и получи желаемый оффер быстрее! Перейти на сайт #реклама agilefluent.ru О рекламодателе

Задача: 981. Time Based Key-Value Store Сложность: medium Спроектируйте структуру данных на основе времени для ключей и значений, которая может хранить несколько значений для одного и того же ключа в разные временные метки и извлекать значение ключа в определённый момент времени. Реализуйте класс TimeMap: TimeMap() Инициализирует объект структуры данных. void set(String key, String value, int timestamp) Сохраняет ключ key с значением value в заданное время timestamp. String get(String key, int timestamp) Возвращает значение, такое что set был вызван ранее с timestamp_prev <= timestamp. Если таких значений несколько, возвращается значение, связанное с наибольшим timestamp_prev. Если значений нет, возвращается "". Пример:

Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]

👨‍💻 Алгоритм: 1⃣Создайте hashmap keyTimeMap, который хранит строку в качестве ключа и другой hashmap в качестве значения, как обсуждалось выше. 2⃣В функции set() сохраните значение в позиции timestamp в корзине ключа keyTimeMap, т.е. keyTimeMap[key][timestamp] = value. 3⃣В функции get() итерируйтесь по всем временам в порядке убывания от timestamp до 1. Для любого времени во время итерации, если существует значение в корзине ключа, верните это значение. В противном случае, в конце верните пустую строку. 😎 Решение:

#include <unordered_map>
#include <string>

class TimeMap {
public:
    std::unordered_map<std::string, std::unordered_map<int, std::string>> keyTimeMap;

    TimeMap() {}

    void set(const std::string& key, const std::string& value, int timestamp) {
        keyTimeMap[key][timestamp] = value;
    }

    std::string get(const std::string& key, int timestamp) {
        if (!keyTimeMap.count(key)) {
            return "";
        }

        for (int currTime = timestamp; currTime >= 1; --currTime) {
            if (keyTimeMap[key].count(currTime)) {
                return keyTimeMap[key][currTime];
            }
        }

        return "";
    }
};

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

Получи грант на обучение в Центральном университете Несгораемый грант до 2 800 000 Р на учебу в бакалавриате Центрального университета. Подробнее о гранте: – Покрывает до 100% стоимости обучения – Выдается на все 4 года обучения в вузе – Сумма гранта не уменьшается, а может увеличиться за дополнительные достижения и успехи в учебе. Для учеников 10-х и 11-х классов. Участвуй в отборе! Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 898. Bitwise ORs of Subarrays Сложность: medium Если задан целочисленный массив arr, верните количество различных побитовых ИЛИ всех непустых подмассивов arr. Побитовое ИЛИ подмассива - это побитовое ИЛИ каждого целого числа в подмассиве. Побитовым ИЛИ подмассива одного целого числа является это целое число. Подмассив - это непрерывная непустая последовательность элементов в массиве. Пример:

Input: arr = [0]
Output: 1

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

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& arr) {
        unordered_set<int> result, current, next;
        for (int num : arr) {
            next = {num};
            for (int x : current) {
                next.insert(x | num);
            }
            current = next;
            result.insert(current.begin(), current.end());
        }
        return result.size();
    }
};

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

Виртуальный сервер в аренду в Турции или России. Отказоустойчивый виртуальный облачный сервер на базе виртуализации VMWARE по модели подписки. - Бесплатная миграция инфраструктуры в Турцию - Размещайте ресурсы в Турции или России и оплачивайте в рублях, турицких лирах или евро. - Храните резервные копии данных за рубежом для минимизации рисков - Продолжайте использовать импортное ПО, скачивайте обновления и патчи, общайтесь с техподдержкой - Доступность сервиса — от 99,982% SLA - Дата центры Tier III в России и Турции - Почасовой биллинг и постоплата Подключите услугу сегодня со скидкой 50% на инфраструктуру. Подать заявку #реклама cloud4y.ru О рекламодателе

Задача: 461. Hamming Distance Сложность: easy Расстояние Хэмминга между двумя целыми числами — это количество позиций, в которых соответствующие биты различны. Даны два целых числа x и y, верните расстояние Хэмминга между ними. Пример:

Input: x = 3, y = 1
Output: 1

👨‍💻 Алгоритм: 1⃣Во-первых, стоит упомянуть, что в большинстве (или, по крайней мере, во многих) языков программирования есть встроенные функции для подсчета битов, установленных в 1. Если вам нужно решить такую задачу в реальном проекте, то лучше использовать эти функции, чем изобретать велосипед. 2⃣Однако, поскольку это задача на LeetCode, использование встроенных функций можно сравнить с "реализацией LinkedList с использованием LinkedList". Поэтому рассмотрим также несколько интересных ручных алгоритмов для подсчета битов. 3⃣Пошаговый подсчет битов: Выполните побитовое XOR между x и y. Инициализируйте счетчик bitCount = 0. Пока число не равно нулю: Если текущий бит равен 1, увеличьте bitCount. Сдвиньте число вправо на один бит. Возвращайте bitCount. 😎 Решение:

class Solution {
public:
    int hammingDistance(int x, int y) {
        return __builtin_popcount(x ^ y);
    }
};

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