C/C++ | LeetCode

Онлайн-магистратура «Науки о данных» в FinTech Применяйте Data Science в своей сфере. Онлайн-магистратура "Науки о данных" МФТИ. ✅Машинное обучение, ML ✅Нейронные сети, AI ✅Big data, data analysis ✅Глубокое обучение, DL ✅Компьютерное зрение, CV Записаться онлайн #реклама 16+ mipt.online О рекламодателе

Задача: 645. Set Mismatch Сложность: easy У вас есть набор целых чисел s, который изначально содержит все числа от 1 до n. К сожалению, из-за какой-то ошибки одно из чисел в s продублировалось в другое число в наборе, что привело к повторению одного числа и потере другого. Вам дан целочисленный массив nums, представляющий состояние данных в этом наборе после ошибки. Найдите число, которое встречается дважды, и число, которое отсутствует, и верните их в виде массива. Пример:

Input: nums = [1,2,2,4]
Output: [2,3]

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

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = nums.size();
        unordered_set<int> numSet;
        int duplicate = -1;
        for (int num : nums) {
            if (!numSet.insert(num).second) {
                duplicate = num;
            }
        }
        int missing = (n * (n + 1)) / 2 - accumulate(numSet.begin(), numSet.end(), 0);
        return {duplicate, missing};
    }
};

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

VK Weekend Offer для бэкенд-разработчиков 28–29 июня VK проведёт Weekend Offer для бэкендеров с опытом от трёх лет. Участников со знанием Java, Go, Python или C++ ждут технические собеседования, знакомство с продуктами и, если всё сложится, офер уже в конце выходных. Ребята много лет создают облачные решения, системы рекомендаций и поисковые движки — всё с миллионами пользователей в проде — и сейчас ищут новых коллег. Поэтому оставляйте заявку до 25 июня, чтобы попасть в команду за выходные! Подробности — на сайте. Подать заявку #реклама 16+ team.vk.company О рекламодателе

Задача: 490. The Maze Сложность: medium В лабиринте есть шар, который может перемещаться по пустым пространствам (представленным как 0) и стенам (представленным как 1). Шар может катиться по пустым пространствам вверх, вниз, влево или вправо, но он не остановится до тех пор, пока не наткнется на стену. Когда шар останавливается, он может выбрать следующее направление. Дан лабиринт размером m x n, начальная позиция шара и место назначения, где start = [startrow, startcol] и destination = [destinationrow, destinationcol]. Верните true, если шар может остановиться в месте назначения, иначе верните false. Вы можете предположить, что границы лабиринта представляют собой стены. В приведённом ниже примере они не указаны. Пример:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.

👨‍💻 Алгоритм: 1⃣Инициализация и подготовка данных Определите количество строк и столбцов в лабиринте (m и n). Создайте 2D массив visit для отслеживания посещённых ячеек. Запустите DFS (глубокий поиск) с начальной позиции. 2⃣DFS обход Если текущая ячейка уже посещена, верните false. Если текущая ячейка совпадает с ячейкой назначения, верните true. Отметьте текущую ячейку как посещённую. Переберите все четыре направления движения (вверх, вправо, вниз, влево): продвигайтесь в выбранном направлении до тех пор, пока не столкнётесь со стеной или границей. После остановки вызовите DFS для новой позиции. 3⃣Результат Если любой вызов DFS возвращает true, завершите выполнение и верните true. Если ни один путь не приводит к цели, верните false. 😎 Решение:

class Solution {
public:
    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        int m = maze.size(), n = maze[0].size();
        vector<vector<bool>> visit(m, vector<bool>(n, false));
        return dfs(m, n, maze, start, destination, visit);
    }

private:
    vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    bool dfs(int m, int n, vector<vector<int>>& maze, vector<int>& curr, vector<int>& destination, vector<vector<bool>>& visit) {
        if (visit[curr[0]][curr[1]]) return false;
        if (curr == destination) return true;
        visit[curr[0]][curr[1]] = true;
        for (auto [dx, dy] : directions) {
            int r = curr[0], c = curr[1];
            while (r >= 0 && r < m && c >= 0 && c < n && maze[r][c] == 0) {
                r += dx;
                c += dy;
            }
            vector<int> newCurr = {r - dx, c - dy};
            if (dfs(m, n, maze, newCurr, destination, visit)) return true;
        }
        return false;
    }
};

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

Arstek Mimic – Топовый электронный микроскоп для пайки ✅Профессиональный микроскоп для точных работ! ✅ Микроскоп с увеличением до 345x, большим рабочим расстоянием до 280 мм и высокой скоростью передачи видео 60 FPS. Подходит для проверки плат, пайки микросхем, ремонта смартфонов. - Подключение к HDMI, USB, TF - 38 МП камера Panasonic - Регулируемое LED-освещение (70 диодов) - Совместим с любым монитором - Штатив i-Type, подходит для больших плат ⚡Идеальный выбор для ремонта, пайки и сборки электроники! ⚡ Перейти на сайт #реклама arstek.ru О рекламодателе

Задача: 758. Bold Words in String Сложность: medium При наличии массива ключевых слов и строки a выделите все ключевые слова [i] жирным шрифтом. Все буквы между тегами <b> и </b> выделяются жирным шрифтом. Возвращает после добавления тегов, выделенных жирным шрифтом. Возвращаемая строка должна содержать как можно меньшее количество тегов, и теги должны образовывать допустимую комбинацию. Пример:

Input: words = ["ab","bc"], s = "aabcd"
Output: "a<b>abc</b>d"

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

class Solution {
public:
    string addBoldTags(vector<string>& keywords, string s) {
        int n = s.size();
        vector<bool> bold(n, false);
        
        for (const string& word : keywords) {
            int start = s.find(word);
            while (start != string::npos) {
                for (int i = start; i < start + word.size(); i++) {
                    bold[i] = true;
                }
                start = s.find(word, start + 1);
            }
        }
        
        string result;
        int i = 0;
        while (i < n) {
            if (bold[i]) {
                result += "<b>";
                while (i < n && bold[i]) {
                    result += s[i];
                    i++;
                }
                result += "</b>";
            } else {
                result += s[i];
                i++;
            }
        }
        
        return result;
    }
};

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

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

Задача: 106. Construct Binary Tree from Inorder and Postorder Traversal Сложность: medium Даны два массива целых чисел: inorder и postorder, где inorder — это результат обхода в глубину слева направо, а postorder — результат обхода после обработки всех потомков узла. Постройте и верните бинарное дерево. Пример:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] Output: [3,9,20,null,null,15,7]

👨‍💻 Алгоритм: 1⃣Создайте хэш-таблицу (unordered_map), где ключ — значение из inorder, а значение — его индекс. Это нужно для быстрого поиска позиции корня. 2⃣Реализуйте рекурсивную функцию helper, принимающую левую и правую границы inorder. Если in_left > in_right, возвращаем nullptr. 3⃣Последний элемент в postorder — это текущий корень. Найдите его индекс в inorder. Рекурсивно постройте сначала правое поддерево, затем левое, и верните текущий корень. 😎 Решение:

class Solution {
    int post_idx;
    vector<int> postorder;
    vector<int> inorder;
    unordered_map<int, int> idx_map;

public:
    TreeNode* helper(int in_left, int in_right) {
        if (in_left > in_right) return NULL;
        
        int root_val = postorder[post_idx];
        TreeNode* root = new TreeNode(root_val);
        
        int index = idx_map[root_val];
        post_idx--;
        
        root->right = helper(index + 1, in_right);
        root->left = helper(in_left, index - 1);
        
        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        this->postorder = postorder;
        this->inorder = inorder;
        post_idx = postorder.size() - 1;

        int idx = 0;
        for (int val : inorder) {
            idx_map[val] = idx++;
        }

        return helper(0, inorder.size() - 1);
    }
};

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

В Битрикс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);
    }
};

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