C/C++ | LeetCode

Современная магистратура от Центрального университета Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой? Поступай в магистратуру Центрального университета! - 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);
    }
};

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

Высшее образование дистанционно в Московском ВУЗе Вы мечтаете получить высшее образование, но не сдали ЕГЭ или получили низкие баллы? У нас есть решение для вас! Институт Международных Экономических Связей предлагает дистанционное обучение , которое позволяет получать качественные знания из любой точки мира по 10+ направлениям обучения. ✅ Государственный диплом без отметки о дистанте ✅ Удобный личный кабинет студента ✅ Поддержка кураторов на каждом этапе обучения ✅ Можно поступить без ЕГЭ Узнать больше #реклама 16+ imes.su О рекламодателе

Задача: 346. Moving Average from Data Stream Сложность: easy Дан поток целых чисел и размер окна, вычислите скользящее среднее всех целых чисел в скользящем окне. Реализуйте класс MovingAverage: MovingAverage(int size) Инициализирует объект с размером окна size. double next(int val) Возвращает скользящее среднее последних size значений потока. Пример:

Input
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
Output
[null, 1.0, 5.5, 4.66667, 6.0]

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

#include <queue>

class MovingAverage {
public:
    MovingAverage(int size) : size(size), sum(0) {}
    
    double next(int val) {
        q.push(val);
        sum += val;
        if (q.size() > size) {
            sum -= q.front();
            q.pop();
        }
        return (double) sum / q.size();
    }
    
private:
    int size;
    std::queue<int> q;
    int sum;
};

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

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

Задача: 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree Сложность: easy Даны два бинарных дерева: original и cloned, а также ссылка на узел target в оригинальном дереве. Дерево cloned является копией оригинального дерева. Верните ссылку на тот же узел в дереве cloned. Обратите внимание, что вам не разрешается изменять какое-либо из двух деревьев или узел target, и ответ должен быть ссылкой на узел в дереве cloned. Пример:

Input: tree = [7,4,3,null,null,6,19], target = 3
Output: 3
Explanation: In all examples the original and cloned trees are shown. The target node is a green node from the original tree. The answer is the yellow node from the cloned tree.

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

class Solution {
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        queue<TreeNode*> queue_o;
        queue<TreeNode*> queue_c;
        
        queue_o.push(original);
        queue_c.push(cloned);
        
        while (!queue_o.empty()) {
            TreeNode* node_o = queue_o.front();
            queue_o.pop();
            TreeNode* node_c = queue_c.front();
            queue_c.pop();
            
            if (node_o == target) {
                return node_c;
            }
            
            if (node_o->left != nullptr) {
                queue_o.push(node_o->left);
                queue_c.push(node_c->left);
            }
            if (node_o->right != nullptr) {
                queue_o.push(node_o->right);
                queue_c.push(node_c->right);
            }
        }
        return nullptr;
    }
};

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

Задача: 847. Shortest Path Visiting All Nodes Сложность: hard У вас есть неориентированный связный граф из n узлов, пронумерованных от 0 до n - 1. Вам дан массив graph, где graph[i] — это список всех узлов, соединенных с узлом i ребром. Верните длину кратчайшего пути, который посещает каждый узел. Вы можете начать и закончить в любом узле, вы можете несколько раз посещать узлы и использовать ребра повторно. Пример:

Input: graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

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

#include <vector>
#include <queue>
#include <utility>

using namespace std;

class Solution {
public:
    int shortestPathLength(vector<vector<int>>& graph) {
        int n = graph.size();
        if (n == 1) return 0;

        int endingMask = (1 << n) - 1;
        vector<vector<bool>> seen(n, vector<bool>(endingMask, false));
        queue<pair<int, int>> q;

        for (int i = 0; i < n; ++i) {
            q.push({i, 1 << i});
            seen[i][1 << i] = true;
        }

        int steps = 0;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                auto [node, mask] = q.front();
                q.pop();
                for (int neighbor : graph[node]) {
                    int nextMask = mask | (1 << neighbor);
                    if (nextMask == endingMask) return 1 + steps;
                    if (!seen[neighbor][nextMask]) {
                        seen[neighbor][nextMask] = true;
                        q.push({neighbor, nextMask});
                    }
                }
            }
            ++steps;
        }

        return -1;
    }
};

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

Sea Breeze: Ваш дом у моря в Баку. Всего в 3 ч от Москвы Продажа апартаментов в Sea Breeze. Роскошная жизнь в городе-курорте на побережье Каспия. 🏠 Яркие архитектурные решения, включая апарт-отель в форме лайнера. Развитая инфраструктура: 60 бассейнов, более 50 ресторанов, школы и детсады с английским языком. ✨ Круглогодичный комфорт: медицинский центр, аквапарк и луна-парк, концертные площадки, консьерж-сервис. 🏃‍♂️ Присоединяйтесь к 25 000 жителям и наслаждайтесь роскошью жизни в Sea Breeze ❤️ Узнать больше Проектная декларация на сайте https://наш.дом.рф/ #реклама invest.seabreeze.az О рекламодателе

Задача: 661. Image Smoother Сложность: easy Дан целочисленный матрица img размером m x n, представляющая градации серого изображения. Верните изображение после применения сглаживания к каждой его ячейке. Пример:

Input: img = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[0,0,0],[0,0,0],[0,0,0]]
Explanation:
For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0
For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0
For the point (1,1): floor(8/9) = floor(0.88888889) = 0

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

class Solution {
public:
    vector<vector<int>> imageSmoother(vector<vector<int>>& img) {
        int m = img.size(), n = img[0].size();
        vector<vector<int>> result(m, vector<int>(n, 0));
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int count = 0, total = 0;
                for (int ni = max(0, i - 1); ni <= min(m - 1, i + 1); ni++) {
                    for (int nj = max(0, j - 1); nj <= min(n - 1, j + 1); nj++) {
                        total += img[ni][nj];
                        count++;
                    }
                }
                result[i][j] = total / count;
            }
        }
        
        return result;
    }
};

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