en
Feedback
C/C++ | LeetCode

C/C++ | LeetCode

Open in Telegram
3 256
Subscribers
-224 hours
-17 days
-630 days
Posts Archive
Скидки на электрические зубные щетки Oral-B ORAL-B Genius-X с искусственным интеллектом – первая в мире зубная щетка, которая
Скидки на электрические зубные щетки Oral-B ORAL-B Genius-X с искусственным интеллектом – первая в мире зубная щетка, которая распознает стиль чистки зубов и дает рекомендации по улучшению. Купить #реклама market.yandex.ru О рекламодателе

Задача: 583. Delete Operation for Two Strings Сложность: medium Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми. На одном шаге можно удалить ровно один символ в любой строке. Пример:
Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
👨‍💻 Алгоритм: 1⃣ Инициализация массива: Создайте одномерный массив dp для хранения минимального количества удалений, необходимых для уравнивания строк word1 и word2. 2⃣ Заполнение массива: Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки. 3⃣ Обновление и результат: Скопируйте временный массив temp обратно в dp после обработки каждой строки. В конце верните значение из dp, представляющее минимальное количество удалений. 😎 Решение:
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<int> dp(n + 1, 0);

        for (int i = 0; i <= m; ++i) {
            vector<int> temp(n + 1, 0);
            for (int j = 0; j <= n; ++j) {
                if (i == 0 || j == 0) {
                    temp[j] = i + j;
                } else if (word1[i - 1] == word2[j - 1]) {
                    temp[j] = dp[j - 1];
                } else {
                    temp[j] = 1 + min(dp[j], temp[j - 1]);
                }
            }
            dp = temp;
        }

        return dp[n];
    }
};
Ставь 👍 и забирай 📚 Базу знаний

Датчики тока ELHART ATE.S Бесконтактные датчики тока для контроля работы оборудования. Российские датчики тока ELHART ATE.S -
+3
Датчики тока ELHART ATE.S Бесконтактные датчики тока для контроля работы оборудования. Российские датчики тока ELHART ATE.S - это современные приборы отечественного производства, качественнее, дешевле европейских аналогов с доставкой по России и Белоруссии от 1 дня! ⚡ Точность до 0,2% ⚡ Выход 4..20 мА ⚡ Защита от длительных перегрузок ⚡ Время отклика от 0,1 с ⚡ Частота измеряемого тока от 40 до 400 Гц Подробное описание на сайте. Оптимизируйте производство современными датчиками ELHART Перейти на сайт #реклама kipservis.ru О рекламодателе

Задача: 1482. Minimum Number of Days to Make m Bouquets Сложность: medium Вам дан массив целых чисел bloomDay, целое число m и целое число k. Вам нужно сделать m букетов. Для создания букета необходимо использовать k соседних цветов из сада. Сад состоит из n цветов, i-й цветок расцветет на bloomDay[i] и затем может быть использован ровно в одном букете. Верните минимальное количество дней, которое нужно подождать, чтобы можно было сделать m букетов из сада. Если сделать m букетов невозможно, верните -1. Пример:
Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.
👨‍💻 Алгоритм: 1⃣Инициализация: Инициализируйте start как 0 и end как максимальное значение в массиве bloomDay. Введите вспомогательную функцию getNumOfBouquets для подсчета количества букетов, которые можно сделать на определенный день. 2⃣Поиск минимального числа дней: Выполняйте бинарный поиск, пока start меньше или равен end: - рассчитайте mid как среднее значение между start и end. - используйте getNumOfBouquets, чтобы определить, сколько букетов можно сделать на mid день. - если количество букетов больше или равно m, сохраните mid как возможное решение и переместите end влево. - иначе переместите start вправо. 3⃣Возвращение результата: Верните найденное минимальное количество дней или -1, если сделать m букетов невозможно. 😎 Решение:
class Solution {
private:
    int getNumOfBouquets(vector<int>& bloomDay, int mid, int k) {
        int numOfBouquets = 0, count = 0;
        for (int day : bloomDay) {
            if (day <= mid) {
                count++;
            } else {
                count = 0;
            }
            if (count == k) {
                numOfBouquets++;
                count = 0;
            }
        }
        return numOfBouquets;
    }

public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        if (bloomDay.size() < m * k) return -1;
        int start = 0, end = *max_element(bloomDay.begin(), bloomDay.end());
        int minDays = -1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (getNumOfBouquets(bloomDay, mid, k) >= m) {
                minDays = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return minDays;
    }
};
Ставь 👍 и забирай 📚 Базу знаний

Получи грант до 1,2 млн руб. на обучение в магистратуре 4 офлайн программы, онлайн-магистратура по ML. Гранты до 1,2 млн руб.
Получи грант до 1,2 млн руб. на обучение в магистратуре 4 офлайн программы, онлайн-магистратура по ML. Гранты до 1,2 млн руб. Стажировки, диплом гос. образца и фокус на твоей карьере в ЦУ Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 1518. Water Bottles Сложность: easy Есть numBottles бутылок с водой, которые изначально наполнены водой. Вы можете обменять numExchange пустых бутылок на одну полную бутылку воды на рынке. Операция питья полной бутылки воды превращает её в пустую бутылку. Даны два целых числа numBottles и numExchange. Верните максимальное количество бутылок с водой, которые вы можете выпить. Пример:
Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.
👨‍💻 Алгоритм: 1⃣Инициализируйте переменную ответа consumedBottles значением 0. 2⃣Продолжайте выполнять следующие действия, пока количество numBottles больше или равно numExchange: — Выпейте numExchange количество полных бутылок, т.е. добавьте numExchange к consumedBottles. — Уменьшите numExchange от доступных полных бутылок numBottles. — Обменяйте пустые бутылки на одну полную бутылку, т.е. увеличьте numBottles на одну. 3⃣Верните consumedBottles + numBottles. 😎 Решение:
class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        int consumedBottles = 0;

        while (numBottles >= numExchange) {
            consumedBottles += numExchange;
            numBottles -= numExchange;
            numBottles++;
        }

        return consumedBottles + numBottles;
    }
};
Ставь 👍 и забирай 📚 Базу знаний

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

Задача: 499. The Maze III Сложность: hard В лабиринте есть мячик с пустыми пространствами (0) и стенами (1). Мячик может кати
Задача: 499. The Maze III Сложность: hard В лабиринте есть мячик с пустыми пространствами (0) и стенами (1). Мячик может катиться вверх, вниз, влево или вправо, пока не столкнется со стеной, затем выбрать новое направление. В лабиринте также есть отверстие, куда мячик упадет, если закатится в него. Дан лабиринт размером m x n, позиция мяча ball и отверстия hole, где ball = [ballrow, ballcol] и hole = [holerow, holecol]. Верните строку instructions с кратчайшим путем мячика к отверстию. Если существует несколько вариантов, верните лексикографически минимальный. Если путь невозможен, верните "impossible". Ответ должен содержать 'u' (вверх), 'd' (вниз), 'l' (влево) и 'r' (вправо). Расстояние — это количество пройденных пустых пространств от начальной позиции (исключительно) до конечной (включительно). Вы можете предположить, что границы лабиринта — это стены. В примере ниже они не указаны. Пример:
Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], ball = [4,3], hole = [0,1]
Output: "lul"
👨‍💻 Алгоритм: 1⃣Инициализация и вспомогательные функции Создайте функцию valid для проверки, находится ли координата (row, col) в пределах лабиринта и является ли она пустым пространством. Создайте функцию getNeighbors для получения списка соседей для данной позиции. Двигайтесь в каждом направлении (вверх, вниз, влево, вправо) до встречи со стеной. 2⃣Запуск алгоритма Дейкстры Инициализируйте очередь с начальной позицией мяча, где элементы с меньшим расстоянием имеют высокий приоритет, а при равных расстояниях выбирайте минимальную строку пути. Создайте структуру seen для отслеживания посещенных узлов. 3⃣Поиск кратчайшего пути Пока очередь не пуста, извлекайте узел с наименьшим расстоянием. Если узел посещен, пропустите его. Если это отверстие, верните текущий путь. Отметьте узел как посещенный, добавьте его соседей в очередь, обновив расстояние и путь. Если пути нет, верните "impossible". 😎 Решение:
#include <vector>
#include <queue>
#include <string>
#include <functional>

using namespace std;

struct State {
    int row, col, dist;
    string path;
    bool operator>(const State& other) const {
        return dist == other.dist ? path > other.path : dist > other.dist;
    }
};

class Solution {
public:
    string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
        int m = maze.size(), n = maze[0].size();
        vector<vector<int>> directions = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
        vector<string> textDirections = {"l", "u", "r", "d"};
        priority_queue<State, vector<State>, greater<State>> heap;
        vector<vector<bool>> seen(m, vector<bool>(n));
        heap.push({ball[0], ball[1], 0, ""});
        
        while (!heap.empty()) {
            auto [row, col, dist, path] = heap.top(); heap.pop();
            if (seen[row][col]) continue;
            if (row == hole[0] && col == hole[1]) return path;
            seen[row][col] = true;
            
            for (int i = 0; i < 4; ++i) {
                int r = row, c = col, d = 0;
                while (valid(r + directions[i][0], c + directions[i][1], maze)) {
                    r += directions[i][0]; c += directions[i][1]; d++;
                    if (r == hole[0] && c == hole[1]) break;
                }
                heap.push({r, c, dist + d, path + textDirections[i]});
            }
        }
        return "impossible";
    }
    
    bool valid(int row, int col, vector<vector<int>>& maze) {
        return row >= 0 && row < maze.size() && col >= 0 && col < maze[0].size() && maze[row][col] == 0;
    }
};
Ставь 👍 и забирай 📚 Базу знаний

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 На
Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

Задача: 82. Remove Duplicates from Sorted List II Сложность: medium Дан head — начало отсортированного связного списка. Удали
Задача: 82. Remove Duplicates from Sorted List II Сложность: medium Дан head — начало отсортированного связного списка. Удалите все узлы, содержащие повторяющиеся числа, оставив только уникальные значения. Верните отсортированный список без дубликатов. Пример:
Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
👨‍💻 Алгоритм: 1⃣Создаем фиктивный узел sentinel, указывающий на head, и инициализируем указатель pred, который всегда указывает на последний узел перед группой дубликатов. 2⃣Проходим по списку: если текущий узел и следующий имеют одинаковое значение — пропускаем все такие узлы и связываем pred->next с первым уникальным после них. 3⃣Если текущий элемент не дублируется — просто передвигаем pred и продолжаем проход 😎 Решение:
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* sentinel = new ListNode(0, head);
        ListNode* pred = sentinel;
        while (head != NULL) {
            if (head->next != NULL && head->val == head->next->val) {
                while (head->next != NULL && head->val == head->next->val) {
                    head = head->next;
                }
                pred->next = head->next;
            } else {
                pred = pred->next;
            }
            head = head->next;
        }
        return sentinel->next;
    }
};
Ставь 👍 и забирай 📚 Базу знаний

Инструменты для дома и дачи Ресанта Мойки высокого давления и дрели-шуруповёрты от Ресанта, Huter и Вихрь со скидкой до 40%!
Инструменты для дома и дачи Ресанта Мойки высокого давления и дрели-шуруповёрты от Ресанта, Huter и Вихрь со скидкой до 40%! Обновите свой арсенал инструментов! Купить #реклама market.yandex.ru О рекламодателе

Задача: 901. Online Stock Span Сложность: medium Разработайте алгоритм, который собирает ежедневные котировки цен на некоторые акции и возвращает размах цены этой акции за текущий день. Размах цены акции за один день - это максимальное количество дней подряд (начиная с этого дня и в обратном направлении), в течение которых цена акции была меньше или равна цене этого дня. Например, если цены акции за последние четыре дня равны [7,2,1,2], а цена акции сегодня равна 2, то размах сегодняшнего дня равен 4, поскольку, начиная с сегодняшнего дня, цена акции была меньше или равна 2 в течение 4 дней подряд. Также, если цена акции за последние четыре дня равна [7,34,1,2], а цена акции сегодня равна 8, то размах сегодняшнего дня равен 3, так как начиная с сегодняшнего дня цена акции была меньше или равна 8 в течение 3 дней подряд. Реализация класса StockSpanner: StockSpanner() Инициализирует объект класса. int next(int price) Возвращает размах цены акции, учитывая, что сегодняшняя цена равна price. Пример:
Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]
👨‍💻 Алгоритм: 1⃣Инициализировать стек для хранения пар значений (цена, размах) и переменную для текущего индекса. 2⃣Для метода next: Установить начальный размах текущего дня равным 1. Пока стек не пуст и верхний элемент стека имеет цену меньше или равную текущей цене: Добавить размах верхнего элемента стека к текущему размаху. Удалить верхний элемент стека. 3⃣Добавить текущую цену и размах на вершину стека. Вернуть текущий размах. 😎 Решение:
class StockSpanner {
    stack<pair<int, int>> stk;

public:
    StockSpanner() {}

    int next(int price) {
        int span = 1;
        while (!stk.empty() && stk.top().first <= price) {
            span += stk.top().second;
            stk.pop();
        }
        stk.push({price, span});
        return span;
    }
};
Ставь 👍 и забирай 📚 Базу знаний

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как
Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать #реклама yandex.ru О рекламодателе

Задача: 41. First Missing Positive Сложность: hard Дан неотсортированный массив целых чисел nums. Верните наименьшее положительное целое число, которого нет в массиве nums. Необходимо реализовать алгоритм, который работает за время O(n) и использует O(1) дополнительной памяти. Пример:
Input: nums = [3,4,-1,1] Output: 2
👨‍💻 Алгоритм: 1⃣Перебрать массив и попытаться разместить каждое число в правильной позиции: nums[i] должен быть равен i + 1 2⃣Используем swap, чтобы поставить каждый элемент на его "правильное" место, если это возможно 3⃣После расстановки — находим первый индекс, где nums[i] != i + 1. Возвращаем i + 1 😎 Решение:
int firstMissingPositive(std::vector<int>& nums) {
    for (int i = 0; i < nums.size(); ) {
        if (nums[i] <= 0 || nums[i] > nums.size()) {
            ++i;
            continue;
        }
        if (nums[i] == i + 1) {
            ++i;
            continue;
        }
        int j = nums[i];
        if (nums[j - 1] == nums[i]) {
            ++i;
            continue;
        }
        std::swap(nums[j - 1], nums[i]);
    }

    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }

    return nums.size() + 1;
}
Ставь 👍 и забирай 📚 Базу знаний

Дарим подписку 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;
    }
};
Ставь 👍 и забирай 📚 Базу знаний