fa
Feedback

فریب کلاهبرداران را نخورید! تل‌متریو این کانال‌ها را شناسایی و برچسب‌گذاری می‌کند 👉 برای مشاهده برچسب، اشتراک تهیه کنید

C/C++ | LeetCode

C/C++ | LeetCode

رفتن به کانال در Telegram

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

نمایش بیشتر
3 199
مشترکین
-124 ساعت
-57 روز
-3230 روز
آرشیو پست ها
Задача: 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;
    }
};
Ставь 👍 и забирай 📚 Базу знаний

Задача: 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};
    }
};
Ставь 👍 и забирай 📚 Базу знаний

Задача: 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;
    }
};
Ставь 👍 и забирай 📚 Базу знаний

Задача: 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;
    }
};
Ставь 👍 и забирай 📚 Базу знаний

Задача: 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;
    }
};
Ставь 👍 и забирай 📚 Базу знаний

Задача: 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;
    }
};
Ставь 👍 и забирай 📚 Базу знаний

Задача: 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;
    }
};
Ставь 👍 и забирай 📚 Базу знаний

Задача: 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);
    }
};
Ставь 👍 и забирай 📚 Базу знаний

Задача: 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;
};
Ставь 👍 и забирай 📚 Базу знаний

Задача: 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;
    }
};
Ставь 👍 и забирай 📚 Базу знаний

Задача: 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;
}
Ставь 👍 и забирай 📚 Базу знаний

Задача: 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);
    }
};
Ставь 👍 и забирай 📚 Базу знаний

🔥 Скрытые вакансии с удаленной работой для C/C++ разработчика, которые нигде больше не публикуются. Напрямую от компаний, с
🔥 Скрытые вакансии с удаленной работой для C/C++ разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров. 🔹 C/C++ Jobs | Вакансии 🔸 Все каналы с вакансиями

Задача: 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;
    }
};
Ставь 👍 и забирай 📚 Базу знаний

Задача: 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;
    }
};
Ставь 👍 и забирай 📚 Базу знаний

🚨 40 минут Пожизненный PRO по цене года закрывается прямо сейчас. Это последнее напоминание. 👉 https://easyoffer.ru/pro
🚨 40 минут Пожизненный PRO по цене года закрывается прямо сейчас. Это последнее напоминание. 👉 https://easyoffer.ru/pro

🎃 3 часа до полуночи... Ровно в 00:00 предложение исчезнет, как призрак на рассвете 👻 Последний шанс забрать PRO навсегда п
🎃 3 часа до полуночи... Ровно в 00:00 предложение исчезнет, как призрак на рассвете 👻 Последний шанс забрать PRO навсегда по цене одного года. Без продлений и без воскрешений. Если откладывал — не дай этой возможности стать твоим ночным кошмаром 🦇 👉 https://easyoffer.ru/pro

Задача: 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;
    }
};
Ставь 👍 и забирай 📚 Базу знаний

🕯 Страшилка на ночь Год спустя. Финальный этап собеседования. В комнате становится холодно. Интервьюер медленно наклоняется
🕯 Страшилка на ночь Год спустя. Финальный этап собеседования. В комнате становится холодно. Интервьюер медленно наклоняется и шепчет: «Почему вы ушли с прошлого места работы?» Ты открываешь easyoffer, а там… «Ваша подписка истекла» 💀 Чтобы эта история не стала твоей, забери пожизненный PRO по цене одного года. База собесов, эталонные ответы, автоотклики, тренажёры и всё, что появится дальше, остаются с тобой навсегда. ⏳ Осталось 7 часов. В полночь предложение исчезнет. 👉 https://easyoffer.ru/pro

⏳ Сегодня последний день Платишь один раз и забираешь весь easyoffer навсегда, вместе со всеми будущими фичами проекта. Никак
⏳ Сегодня последний день Платишь один раз и забираешь весь easyoffer навсегда, вместе со всеми будущими фичами проекта. Никаких ежегодных продлений, только ты, твой оффер и мешок конфет 🍭 🎃 Завтра цена вернётся к обычной, и такого угощения уже не будет. 👉 https://easyoffer.ru/pro