uk
Feedback

Не попадись на ботовода! Telemetrio знаходить і позначає такі канали мітками 👉 Хочеш бачити мітку, оформляй підписку

C/C++ | LeetCode

C/C++ | LeetCode

Відкрити в Telegram

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

Показати більше
3 199
Підписники
-124 години
-57 днів
-3230 днів

Завантажуємо дані

Залучення підписників
лист '26
листопад '26
+10
в 0 каналах
жовтень '26
+27
в 0 каналах
Get PRO
вересень '26
+42
в 0 каналах
Get PRO
серпень '26
+32
в 0 каналах
Get PRO
липень '26
+42
в 0 каналах
Get PRO
червень '26
+30
в 1 каналах
Get PRO
травень '26
+35
в 0 каналах
Get PRO
квітень '26
+35
в 0 каналах
Get PRO
березень '26
+32
в 0 каналах
Get PRO
лютий '26
+45
в 0 каналах
Get PRO
січень '26
+35
в 0 каналах
Get PRO
грудень '25
+37
в 0 каналах
Get PRO
листопад '25
+84
в 0 каналах
Get PRO
жовтень '25
+43
в 0 каналах
Get PRO
вересень '25
+35
в 0 каналах
Get PRO
серпень '25
+40
в 0 каналах
Get PRO
липень '25
+40
в 1 каналах
Get PRO
червень '25
+43
в 0 каналах
Get PRO
травень '25
+44
в 0 каналах
Get PRO
квітень '25
+61
в 0 каналах
Get PRO
березень '25
+60
в 1 каналах
Get PRO
лютий '25
+179
в 3 каналах
Get PRO
січень '25
+79
в 53 каналах
Get PRO
грудень '24
+64
в 0 каналах
Get PRO
листопад '24
+91
в 1 каналах
Get PRO
жовтень '24
+424
в 13 каналах
Get PRO
вересень '24
+1 488
в 331 каналах
Get PRO
серпень '24
+91
в 0 каналах
Get PRO
липень '24
+826
в 219 каналах
Get PRO
червень '24
+1 211
в 232 каналах
Дата
Залучення підписників
Згадування
Канали
15 листопада+2
14 листопада0
13 листопада0
12 листопада0
11 листопада+1
10 листопада+1
09 листопада0
08 листопада+2
07 листопада+1
06 листопада+1
05 листопада0
04 листопада+1
03 листопада0
02 листопада+1
01 листопада0
Дописи каналу
Задача: 1129. Shortest Path with Alternating Colors Сложность: medium Вам дано целое число n, количество узлов в ориентированном графе, где узлы помечены от 0 до n - 1. Каждое ребро в этом графе может быть красным или синим, и могут быть самопетли и параллельные ребра. Вам даны два массива redEdges и blueEdges, где: redEdges[i] = [ai, bi] указывает, что в графе существует направленное красное ребро от узла ai к узлу bi, и blueEdges[j] = [uj, vj] указывает, что в графе существует направленное синее ребро от узла uj к узлу vj. Верните массив answer длины n, где каждый answer[x] — это длина кратчайшего пути от узла 0 до узла x, такого что цвета ребер чередуются вдоль пути, или -1, если такого пути не существует. Пример:
Input: n = 3, redEdges = [[0,1],[1,2]], blueEdges = []
Output: [0,1,-1]
👨‍💻 Алгоритм: 1⃣Создание структуры данных и инициализация: Создайте список смежности adj, который будет содержать пары (сосед, цвет) для каждого узла. Создайте массив answer длиной n, инициализированный значением -1, чтобы хранить длину кратчайшего пути для каждого узла. Создайте 2D массив visit для отслеживания, были ли узлы посещены с использованием ребра определённого цвета. 2⃣Инициализация очереди и начальных условий: Создайте очередь для хранения трёх значений (узел, количество шагов, цвет предыдущего ребра). Добавьте в очередь начальный узел (0, 0, -1) и установите visit[0][0] и visit[0][1] в true, так как повторное посещение узла 0 бессмысленно. 3⃣Обработка очереди и обновление результата: Пока очередь не пуста, извлекайте элемент из очереди и получайте (узел, количество шагов, цвет предыдущего ребра). Для каждого соседа, если сосед не был посещён с использованием ребра текущего цвета и текущий цвет не равен предыдущему, обновите массив answer и добавьте соседа в очередь. 😎 Решение:
class Solution {
public:
    vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& redEdges, vector<vector<int>>& blueEdges) {
        unordered_map<int, vector<pair<int, int>>> adj;
        for (const auto& edge : redEdges) {
            adj[edge[0]].emplace_back(edge[1], 0);
        }
        for (const auto& edge : blueEdges) {
            adj[edge[0]].emplace_back(edge[1], 1);
        }

        vector<int> answer(n, -1);
        vector<vector<bool>> visit(n, vector<bool>(2, false));
        queue<tuple<int, int, int>> q;
        q.emplace(0, 0, -1);
        answer[0] = 0;
        visit[0][0] = visit[0][1] = true;

        while (!q.empty()) {
            auto [node, steps, prevColor] = q.front();
            q.pop();

            for (const auto& [neighbor, color] : adj[node]) {
                if (!visit[neighbor][color] && color != prevColor) {
                    if (answer[neighbor] == -1) {
                        answer[neighbor] = steps + 1;
                    }
                    visit[neighbor][color] = true;
                    q.emplace(neighbor, steps + 1, color);
                }
            }
        }
        return answer;
    }
};
Ставь 👍 и забирай 📚 Базу знаний

2
Задача: 1273. Delete Tree Nodes Сложность: medium Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве. Пример: Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1] Output: 2 👨‍💻 Алгоритм: 1⃣Постройте дерево из заданных узлов, значений и родителей. 2⃣Используйте постфиксный обход для вычисления суммы значений в каждом поддереве и помечайте узлы для удаления, если их сумма равна нулю. 3⃣Удалите отмеченные узлы и их поддеревья и верните количество оставшихся узлов. 😎 Решение: class Solution { public: int deleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) { unordered_map<int, vector<int>> tree; for (int i = 0; i < nodes; ++i) { tree[parent[i]].push_back(i); } return dfs(0, tree, value).second; } private: pair<int, int> dfs(int node, unordered_map<int, vector<int>>& tree, vector<int>& value) { int totalSum = value[node]; int totalCount = 1; for (int child : tree[node]) { auto [childSum, childCount] = dfs(child, tree, value); totalSum += childSum; totalCount += childCount; } if (totalSum == 0) { return {0, 0}; } return {totalSum, totalCount}; } }; Ставь 👍 и забирай 📚 Базу знаний
154
3
Задача: 1017. Convert to Base -2 Сложность: medium Если задано целое число n, верните двоичную строку, представляющую его в базе -2. Обратите внимание, что возвращаемая строка не должна содержать ведущих нулей, за исключением случаев, когда строка равна "0". Пример: Input: n = 2 Output: "110" 👨‍💻 Алгоритм: 1⃣Инициализация переменных: Создайте пустую строку для хранения двоичного представления числа. Используйте цикл для вычисления каждой цифры числа в базе -2. 2⃣Вычисление цифр: В цикле, пока число не равно 0, вычисляйте остаток от деления числа на -2. Если остаток отрицательный, корректируйте его, добавляя 2, и увеличивайте число на 1. Добавляйте остаток в начало строки. 3⃣Возврат результата: Верните строку, представляющую число в базе -2. Если строка пустая, верните "0". 😎 Решение: class Solution { public: string baseNeg2(int n) { if (n == 0) return "0"; string res = ""; while (n != 0) { int remainder = n % -2; n /= -2; if (remainder < 0) { remainder += 2; n += 1; } res = to_string(remainder) + res; } return res; } }; Ставь 👍 и забирай 📚 Базу знаний
160
4
Задача: 1496. Path Crossing Сложность: easy Дана строка path, где path[i] = 'N', 'S', 'E' или 'W', каждая из которых представляет движение на одну единицу на север, юг, восток или запад соответственно. Вы начинаете с точки (0, 0) на 2D плоскости и идете по пути, указанному в path. Верните true, если путь пересекает сам себя в какой-либо точке, то есть если вы в какой-то момент окажетесь в месте, которое уже посещали ранее. В противном случае верните false. Пример: Input: path = "NESWW" Output: true Explanation: Notice that the path visits the origin twice. 👨‍💻 Алгоритм: 1⃣Инициализация переменных: Создать хэш-карту moves, которая сопоставляет символы 'N', 'S', 'E', 'W' с соответствующими значениями. Инициализировать множество visited с начальной точкой (0, 0). Установить начальные координаты x = 0 и y = 0. 2⃣Проход по строке path: Для каждого символа c в path получить значения (dx, dy) из moves[c]. Обновить координаты: добавить dx к x и dy к y. Проверить, содержится ли текущая точка (x, y) в visited. Если да, вернуть true. Добавить текущую точку (x, y) в visited. 3⃣Возврат результата: Если ни одна точка не пересекалась, вернуть false. 😎 Решение: class Solution { public: bool isPathCrossing(string path) { unordered_map<char, pair<int, int>> moves = { {'N', {0, 1}}, {'S', {0, -1}}, {'E', {1, 0}}, {'W', {-1, 0}} }; set<pair<int, int>> visited = {{0, 0}}; int x = 0, y = 0; for (char c : path) { x += moves[c].first; y += moves[c].second; if (visited.count({x, y})) { return true; } visited.insert({x, y}); } return false; } }; Ставь 👍 и забирай 📚 Базу знаний
169
5
Задача: 1178. Number of Valid Words for Each PuzzleHardTopicsHint Сложность: hard Относительно заданной строки-головоломки, слово является допустимым, если выполняются оба следующих условия: Слово содержит первую букву головоломки. Каждая буква в слове присутствует в головоломке. Например, если головоломка "abcdefg", то допустимыми словами являются "faced", "cabbage" и "baggage", а недопустимыми словами являются "beefed" (не включает 'a') и "based" (включает 's', которой нет в головоломке). Верните массив answer, где answer[i] - это количество слов в данном списке слов words, которые допустимы относительно головоломки puzzles[i]. Пример: Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"] Output: [0,1,3,2,0] 👨‍💻 Алгоритм: 1⃣Постройте карту. Для каждого слова в списке words: Преобразуйте его в битовую маску его символов. Если эта битовая маска не была ранее встречена, сохраните ее в качестве ключа в карте со значением 1. Если она была ранее встречена, увеличьте счетчик для этой битовой маски на 1. 2⃣Подсчитайте количество допустимых слов для каждой головоломки. Для каждой головоломки в списке puzzles: Преобразуйте ее в битовую маску ее символов. Итерируйте по каждой возможной подмаске, содержащей первую букву головоломки (puzzle[i][0]). Слово является допустимым для головоломки, если его битовая маска совпадает с одной из подмасок головоломки. 3⃣Для каждой подмаски увеличивайте счетчик на количество слов, соответствующих подмаске. Мы можем найти количество слов, соответствующих подмаске, используя карту, построенную на предыдущем шаге. 😎 Решение: class Solution { private: int bitmask(string word) { int mask = 0; for (char letter : word) { mask |= 1 << (letter - 'a'); } return mask; } public: vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) { unordered_map<int, int> wordCount; for (string word : words) { int mask = bitmask(word); wordCount[mask]++; } vector<int> result; for (string puzzle : puzzles) { int first = 1 << (puzzle[0] - 'a'); int count = wordCount[first]; int mask = bitmask(puzzle.substr(1)); for (int submask = mask; submask > 0; submask = (submask - 1) & mask) { count += wordCount[submask | first]; } result.push_back(count); } return result; } }; Ставь 👍 и забирай 📚 Базу знаний
159
6
Задача: 894. All Possible Full Binary Trees Сложность: medium Учитывая целое число n, верните список всех возможных полных бинарных деревьев с узлами. Каждый узел каждого дерева в ответе должен иметь Node.val == 0. Каждый элемент ответа является корневым узлом одного возможного дерева. Вы можете вернуть конечный список деревьев в любом порядке. Полное бинарное дерево - это бинарное дерево, в котором каждый узел имеет ровно 0 или 2 дочерних. Пример: Input: n = 7 Output: [[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]] 👨‍💻 Алгоритм: 1⃣Если n четное, вернуть пустой список, так как полное бинарное дерево не может иметь четное количество узлов. 2⃣Если n == 1, вернуть дерево с одним узлом. Для всех возможных значений i от 1 до n-1 с шагом 2: Создать левое поддерево с i узлами. Создать правое поддерево с n-1-i узлами. Объединить все комбинации левого и правого поддеревьев с новым корнем, добавив их в список результатов. 3⃣Вернуть список результатов. 😎 Решение: struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(0), left(nullptr), right(nullptr) {} }; class Solution { public: vector<TreeNode*> allPossibleFBT(int n) { if (n % 2 == 0) return {}; if (n == 1) return {new TreeNode(0)}; vector<TreeNode*> result; for (int i = 1; i < n; i += 2) { vector<TreeNode*> leftTrees = allPossibleFBT(i); vector<TreeNode*> rightTrees = allPossibleFBT(n - 1 - i); for (auto left : leftTrees) { for (auto right : rightTrees) { TreeNode* root = new TreeNode(0); root.left = left; root.right = right; result.push_back(root); } } } return result; } }; Ставь 👍 и забирай 📚 Базу знаний
167
7
Задача: 1066. Campus Bikes II Сложность: medium На кампусе, представленном в виде двумерной сетки, есть n рабочих и m велосипедов, где n <= m. Каждый рабочий и велосипед имеют координаты на этой сетке. Мы назначаем каждому рабочему уникальный велосипед таким образом, чтобы сумма Манхэттенских расстояний между каждым рабочим и назначенным ему велосипедом была минимальной. Верните минимально возможную сумму Манхэттенских расстояний между каждым рабочим и назначенным ему велосипедом. Манхэттенское расстояние между двумя точками p1 и p2 вычисляется как Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|. Пример: Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"] Output: [[3,7],[9,13],[10,17]] 👨‍💻 Алгоритм: 1⃣Для каждого рабочего, начиная с рабочего с индексом 0, пройдите по всем велосипедам и назначьте велосипед рабочему, если он доступен (visited[bikeIndex] = false). После назначения велосипеда отметьте его как недоступный (visited[bikeIndex] = true). Добавьте Манхэттенское расстояние от этого назначения к общей текущей сумме расстояний, представленной currDistanceSum, и выполните рекурсивный вызов для следующего рабочего. 2⃣Когда рекурсивный вызов завершится, сделайте велосипед снова доступным, установив visited[bikeIndex] в false. Если мы назначили велосипеды всем рабочим, сравните currDistanceSum с smallestDistanceSum и обновите smallestDistanceSum соответственно. 3⃣Перед назначением любого велосипеда рабочему, проверьте, если currDistanceSum уже больше или равен smallestDistanceSum. Если это так, пропустите остальных рабочих и вернитесь. Это связано с тем, что currDistanceSum может только увеличиваться, и таким образом мы не найдем лучший результат, чем smallestDistanceSum, используя текущую комбинацию рабочих и велосипедов. 😎 Решение: class Solution { public: int smallestDistanceSum = INT_MAX; bool visited[10] = {false}; int findDistance(vector<int>& worker, vector<int>& bike) { return abs(worker[0] - bike[0]) + abs(worker[1] - bike[1]); } void minimumDistanceSum(vector<vector<int>>& workers, int workerIndex, vector<vector<int>>& bikes, int currDistanceSum) { if (workerIndex >= workers.size()) { smallestDistanceSum = min(smallestDistanceSum, currDistanceSum); return; } if (currDistanceSum >= smallestDistanceSum) { return; } for (int bikeIndex = 0; bikeIndex < bikes.size(); bikeIndex++) { if (!visited[bikeIndex]) { visited[bikeIndex] = true; minimumDistanceSum(workers, workerIndex + 1, bikes, currDistanceSum + findDistance(workers[workerIndex], bikes[bikeIndex])); visited[bikeIndex] = false; } } } int assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) { minimumDistanceSum(workers, 0, bikes, 0); return smallestDistanceSum; } }; Ставь 👍 и забирай 📚 Базу знаний
178
8
Задача: 1530. Number of Good Leaf Nodes Pairs Сложность: medium Вам дан корень бинарного дерева и целое число distance. Пара двух различных листовых узлов бинарного дерева называется хорошей, если длина кратчайшего пути между ними меньше или равна distance. Верните количество хороших пар листовых узлов в дереве. Пример: Input: root = [1,2,3,null,4], distance = 3 Output: 1 Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair. 👨‍💻 Алгоритм: 1⃣Инициализируйте список смежности для преобразования дерева в граф и множество для хранения листовых узлов. Используйте вспомогательный метод traverseTree для обхода дерева, чтобы построить граф и найти листовые узлы. В параметрах поддерживайте текущий узел, а также родительский узел. Если текущий узел является листом, добавьте его в множество. В списке смежности добавьте текущий узел в список соседей родительского узла и наоборот. Рекурсивно вызовите traverseTree для левого и правого дочернего узла текущего узла. 2⃣Инициализируйте переменную ans для подсчета количества хороших пар листовых узлов. Итеративно переберите каждый листовой узел в множестве. Запустите BFS для текущего листового узла. BFS можно прервать досрочно, как только будут обнаружены все узлы, находящиеся на расстоянии от текущего листового узла. Увеличьте ans для каждого листового узла, найденного в каждом запуске BFS. 3⃣Верните ans / 2. Мы считаем каждую пару дважды, поэтому нужно разделить на 2, чтобы получить фактическое количество. 😎 Решение: class Solution { public: int countPairs(TreeNode* root, int distance) { unordered_map<TreeNode*, vector<TreeNode*>> graph; unordered_set<TreeNode*> leafNodes; traverseTree(root, nullptr, graph, leafNodes); int ans = 0; for (auto leaf : leafNodes) { queue<TreeNode*> bfsQueue; unordered_set<TreeNode*> seen; bfsQueue.push(leaf); seen.insert(leaf); for (int i = 0; i <= distance; ++i) { int size = bfsQueue.size(); for (int j = 0; j < size; ++j) { TreeNode* currNode = bfsQueue.front(); bfsQueue.pop(); if (leafNodes.count(currNode) && currNode != leaf) { ++ans; } for (auto neighbor : graph[currNode]) { if (!seen.count(neighbor)) { bfsQueue.push(neighbor); seen.insert(neighbor); } } } } } return ans / 2; } private: void traverseTree(TreeNode* currNode, TreeNode* prevNode, unordered_map<TreeNode*, vector<TreeNode*>>& graph, unordered_set<TreeNode*>& leafNodes) { if (!currNode) { return; } if (!currNode->left && !currNode->right) { leafNodes.insert(currNode); } if (prevNode) { graph[prevNode].push_back(currNode); graph[currNode].push_back(prevNode); } traverseTree(currNode->left, currNode, graph, leafNodes); traverseTree(currNode->right, currNode, graph, leafNodes); } }; Ставь 👍 и забирай 📚 Базу знаний
179
9
Задача: 1429. First Unique Number Сложность: medium У вас есть очередь целых чисел, необходимо извлечь первый уникальный элемент из очереди. Реализуйте класс FirstUnique: - FirstUnique(int[] nums) Инициализирует объект числами в очереди. - int showFirstUnique() возвращает значение первого уникального элемента в очереди и возвращает -1, если такого элемента нет. - void add(int value) вставляет значение в очередь. Пример: Input: ["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"] [[[2,3,5]],[],[5],[],[2],[],[3],[]] Output: [null,2,null,2,null,3,null,-1] Explanation: FirstUnique firstUnique = new FirstUnique([2,3,5]); firstUnique.showFirstUnique(); // return 2 firstUnique.add(5); // the queue is now [2,3,5,5] firstUnique.showFirstUnique(); // return 2 firstUnique.add(2); // the queue is now [2,3,5,5,2] firstUnique.showFirstUnique(); // return 3 firstUnique.add(3); // the queue is now [2,3,5,5,2,3] firstUnique.showFirstUnique(); // return -1 👨‍💻 Алгоритм: 1⃣Инициализируйте объект FirstUnique с числами в очереди, добавляя их в структуру данных для отслеживания уникальности и порядка. 2⃣Метод showFirstUnique возвращает значение первого уникального элемента в очереди, если таковой существует, или -1, если уникальных элементов нет. 3⃣Метод add добавляет новое значение в очередь. Если значение уже было добавлено ранее, обновляет его статус уникальности и удаляет его из множества уникальных значений, если оно больше не уникально. 😎 Решение: #include <unordered_map> #include <unordered_set> #include <list> class FirstUnique { public: FirstUnique(vector<int>& nums) { for (int num : nums) { add(num); } } int showFirstUnique() { if (!queue.empty()) { return queue.front(); } return -1; } void add(int value) { if (isUnique.find(value) == isUnique.end()) { isUnique[value] = true; queue.push_back(value); } else if (isUnique[value]) { isUnique[value] = false; queue.remove(value); } } private: list<int> queue; unordered_map<int, bool> isUnique; }; Ставь 👍 и забирай 📚 Базу знаний
206
10
Задача: 728. Self Dividing Numbers Сложность: hard Например, 128 является саморазделяющимся числом, потому что 128 % 1 == 0, 128 % 2 == 0 и 128 % 8 == 0. Саморазделяющееся число не может содержать цифру ноль. Если даны два целых числа left и right, верните список всех саморазделяющихся чисел в диапазоне [left, right]. Пример: Input: left = 1, right = 22 Output: [1,2,3,4,5,6,7,8,9,11,12,15,22] 👨‍💻 Алгоритм: 1⃣Переберите все числа в диапазоне от left до right. 2⃣Для каждого числа проверьте, является ли оно саморазделяющимся: Разделите число на его цифры. Убедитесь, что ни одна цифра не равна нулю и число делится на каждую из своих цифр без остатка. 3⃣Добавьте саморазделяющиеся числа в результативный список и верните его. 😎 Решение: #include <vector> using namespace std; class Solution { public: vector<int> selfDividingNumbers(int left, int right) { vector<int> result; for (int num = left; num <= right; num++) { if (isSelfDividing(num)) { result.push_back(num); } } return result; } private: bool isSelfDividing(int num) { int n = num; while (n > 0) { int digit = n % 10; if (digit == 0 || num % digit != 0) { return false; } n /= 10; } return true; } }; Ставь 👍 и забирай 📚 Базу знаний
216
11
Задача: 722. Remove Comments Сложность: medium Дана программа на C++, удалите из нее комментарии. Исходный текст программы представляет собой массив строк source, где source[i] - это i-я строка исходного кода. Это результат разбиения исходной строки исходного кода символом новой строки '\n'. В C++ существует два типа комментариев: строчные и блочные. Строка "//" обозначает строчный комментарий, который означает, что он и остальные символы справа от него в той же строке должны игнорироваться. Строка "/*" обозначает блочный комментарий, который означает, что все символы до следующего (не перекрывающегося) вхождения "*/" должны игнорироваться. (Здесь вхождения происходят в порядке чтения: строка за строкой слева направо.) Чтобы было понятно, строка "/*/" еще не завершает блочный комментарий, так как окончание будет перекрывать начало. Первый эффективный комментарий имеет приоритет над остальными. Например, если строка "//" встречается в блочном комментарии, она игнорируется. Аналогично, если строка "/*" встречается в строчном или блочном комментарии, она также игнорируется. Если после удаления комментариев определенная строка кода оказывается пустой, вы не должны выводить эту строку: каждая строка в списке ответов будет непустой. Пример: Input: source = ["/*Test program */", "int main()", "{ ", " // variable declaration ", "int a, b, c;", "/* This is a test", " multiline ", " comment for ", " testing */", "a = b + c;", "}"] Output: ["int main()","{ "," ","int a, b, c;","a = b + c;","}"] 👨‍💻 Алгоритм: 1⃣Создайте строку buffer для хранения текущей строки кода без комментариев и флаг inBlock для отслеживания, находимся ли мы внутри блочного комментария. 2⃣Пройдите по каждой строке source и по каждому символу в этой строке, обрабатывая комментарии: Если встречен блочный комментарий /*, установите флаг inBlock и пропустите символы до */. Если встречен строчный комментарий //, прекратите обработку текущей строки. Если не находимся внутри комментария, добавьте символ в buffer. 3⃣После обработки всех строк добавьте непустые строки из buffer в результат. 😎 Решение: vector<string> removeComments(vector<string>& source) { bool inBlock = false; string buffer; vector<string> result; for (const string& line : source) { int i = 0; if (!inBlock) buffer.clear(); while (i < line.size()) { if (!inBlock && i + 1 < line.size() && line[i] == '/' && line[i + 1] == '*') { inBlock = true; i++; } else if (inBlock && i + 1 < line.size() && line[i] == '*' && line[i + 1] == '/') { inBlock = false; i++; } else if (!inBlock && i + 1 < line.size() && line[i] == '/' && line[i + 1] == '/') { break; } else if (!inBlock) { buffer.push_back(line[i]); } i++; } if (!inBlock && !buffer.empty()) { result.push_back(buffer); } } return result; } Ставь 👍 и забирай 📚 Базу знаний
268
12
Задача: 1254. Number of Closed Islands Сложность: medium Дана двумерная сетка, состоящая из 0 (земля) и 1 (вода).Остров - это максимальная 4-направленно связная группа из 0s, а закрытый остров - это остров, полностью (слева, сверху, справа, снизу) окруженный 1s. Верните количество закрытых островов. Пример: Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]] Output: 2 👨‍💻 Алгоритм: 1⃣Пройдите по границам сетки и с помощью поиска в глубину (DFS) или поиска в ширину (BFS) замените все связанные земли (0) на воду (1). 2⃣Пройдите по всей сетке, используя DFS или BFS для поиска всех оставшихся островов (групп 0) 3⃣Подсчитайте количество таких островов. 😎 Решение: class Solution { public: int closedIsland(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j] == 0) { dfs(grid, i, j); } } } int count = 0; for (int i = 1; i < m - 1; i++) { for (int j = 1; j < n - 1; j++) { if (grid[i][j] == 0) { dfs(grid, i, j); count++; } } } return count; } private: void dfs(vector<vector<int>>& grid, int x, int y) { if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] == 1) { return; } grid[x][y] = 1; dfs(grid, x + 1, y); dfs(grid, x - 1, y); dfs(grid, x, y + 1); dfs(grid, x, y - 1); } }; Ставь 👍 и забирай 📚 Базу знаний
310
13
🔥 Скрытые вакансии с удаленной работой для C/C++ разработчика, которые нигде больше не публикуются. Напрямую от компаний, с
🔥 Скрытые вакансии с удаленной работой для C/C++ разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров. 🔹 C/C++ Jobs | Вакансии 🔸 Все каналы с вакансиями
292
14
Задача: 1426. Counting Elements Сложность: easy Дан целочисленный массив arr, посчитайте, сколько элементов x в нем есть таких, что x + 1 также находится в arr. Если в arr есть дубликаты, считайте их отдельно. Пример: Input: arr = [1,2,3] Output: 2 Explanation: 1 and 2 are counted cause 2 and 3 are in arr. 👨‍💻 Алгоритм: 1⃣Создайте вспомогательную функцию для проверки, содержится ли элемент в массиве. 2⃣Итерируйте по каждому элементу массива и используйте вспомогательную функцию для проверки, содержится ли элемент x + 1 в массиве. 3⃣Увеличьте счетчик, если x + 1 найден, и верните значение счетчика. 😎 Решение: class Solution { public: int countElements(vector<int>& arr) { int count = 0; for (int x : arr) { if (integerInArray(arr, x + 1)) { count++; } } return count; } bool integerInArray(vector<int>& arr, int target) { for (int x : arr) { if (x == target) { return true; } } return false; } }; Ставь 👍 и забирай 📚 Базу знаний
307
15
Задача: 684. Redundant Connection Сложность: medium В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов. Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе. Верните ребро, которое можно удалить, чтобы результирующий граф стал деревом из n узлов. Если существует несколько ответов, верните тот, который встречается последним в исходных данных. Пример: Input: edges = [[1,2],[1,3],[2,3]] Output: [2,3] 👨‍💻 Алгоритм: 1⃣Для каждого ребра (u, v) создайте представление графа с использованием списка смежности. Это позволит легко выполнять обход в глубину (DFS) для проверки соединений между узлами. 2⃣Выполняйте обход в глубину для каждого ребра, временно удаляя его из графа. Проверьте, можно ли соединить узлы u и v с помощью обхода в глубину. Если узлы остаются соединенными, значит, это ребро является дублирующимся. 3⃣Верните дублирующееся ребро, которое встречается последним в исходных данных. Это обеспечит корректность решения, даже если существует несколько ответов. 😎 Решение: #include <vector> #include <unordered_set> #include <array> class Solution { public: std::unordered_set<int> seen; static const int MAX_EDGE_VAL = 1000; std::vector<int> findRedundantConnection(std::vector<std::vector<int>>& edges) { std::array<std::vector<int>, MAX_EDGE_VAL + 1> graph; for (auto& edge : edges) { seen.clear(); if (!graph[edge[0]].empty() && !graph[edge[1]].empty() && dfs(graph, edge[0], edge[1])) { return edge; } graph[edge[0]].push_back(edge[1]); graph[edge[1]].push_back(edge[0]); } throw std::runtime_error("No redundant connection found"); } bool dfs(const std::array<std::vector<int>, MAX_EDGE_VAL + 1>& graph, int source, int target) { if (!seen.count(source)) { seen.insert(source); if (source == target) return true; for (int nei : graph[source]) { if (dfs(graph, nei, target)) return true; } } return false; } }; Ставь 👍 и забирай 📚 Базу знаний
316
16
🚨 40 минут Пожизненный PRO по цене года закрывается прямо сейчас. Это последнее напоминание. 👉 https://easyoffer.ru/pro
🚨 40 минут Пожизненный PRO по цене года закрывается прямо сейчас. Это последнее напоминание. 👉 https://easyoffer.ru/pro
104
17
🎃 3 часа до полуночи... Ровно в 00:00 предложение исчезнет, как призрак на рассвете 👻 Последний шанс забрать PRO навсегда п
🎃 3 часа до полуночи... Ровно в 00:00 предложение исчезнет, как призрак на рассвете 👻 Последний шанс забрать PRO навсегда по цене одного года. Без продлений и без воскрешений. Если откладывал — не дай этой возможности стать твоим ночным кошмаром 🦇 👉 https://easyoffer.ru/pro
110
18
Задача: 424. Longest Repeating Character Replacement Сложность: medium Вам дана строка s и целое число k. Вы можете выбрать любой символ строки и заменить его на любой другой заглавный английский символ. Вы можете выполнить эту операцию не более k раз. Верните длину самой длинной подстроки, содержащей одну и ту же букву, которую можно получить после выполнения вышеуказанных операций. Пример: Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa. 👨‍💻 Алгоритм: 1⃣Определите диапазон поиска. Минимальная длина подстроки с одинаковыми символами всегда равна 1 (назовем ее min), а максимальная длина подстроки может быть равна длине данной строки (назовем ее max). Ответ будет лежать в диапазоне [min, max] (включительно). 2⃣Инициализируйте две переменные lo и hi для бинарного поиска. lo всегда указывает на длину допустимой строки, а hi - на недопустимую длину. Изначально lo равно 1, а hi равно max+1. 3⃣Выполните бинарный поиск, чтобы найти максимальное значение lo, которое представляет самую длинную допустимую подстроку. В конце lo будет содержать ответ, а hi будет на единицу больше lo. 😎 Решение: class Solution { public: int characterReplacement(string s, int k) { int lo = 1; int hi = s.size() + 1; while (lo + 1 < hi) { int mid = lo + (hi - lo) / 2; if (canMakeValidSubstring(s, mid, k)) { lo = mid; } else { hi = mid; } } return lo; } private: bool canMakeValidSubstring(const string& s, int substringLength, int k) { vector<int> freqMap(26, 0); int maxFrequency = 0; int start = 0; for (int end = 0; end < s.size(); ++end) { freqMap[s[end] - 'A']++; if (end + 1 - start > substringLength) { freqMap[s[start] - 'A']--; start++; } maxFrequency = max(maxFrequency, freqMap[s[end] - 'A']); if (substringLength - maxFrequency <= k) { return true; } } return false; } }; Ставь 👍 и забирай 📚 Базу знаний
339
19
🕯 Страшилка на ночь Год спустя. Финальный этап собеседования. В комнате становится холодно. Интервьюер медленно наклоняется
🕯 Страшилка на ночь Год спустя. Финальный этап собеседования. В комнате становится холодно. Интервьюер медленно наклоняется и шепчет: «Почему вы ушли с прошлого места работы?» Ты открываешь easyoffer, а там… «Ваша подписка истекла» 💀 Чтобы эта история не стала твоей, забери пожизненный PRO по цене одного года. База собесов, эталонные ответы, автоотклики, тренажёры и всё, что появится дальше, остаются с тобой навсегда. ⏳ Осталось 7 часов. В полночь предложение исчезнет. 👉 https://easyoffer.ru/pro
132
20
⏳ Сегодня последний день Платишь один раз и забираешь весь easyoffer навсегда, вместе со всеми будущими фичами проекта. Никак
⏳ Сегодня последний день Платишь один раз и забираешь весь easyoffer навсегда, вместе со всеми будущими фичами проекта. Никаких ежегодных продлений, только ты, твой оффер и мешок конфет 🍭 🎃 Завтра цена вернётся к обычной, и такого угощения уже не будет. 👉 https://easyoffer.ru/pro
148