es
Feedback

¡No caigas en manos de tramposos! Telemetrio encuentra y marca estos canales 👉 Si quieres ver la etiqueta, suscríbete

C/C++ | LeetCode

C/C++ | LeetCode

Ir al canal en Telegram

Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads

Mostrar más
3 208
Suscriptores
-124 horas
-77 días
-2230 días
Archivo de publicaciones
Дарим подписку Mail Space на 1 ТБ на 3 летних месяца. У вас будет 1 ТБ для любых файлов, а еще безлимит — это когда фото и видео с телефона не занимают место в Облаке. Можете фоткать всё, что угодно и не переживать, что место закончится. Не закончится. Совсем. Даже на 1 000 001 фото летней вечеринки. Забрать подарок Узнать больше #реклама 16+ cloud.mail.ru О рекламодателе

Задача: 478. Generate Random Point in a Circle Сложность: medium Дан радиус и положение центра окружности, реализуйте функцию
Задача: 478. Generate Random Point in a Circle Сложность: medium Дан радиус и положение центра окружности, реализуйте функцию randPoint, которая генерирует равномерно случайную точку внутри окружности. Реализуйте класс Solution: - Solution(double radius, double x_center, double y_center) инициализирует объект с радиусом окружности radius и положением центра (x_center, y_center). - randPoint() возвращает случайную точку внутри окружности. Точка на окружности считается находящейся внутри окружности. Ответ возвращается в виде массива [x, y]. Пример:
Input
["Solution", "randPoint", "randPoint", "randPoint"]
[[1.0, 0.0, 0.0], [], [], []]
Output
[null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]

Explanation
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint(); // return [-0.02493, -0.38077]
solution.randPoint(); // return [0.82314, 0.38945]
solution.randPoint(); // return [0.36572, 0.17248]
👨‍💻 Алгоритм: 1⃣ Генерируем равномерно случайные точки в квадрате S с длиной стороны 2R. 2⃣ Сохраняем все точки, которые находятся на расстоянии не более R от центра, и отклоняем все, которые дальше этого расстояния. 3⃣ Повторяем процесс до получения нужного количества точек, учитывая, что примерно 78.5% от всех сгенерированных точек будут приемлемыми, и ожидаемое число попыток до получения приемлемой точки составляет примерно 1.274 раза. 😎 Решение:
#include <cmath>
#include <cstdlib>
#include <vector>

class Solution {
    double rad, xc, yc;

public:
    Solution(double radius, double x_center, double y_center) : rad(radius), xc(x_center), yc(y_center) {}

    std::vector<double> randPoint() {
        double x0 = xc - rad;
        double y0 = yc - rad;

        while (true) {
            double xg = x0 + static_cast<double>(rand()) / RAND_MAX * rad * 2;
            double yg = y0 + static_cast<double>(rand()) / RAND_MAX * rad * 2;
            if (sqrt(pow(xg - xc, 2) + pow(yg - yc, 2)) <= rad) {
                return {xg, yg};
            }
        }
    }
};
Ставь 👍 и забирай 📚 Базу знаний

Большая распродажа: скидки на серверы Dell, HPE В Сервер Молл выгодное предложение на серверы Dell, HPE предыдущих поколений
Большая распродажа: скидки на серверы Dell, HPE В Сервер Молл выгодное предложение на серверы Dell, HPE предыдущих поколений — самое время для апгрейда и масштабирования. Есть модели под любые задачи: 1С, базы данных, виртуализация, видеонаблюдение, файловое хранилище, VPN и другие офисные нагрузки. Конфигурации — от бюджетных до некогда топов с двумя процессорами Intel Xeon Gold. Все серверы в наличии и готовы к отправке: с гарантией до 5 лет, бесплатной доставкой по всей России и послепродажной поддержкой. Можно выбрать готовый вариант или доукомплектовать под свои задачи — консультации в любом объёме. Если вы ждали повод собрать инфраструктуру с нуля, масштабировать или заменить старую технику — он перед вами. Акция продлится, пока серверы есть в наличии. ✅ Пишите в чат или звоните — 8 800 755-25-51 📞 Узнать цену #реклама 16+ servermall.ru О рекламодателе

Задача: 686. Repeated String Match Сложность: medium Даны две строки a и b. Верните минимальное количество повторений строки a, чтобы строка b стала её подстрокой. Если сделать b подстрокой a невозможно, верните -1. Обратите внимание: строка "abc", повторенная 0 раз, это "", повторенная 1 раз - "abc", повторенная 2 раза - "abcabc". Пример:
Input: a = "abcd", b = "cdabcdab"
Output: 3
Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.
👨‍💻 Алгоритм: 1⃣Найти минимальное количество повторений строки A, чтобы её длина стала больше или равна длине B. Это значение q = ceil(len(B) / len(A)). 2⃣Проверить, является ли B подстрокой строки A, повторенной q раз. Если да, вернуть q. Иначе, проверить строку A, повторенную (q+1) раз. Если B является подстрокой этой строки, вернуть q+1. 3⃣Если B не является подстрокой ни в одном из случаев, вернуть -1. 😎 Решение:
class Solution {
public:
    int repeatedStringMatch(string A, string B) {
        int q = 1;
        string S = A;
        while (S.length() < B.length()) {
            S += A;
            q++;
        }
        if (S.find(B) != string::npos) return q;
        if ((S + A).find(B) != string::npos) return q + 1;
        return -1;
    }
};
Ставь 👍 и забирай 📚 Базу знаний

Онлайн-магистратура в IT совместно с ИТМО, МИФИ и МФТИ День открытых дверей 26 июня в 19.00 по Москве | Онлайн Все программы 2025, общение со студентами и экспертами из вузов и Яндекса. Ответы на вопросы. Зарегистрироваться #реклама 16+ praktikum.yandex.ru О рекламодателе

Задача: 1168. Optimize Water Distribution in a Village Сложность: hard В деревне есть n домов. Мы хотим обеспечить все дома водой, строя колодцы и прокладывая трубы. Для каждого дома i мы можем либо построить колодец внутри него непосредственно с затратами wells[i - 1] (обратите внимание на -1 из-за нумерации с нуля), либо провести воду из другого колодца с помощью трубы. Затраты на прокладку труб между домами даны в массиве pipes, где каждый pipes[j] = [house1j, house2j, costj] представляет собой стоимость соединения дома house1j и дома house2j с помощью трубы. Соединения двунаправленные, и между одними и теми же домами могут быть несколько допустимых соединений с разными затратами. Верните минимальные оhttps://leetcode.com/problems/optimize-water-distribution-in-a-village/Figures/1168/PrimAlgDemo.gifбщие затраты на обеспечение всех домов водой. Пример:
Input: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
Output: 3
Explanation: The image shows the costs of connecting houses using pipes.
The best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3.
👨‍💻 Алгоритм: 1⃣Представление графа: Постройте список смежности для представления графа, где вершины и ребра соответствуют домам и трубам. Список смежности можно представить в виде списка списков или словаря списков. 2⃣Набор для вершин: Используйте набор для поддержания всех вершин, добавленных в окончательное минимальное остовное дерево (MST) во время его построения. С помощью набора можно определить, была ли вершина уже добавлена или нет. 3⃣Очередь с приоритетом (куча): Используйте кучу для реализации жадной стратегии. На каждом шаге определяйте лучшее ребро для добавления на основе стоимости его добавления в дерево. Куча позволяет извлекать минимальный элемент за константное время и удалять минимальный элемент за логарифмическое время. Это идеально подходит для нашей задачи повторного нахождения ребра с наименьшей стоимостью. 😎 Решение:
class Solution {
public:
    int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> edgesHeap;
        vector<vector<pair<int, int>>> graph(n + 1);
        
        for (int i = 0; i < wells.size(); ++i) {
            graph[0].emplace_back(wells[i], i + 1);
            edgesHeap.emplace(wells[i], i + 1);
        }
        
        for (const auto& pipe : pipes) {
            int house1 = pipe[0], house2 = pipe[1], cost = pipe[2];
            graph[house1].emplace_back(cost, house2);
            graph[house2].emplace_back(cost, house1);
        }
        
        unordered_set<int> mstSet{0};
        int totalCost = 0;
        
        while (mstSet.size() < n + 1) {
            auto [cost, nextHouse] = edgesHeap.top(); edgesHeap.pop();
            if (mstSet.count(nextHouse)) continue;
            mstSet.insert(nextHouse);
            totalCost += cost;
            for (const auto& [nextCost, neighbor] : graph[nextHouse]) {
                if (!mstSet.count(neighbor)) {
                    edgesHeap.emplace(nextCost, neighbor);
                }
            }
        }
        
        return totalCost;
    }
};
Ставь 👍 и забирай 📚 Базу знаний

Онлайн-магистратура «Науки о данных» в FinTech Применяйте Data Science в своей сфере. Онлайн-магистратура "Науки о данных" МФ
Онлайн-магистратура «Науки о данных» в 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 для бэкендеров с опытом от трёх лет. Участнико
VK Weekend Offer для бэкенд-разработчиков 28–29 июня VK проведёт Weekend Offer для бэкендеров с опытом от трёх лет. Участников со знанием Java, Go, Python или C++ ждут технические собеседования, знакомство с продуктами и, если всё сложится, офер уже в конце выходных. Ребята много лет создают облачные решения, системы рекомендаций и поисковые движки — всё с миллионами пользователей в проде — и сейчас ищут новых коллег. Поэтому оставляйте заявку до 25 июня, чтобы попасть в команду за выходные! Подробности — на сайте. Подать заявку #реклама 16+ team.vk.company О рекламодателе

Задача: 490. The Maze Сложность: medium В лабиринте есть шар, который может перемещаться по пустым пространствам (представлен
Задача: 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 – Топовый электронный микроскоп для пайки ✅Профессиональный микроскоп для точных работ! ✅ Микроскоп с увеличение
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 теперь есть Онлайн-доски Вместе с мессенджером, видеозвонками и задачами — базовый набор для любого проекта. Бесп
В Битрикс24 теперь есть Онлайн-доски Вместе с мессенджером, видеозвонками и задачами — базовый набор для любого проекта. Бесплатно. Передайте команде Узнать больше #реклама 16+ bitrix24.ru О рекламодателе

Задача: 106. Construct Binary Tree from Inorder and Postorder Traversal Сложность: medium Даны два массива целых чисел: inord
Задача: 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 сам всё собирает: тексты, картинки, офор
В Битрикс24 теперь можно сделать сайт за 30 секунд Серьёзно. Пишешь, что нужно, и AI сам всё собирает: тексты, картинки, оформление. ✨Никакой магии, просто умный помощник. Попробуйте — закайфуете от скорости! Попробовать #реклама 16+ sites-24.bitrix24.ru О рекламодателе

Задача: 328. Odd Even Linked List Сложность: medium Дан заголовок односвязного списка. Сгруппируйте все узлы с нечетными инде
Задача: 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. Верните количес
Задача: 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 О рекламодателе