Задача: 207. Course Schedule
Сложность: medium

У вас есть numCourses курсов, пронумерованных от 0 до numCourses - 1, и массив prerequisites, где prerequisites[i] = [ai, bi] означает, что курс ai требует предварительного прохождения курса bi.

Нужно вернуть true, если можно пройти все курсы, иначе — false.

Пример:

Input: numCourses = 2, prerequisites = [[1,0]] Output: true

👨‍💻 Алгоритм:

1⃣Построить граф зависимостей:
Создаем список смежности adj и массив входящих степеней indegree, чтобы отразить зависимости между курсами.

2⃣Найти стартовые узлы и запустить BFS:
Добавляем в очередь все курсы с indegree == 0 (те, которые можно взять сразу). Проходим в ширину по графу, уменьшая indegree зависимых курсов.

3⃣Проверка количества завершенных курсов:
Если количество завершённых курсов (nodesVisited) совпадает с numCourses, возвращаем true, иначе false. Это означает, что в графе нет циклов, мешающих прохождению.

😎 Решение:

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> indegree(numCourses);
        vector<vector<int>> adj(numCourses);
        for (auto prerequisite : prerequisites) {
            adj[prerequisite[1]].push_back(prerequisite[0]);
            indegree[prerequisite[0]]++;
        }

        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        int nodesVisited = 0;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            nodesVisited++;

            for (auto& neighbor : adj[node]) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        return nodesVisited == numCourses;
    }
};

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

Задача: 1244. Design A Leaderboard
Сложность: medium

Разработайте класс Leaderboard, который содержит 3 функции: addScore(playerId, score): Обновляет таблицу лидеров, добавляя счет к счету данного игрока. Если в таблице лидеров нет игрока с таким id, добавьте его в таблицу лидеров с заданным счетом. top(K): Возвращает сумму очков K лучших игроков. reset(playerId): Сбрасывает счет игрока с заданным идентификатором в 0 (другими словами, стирает его из таблицы лидеров). Гарантируется, что игрок был добавлен в таблицу лидеров до вызова этой функции. Изначально таблица лидеров пуста.

Пример:

Input: 
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output: 
[null,null,null,null,null,null,73,null,null,null,141]

👨‍💻 Алгоритм:

1⃣addScore(playerId, score):
Если игрок уже существует в таблице лидеров, добавляем к его текущему счету новое значение.
Если игрок не существует, добавляем его с заданным счетом.

2⃣top(K):
Сортируем игроков по их счету в порядке убывания.
Возвращаем сумму очков K лучших игроков.

3⃣reset(playerId):
Устанавливаем счет игрока в 0.

😎 Решение:

class Leaderboard {
private:
    std::unordered_map<int, int> scores;

public:
    Leaderboard() {}

    void addScore(int playerId, int score) {
        scores[playerId] += score;
    }

    int top(int K) {
        std::vector<int> all_scores;
        for (auto& [playerId, score] : scores) {
            all_scores.push_back(score);
        }
        std::sort(all_scores.rbegin(), all_scores.rend());
        int sum = 0;
        for (int i = 0; i < K && i < all_scores.size(); ++i) {
            sum += all_scores[i];
        }
        return sum;
    }

    void reset(int playerId) {
        scores[playerId] = 0;
    }
};

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

Задача: 1431. Kids With the Greatest Number of Candies
Сложность: easy

Дано n детей с конфетами. Вам дан целочисленный массив candies, где каждый candies[i] представляет количество конфет у i-го ребенка, и целое число extraCandies, обозначающее количество дополнительных конфет, которые у вас есть.

Вернуть булев массив result длиной n, где result[i] равно true, если, дав i-му ребенку все дополнительные конфеты, он будет иметь наибольшее количество конфет среди всех детей, или false в противном случае.

Обратите внимание, что несколько детей могут иметь наибольшее количество конфет.

Пример:

Input: candies = [2,3,5,1,3], extraCandies = 3
Output: [true,true,true,false,true] 
Explanation: If you give all extraCandies to:
- Kid 1, they will have 2 + 3 = 5 candies, which is the greatest among the kids.
- Kid 2, they will have 3 + 3 = 6 candies, which is the greatest among the kids.
- Kid 3, they will have 5 + 3 = 8 candies, which is the greatest among the kids.
- Kid 4, they will have 1 + 3 = 4 candies, which is not the greatest among the kids.
- Kid 5, they will have 3 + 3 = 6 candies, which is the greatest among the kids.

👨‍💻 Алгоритм:

1⃣Найдите максимальное количество конфет в массиве candies, сохраняя его в переменной maxCandies.

2⃣Создайте булев список answer и пройдитесь по массиву candies, добавляя в answer значение true, если текущий ребенок с добавленными extraCandies имеет количество конфет больше или равное maxCandies, иначе добавляйте false.

3⃣Верните список answer.

😎 Решение:

class Solution {
public:
    vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
        int maxCandies = *max_element(candies.begin(), candies.end());
        vector<bool> result;
        for (int candy : candies) {
            result.push_back(candy + extraCandies >= maxCandies);
        }
        return result;
    }
};

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

Задача: 1801. Number of Orders in the Backlog
Сложность: medium

Дан двумерный целочисленный массив orders, где каждый элемент orders[i] = [pricei, amounti, orderTypei] обозначает, что было размещено amounti заказов типа orderTypei по цене pricei. Тип заказа orderTypei может быть:

- 0, если это партия заказов на покупку, или
- 1, если это партия заказов на продажу.

Обратите внимание, что orders[i] представляет собой партию из amounti независимых заказов с одинаковой ценой и типом. Все заказы, представленные orders[i], будут размещены перед всеми заказами, представленными orders[i+1] для всех допустимых i.

Существует список невыполненных заказов (backlog), который изначально пуст. При размещении заказа происходит следующее:

- Если это заказ на покупку, вы просматриваете заказ на продажу с наименьшей ценой в списке невыполненных заказов. Если цена этого заказа на продажу меньше или равна цене текущего заказа на покупку, они будут сопоставлены и выполнены, и этот заказ на продажу будет удален из списка. В противном случае заказ на покупку добавляется в список невыполненных заказов.
- Если это заказ на продажу, вы просматриваете заказ на покупку с наибольшей ценой в списке невыполненных заказов. Если цена этого заказа на покупку больше или равна цене текущего заказа на продажу, они будут сопоставлены и выполнены, и этот заказ на покупку будет удален из списка. В противном случае заказ на продажу добавляется в список невыполненных заказов.

Верните общее количество заказов в списке невыполненных заказов после размещения всех заказов из входных данных. Поскольку это число может быть большим, верните его по модулю 10^9 + 7.

Пример:

Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
Output: 6

👨‍💻 Алгоритм:

1⃣Обрабатывайте каждый заказ в orders. Для заказа на покупку сравните с самыми дешевыми заказами на продажу в списке и выполняйте их при возможности, иначе добавьте в список.

2⃣Для заказа на продажу сравните с самыми дорогими заказами на покупку в списке и выполняйте их при возможности, иначе добавьте в список.

3⃣Подсчитайте общее количество оставшихся заказов в списке и верните его по модулю 10^9 + 7.

😎 Решение:

class Solution {
public:
    int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
        const int MOD = 1'000'000'007;
        priority_queue<pair<int, int>> buyOrders;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> sellOrders;

        for (const auto& order : orders) {
            int price = order[0], amount = order[1], orderType = order[2];
            auto& primaryQueue = orderType == 0 ? sellOrders : buyOrders;
            auto& secondaryQueue = orderType == 0 ? buyOrders : sellOrders;

            while (amount > 0 && !primaryQueue.empty() &&
                  (orderType == 0 ? primaryQueue.top().first <= price : primaryQueue.top().first >= price)) {
                auto [topPrice, topAmount] = primaryQueue.top();
                primaryQueue.pop();
                int executedAmount = min(amount, topAmount);
                amount -= executedAmount;
                if (topAmount > executedAmount)
                    primaryQueue.emplace(topPrice, topAmount - executedAmount);
            }
            if (amount > 0)
                secondaryQueue.emplace(price, amount);
        }

        auto countTotalOrders = [](auto& queue) {
            long long total = 0;
            while (!queue.empty()) {
                total = (total + queue.top().second) % MOD;
                queue.pop();
            }
            return total;
        };

        return (countTotalOrders(buyOrders) + countTotalOrders(sellOrders)) % MOD;
    }
};

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

Задача: 1217. Minimum Cost to Move Chips to The Same Position
Сложность: easy

У нас есть n фишек, где позиция i-й фишки равна position[i].

Нам нужно переместить все фишки в одну и ту же позицию. За один шаг мы можем изменить позицию i-й фишки с position[i] на:
position[i] + 2 или position[i] - 2 с затратами = 0.
position[i] + 1 или position[i] - 1 с затратами = 1.
Верните минимальные затраты, необходимые для перемещения всех фишек в одну и ту же позицию.

Пример:

Input: position = [2,2,2,3,3]
Output: 2
Explanation: We can move the two chips at position  3 to position 2. Each move has cost = 1. The total cost = 2.

👨‍💻 Алгоритм:

1⃣Посчитать количество фишек на четных и нечетных позициях.

2⃣Сравнить количество фишек на четных и нечетных позициях.

3⃣Вернуть минимальное количество фишек как минимальную стоимость для перемещения всех фишек в одну позицию.

😎 Решение:

class Solution {
public:
    int minCostToMoveChips(vector<int>& position) {
        int evenCount = 0;
        int oddCount = 0;
        
        for (int pos : position) {
            if (pos % 2 == 0) {
                evenCount++;
            } else {
                oddCount++;
            }
        }
        
        return min(evenCount, oddCount);
    }
};

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

Задача: 780. Reaching Points
Сложность: hard

Даны четыре целых числа sx, sy, tx и ty, верните true, если возможно преобразовать точку (sx, sy) в точку (tx, ty) с помощью некоторых операций, иначе верните false.

Допустимая операция для некоторой точки (x, y) заключается в преобразовании её либо в (x, x + y), либо в (x + y, y).

Пример:

Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: true
Explanation:
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

👨‍💻 Алгоритм:

1⃣Повторно вычитайте меньшее из {tx, ty} из большего из {tx, ty}.

2⃣Продолжайте вычитание, пока tx и ty больше или равны sx и sy соответственно.

3⃣Ответ будет true, если и только если в конечном итоге мы достигнем точки sx, sy.

😎 Решение:

class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx >= sx && ty >= sy) {
            if (sx == tx && sy == ty) return true;
            if (tx > ty) {
                tx -= ty;
            } else {
                ty -= tx;
            }
        }
        return false;
    }
};

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

🚨 60 минут до финала

Через час мы закроем краудфандинг easyoffer 2.0
Это последний шанс вписаться в самые выгодные условия.

👉 https://planeta.ru/campaigns/easyoffer

Задача: 240. Search a 2D Matrix II
Сложность: medium

Целые числа в каждой строке отсортированы по возрастанию слева направо
Целые числа в каждом столбце отсортированы по возрастанию сверху вниз

Пример:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 Output: true

👨‍💻 Алгоритм:

1⃣Проверяем каждую строку и каждый столбец вдоль диагонали с помощью бинарного поиска

2⃣Для каждой позиции i ищем target сначала по строке, затем по столбцу, начиная с i-й строки и i-го столбца

3⃣Если target найден хотя бы в одном из направлений, возвращаем true, иначе false

😎 Решение:

class Solution {
public:
    bool binarySearch(vector<vector<int>>& matrix, int target, int start, bool vertical) {
        int lo = start;
        int hi = vertical ? matrix[0].size() - 1 : matrix.size() - 1;

        while (hi >= lo) {
            int mid = (lo + hi) / 2;
            if (vertical) {
                if (matrix[start][mid] < target) {
                    lo = mid + 1;
                } else if (matrix[start][mid] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            } else {
                if (matrix[mid][start] < target) {
                    lo = mid + 1;
                } else if (matrix[mid][start] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            }
        }
        return false;
    }

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;

        int shorterDim = min(matrix.size(), matrix[0].size());
        for (int i = 0; i < shorterDim; i++) {
            if (binarySearch(matrix, target, i, true) || binarySearch(matrix, target, i, false)) {
                return true;
            }
        }
        return false;
    }
};

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

Задача: 122. Best Time to Buy and Sell Stock II
Сложность: medium

Вам дан массив целых чисел prices, где prices[i] — это цена акции в i-й день.
Каждый день вы можете купить и/или продать акцию, но держать в руках можно только одну. Разрешено покупать и продавать в тот же день.
Найдите и верните максимальную прибыль, которую можно получить.

Пример:

Input: prices = [7,1,5,3,6,4] Output: 7
Explanation:
Купить на 2-й день (цена = 1), продать на 3-й (цена = 5), прибыль = 4
Купить на 4-й день (цена = 3), продать на 5-й (цена = 6), прибыль = 3
Итоговая прибыль = 4 + 3 = 7

👨‍💻 Алгоритм:

1⃣Найдём все возрастающие отрезки (впадина → пик), и прибавим к прибыли разницу между пиком и впадиной.

2⃣Не стоит пытаться найти один глобальный минимум и максимум — это уменьшит прибыль. Лучше учитывать все локальные сделки, даже если они малы.

3⃣Реализуем проход по массиву:
Ищем впадину (где цена начинает расти)
Затем ищем пик (где рост заканчивается)
Добавляем разницу в maxprofit
Повторяем до конца

😎 Решение:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int i = 0;
        int valley = prices[0];
        int peak = prices[0];
        int maxprofit = 0;

        while (i < prices.size() - 1) {
            while (i < prices.size() - 1 && prices[i] >= prices[i + 1]) i++;
            valley = prices[i];

            while (i < prices.size() - 1 && prices[i] <= prices[i + 1]) i++;
            peak = prices[i];

            maxprofit += peak - valley;
        }

        return maxprofit;
    }
};

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

Задача: 1510. Stone Game IV
Сложность: hard

Алиса и Боб поочередно играют в игру, причем Алиса начинает первой.

Изначально в куче n камней. В ходе каждого хода игрок удаляет любое ненулевое количество камней, являющееся квадратом целого числа.

Кроме того, если игрок не может сделать ход, он/она проигрывает игру.

Дано положительное целое число n, верните true, если и только если Алиса выиграет игру, иначе верните false, предполагая, что оба игрока играют оптимально.

Пример:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

👨‍💻 Алгоритм:

1⃣Функция dfs(remain) представляет собой проверку, должен ли текущий игрок выиграть при оставшихся remain камнях.

2⃣Для определения результата dfs(n) необходимо итерировать k от 0, чтобы проверить, существует ли такое k, что dfs(remain - k*k) == False. Чтобы предотвратить избыточные вычисления, используйте карту для хранения результатов функции dfs.

3⃣Не забудьте базовые случаи: dfs(0) == False и dfs(1) == True.

😎 Решение:

class Solution {
public:
    bool winnerSquareGame(int n) {
        unordered_map<int, bool> cache;
        cache[0] = false;
        return dfs(cache, n);
    }

    bool dfs(unordered_map<int, bool>& cache, int remain) {
        if (cache.find(remain) != cache.end()) {
            return cache[remain];
        }
        int sqrt_root = (int) sqrt(remain);
        for (int i = 1; i <= sqrt_root; ++i) {
            if (!dfs(cache, remain - i * i)) {
                cache[remain] = true;
                return true;
            }
        }
        cache[remain] = false;
        return false;
    }
};

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

Задача: 1024. Video Stitching
Сложность: medium

Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается массивом clips, где clips[i] = [starti, endi] указывает, что i-й клип начинается в starti и заканчивается в endi. Мы можем произвольно разрезать эти клипы на сегменты. Например, клип [0, 7] может быть разрезан на сегменты [0, 1] + [1, 3] + [3, 7]. Верните минимальное количество клипов, необходимое для того, чтобы мы могли разрезать клипы на сегменты, охватывающие все спортивное событие [0, время]. Если задача невыполнима, верните -1.

Пример:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3

👨‍💻 Алгоритм:

1⃣Сортировка клипов:
Отсортируйте клипы по начальным значениям. Если начальные значения равны, отсортируйте по конечным значениям в убывающем порядке.

2⃣Выбор клипов:
Используйте жадный алгоритм для выбора клипов. Начните с начальной точки 0 и двигайтесь вперед, выбирая клип, который может покрыть наибольший диапазон.
Если обнаруживается, что начальная точка текущего клипа больше текущей позиции, это означает, что клипы не могут покрыть промежуток, и нужно вернуть -1.

3⃣Проверка покрытия:
Продолжайте процесс, пока не покроете весь диапазон от 0 до T. Если в конце процесса достигнута или превышена точка T, верните количество использованных клипов, иначе верните -1.

😎 Решение:

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int T) {
        sort(clips.begin(), clips.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
        });
        int end = -1, end2 = 0, res = 0;
        for (const auto& clip : clips) {
            if (end2 >= T || clip[0] > end2) break;
            if (end < clip[0] && clip[0] <= end2) {
                res++;
                end = end2;
            }
            end2 = max(end2, clip[1]);
        }
        return end2 >= T ? res : -1;
    }
};

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

Задача: 974. Subarray Sums Divisible by K
Сложность: medium

Дан целочисленный массив nums и целое число k. Верните количество непустых подмассивов, сумма которых делится на k.

Подмассив — это непрерывная часть массива.

Пример:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

👨‍💻 Алгоритм:

1⃣Инициализация и подготовка. Инициализируйте prefixMod = 0 для хранения остатка от суммы элементов до текущего индекса при делении на k. Инициализируйте result = 0 для хранения количества подмассивов, сумма которых делится на k. Инициализируйте массив modGroups длиной k, где modGroups[R] хранит количество подмассивов с остатком R. Установите modGroups[0] = 1.

2⃣Итерирование по массиву. Для каждого элемента массива nums вычислите новый prefixMod как (prefixMod + nums[i] % k + k) % k, чтобы избежать отрицательных значений. Увеличьте result на значение modGroups[prefixMod], чтобы добавить количество подмассивов с текущим остатком. Увеличьте значение modGroups[prefixMod] на 1 для будущих совпадений.

3⃣Возврат результата. Верните значение result, которое содержит количество подмассивов, сумма которых делится на k.

😎 Решение:

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int prefixMod = 0, result = 0;
        vector<int> modGroups(k);
        modGroups[0] = 1;

        for (int num : nums) {
            prefixMod = (prefixMod + num % k + k) % k;
            result += modGroups[prefixMod];
            modGroups[prefixMod]++;
        }

        return result;
    }
};

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

Задача: 918. Maximum Sum Circular Subarray
Сложность: medium

Если задан круговой целочисленный массив nums длины n, верните максимально возможную сумму непустого подмассива nums. Круговой массив означает, что конец массива соединяется с его началом. Формально, следующий элемент nums[i] равен nums[(i + 1) % n], а предыдущий элемент nums[i] равен nums[(i - 1 + n) % n]. Подмассив может включать каждый элемент фиксированного буфера nums не более одного раза. Формально, для подмассива nums[i], nums[i + 1], ..., nums[j] не существует i <= k1, k2 <= j, при этом k1 % n == k2 % n.

Пример:

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

👨‍💻 Алгоритм:

1⃣Найти стандартную максимальную сумму подмассива с помощью алгоритма Кадане.

2⃣Найти минимальную сумму подмассива с помощью алгоритма Кадане и вычесть ее из общей суммы массива.

3⃣Вернуть максимум между стандартной максимальной суммой подмассива и общей суммой массива минус минимальную сумму подмассива, если результат не равен 0 (чтобы учесть случай, когда все числа отрицательные).

😎 Решение:

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int kadane(vector<int>& arr) {
            int currentSum = arr[0], maxSum = arr[0];
            for (int i = 1; i < arr.size(); ++i) {
                currentSum = max(arr[i], currentSum + arr[i]);
                maxSum = max(maxSum, currentSum);
            }
            return maxSum;
        }

        int maxKadane = kadane(nums);
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        for (int& num : nums) num = -num;
        int minKadane = kadane(nums);

        return max(maxKadane, totalSum + minKadane == 0 ? maxKadane : totalSum + minKadane);
    }
};

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

Задача: 1302. Deepest Leaves Sum
Сложность: medium

Дано корень бинарного дерева, вернуть сумму значений его самых глубоких листьев.

Пример:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

👨‍💻 Алгоритм:

1⃣Поместите корень в стек.

2⃣Пока стек не пуст. Извлеките узел из стека и обновите текущее число. Если узел является листом, обновите сумму самых глубоких листьев deepest_sum. Поместите правый и левый дочерние узлы в стек.

3⃣Верните deepest_sum.

😎 Решение:

class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
        int deepestSum = 0, depth = 0, currDepth;
        stack<pair<TreeNode*, int>> stack;
        stack.push({root, 0});

        while (!stack.empty()) {
            auto [node, currDepth] = stack.top();
            stack.pop();

            if (!node->left && !node->right) {
                if (depth < currDepth) {
                    deepestSum = node->val;
                    depth = currDepth;
                } else if (depth == currDepth) {
                    deepestSum += node->val;
                }
            } else {
                if (node->right) {
                    stack.push({node->right, currDepth + 1});
                }
                if (node->left) {
                    stack.push({node->left, currDepth + 1});
                }
            }
        }
        return deepestSum;
    }
};

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

Задача: 345. Reverse Vowels of a String
Сложность: easy

Дана строка s, переверните только все гласные в строке и верните её.

Гласные: 'a', 'e', 'i', 'o', 'u', а также их верхние регистры.

Пример:

Input: s = "hello"
Output: "holle"

👨‍💻 Алгоритм:

1⃣Инициализация указателей и гласных:
Создайте набор гласных для быстрой проверки.
Установите два указателя: один на начало строки (left), другой на конец строки (right).

2⃣Перестановка гласных:
Пока левый указатель меньше правого, перемещайте указатели к центру, пока не найдёте гласные.
Обменивайте найденные гласные и продолжайте сдвигать указатели.

3⃣Завершение работы:
Когда указатели пересекутся, остановите процесс и верните строку.

😎 Решение:

class Solution {
public:
    string reverseVowels(string s) {
        unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
        int left = 0, right = s.size() - 1;
        
        while (left < right) {
            if (vowels.find(s[left]) == vowels.end()) {
                left++;
            } else if (vowels.find(s[right]) == vowels.end()) {
                right--;
            } else {
                swap(s[left], s[right]);
                left++;
                right--;
            }
        }
        
        return s;
    }
};

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