C/C++ | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
نمایش بیشتر3 199
مشترکین
-124 ساعت
-57 روز
-3230 روز
در حال بارگذاری دادهها
کانالهای مشابه
ابر برچسبها
اشارات ورودی و خروجی
---
---
---
---
---
---
جذب مشترکین
نوامبر '26نوامبر '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++ 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 | 104 |
| 17 | 🎃 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 навсегда, вместе со всеми будущими фичами проекта. Никаких ежегодных продлений, только ты, твой оффер и мешок конфет 🍭
🎃 Завтра цена вернётся к обычной, и такого угощения уже не будет.
👉 https://easyoffer.ru/pro | 148 |
