C/C++ | LeetCode

Начните работу легко, даже если у вас лапки Работаете в программах 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;
    }
};

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

Задача: 60. Permutation Sequence Сложность: hard Дано n, представляющее числа от 1 до n, и k — порядковый номер. Нужно вернуть k-ю лексикографическую перестановку этих чисел. Пример:

Input: n = 3, k = 3 Output: "213"

👨‍💻 Алгоритм: 1⃣Сформировать массив nums из символов '1' до 'n' и массив факториалов от 0! до (n-1)! 2⃣Уменьшить k на 1 (чтобы перейти к 0-индексации) 3⃣На каждой позиции определить индекс следующего числа: idx = k / factorial[i], далее обновить k -= idx * factorial[i] Удалить выбранный элемент из nums и добавить к результату 😎 Решение:

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> factorials(n);
        vector<char> nums;
        factorials[0] = 1;
        nums.push_back('1');
        for (int i = 1; i < n; ++i) {
            factorials[i] = factorials[i - 1] * i;
            nums.push_back(char(i + 1 + '0'));
        }

        --k;
        string result = "";
        for (int i = n - 1; i > -1; --i) {
            int idx = k / factorials[i];
            k -= idx * factorials[i];
            result += nums[idx];
            nums.erase(nums.begin() + idx);
        }
        return result;
    }
};

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

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

Задача: 1538. Guess the Majority in a Hidden Array Сложность: medium У нас есть целочисленный массив nums, где все числа в nums равны 0 или 1. Вам не будет предоставлен прямой доступ к массиву, вместо этого у вас будет API ArrayReader, который имеет следующие функции: int query(int a, int b, int c, int d): где 0 <= a < b < c < d < ArrayReader.length(). Функция возвращает распределение значений 4 элементов и возвращает: 4: если значения всех 4 элементов одинаковы (0 или 1). 2: если три элемента имеют значение 0 и один элемент имеет значение 1 или наоборот. 0: если два элемента имеют значение 0 и два элемента имеют значение 1. int length(): Возвращает размер массива. Вам разрешено вызывать query() не более 2 * n раз, где n равно ArrayReader.length(). Верните любой индекс самого частого значения в nums, в случае ничьей верните -1. Пример:

Input: nums = [0,0,1,0,1,1,1,1]
Output: 5
Explanation: The following calls to the API
reader.length() // returns 8 because there are 8 elements in the hidden array.
reader.query(0,1,2,3) // returns 2 this is a query that compares the elements nums[0], nums[1], nums[2], nums[3]
// Three elements have a value equal to 0 and one element has value equal to 1 or viceversa.
reader.query(4,5,6,7) // returns 4 because nums[4], nums[5], nums[6], nums[7] have the same value.
we can infer that the most frequent value is found in the last 4 elements.
Index 2, 4, 6, 7 is also a correct answer.

👨‍💻 Алгоритм: 1⃣Получите n вызовом функции length. Объявите и инициализируйте переменные cntEqual = 1, cntDiffer = 0, indexDiffer = -1. Вызовите query(0, 1, 2, 3) и сохраните результат в переменной query0123. Вызовите query(1, 2, 3, 4) и сохраните результат в переменной query1234. Если query1234 равно query0123, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = 4. 2⃣Итерация от i = 5 до n-1. Если значение query(1, 2, 3, i) равно query0123, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = i. Дополнительные проверки для первых элементов: если query(0, 2, 3, 4) равно query1234, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = 1. Если query(0, 1, 3, 4) равно query1234, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = 2. Если query(0, 1, 2, 4) равно query1234, увеличьте cntEqual, иначе увеличьте cntDiffer и обновите indexDiffer = 3. 3⃣Если cntEqual > cntDiffer, верните 0. Если cntDiffer > cntEqual, верните indexDiffer. Верните -1. 😎 Решение:

class Solution {
    int cntEqual = 1, cntDiffer = 0, indexDiffer = -1;

    void f(bool equal, int i) {
        if (equal) {
            cntEqual++;
        } else {
            cntDiffer++;
            indexDiffer = i;
        }
    }

public:
    int guessMajority(ArrayReader& reader) {
        int n = reader.length(), query0123 = reader.query(0, 1, 2, 3), query1234 = reader.query(1, 2, 3, 4);
        f(query1234 == query0123, 4);
        for (int i = 5; i < n; i++) {
            f(reader.query(1, 2, 3, i) == query0123, i);
        }
        f(reader.query(0, 2, 3, 4) == query1234, 1);
        f(reader.query(0, 1, 3, 4) == query1234, 2);
        f(reader.query(0, 1, 2, 4) == query1234, 3);
        return cntEqual > cntDiffer ? 0 : cntDiffer > cntEqual ? indexDiffer : -1;
    }
};

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

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