متاح الآن! بحث تيليغرام 2025 — أهم رؤى العام 
C/C++ | LeetCode
الذهاب إلى القناة على Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+zYofcX2VLTM3MGMy Вопросы собесов t.me/+BTbqlW1VbIFmYmVi Вакансии t.me/+za2mJYs4riAzMzFi
إظهار المزيد3 262
المشتركون
-124 ساعات
-37 أيام
لا توجد بيانات30 أيام
أرشيف المشاركات
3 262
Задача: 716. Max Stack
Сложность: hard
Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова.
Пример:
Input ["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"] [[], [5], [1], [5], [], [], [], [], [], []] Output [null, null, null, null, 5, 5, 1, 5, 1, 5]👨💻 Алгоритм: 1⃣Инициализируйте MaxStack с двумя стеками: один для хранения всех элементов, другой для отслеживания максимальных элементов. 2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека. 3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно. 😎 Решение:
class MaxStack {
public:
MaxStack() {}
void push(int x) {
stack.push(x);
if (maxStack.empty() || x >= maxStack.top()) {
maxStack.push(x);
}
}
int pop() {
int x = stack.top();
stack.pop();
if (x == maxStack.top()) {
maxStack.pop();
}
return x;
}
int top() {
return stack.top();
}
int peekMax() {
return maxStack.top();
}
int popMax() {
int maxVal = maxStack.top();
maxStack.pop();
stack<int> buffer;
while (stack.top() != maxVal) {
buffer.push(stack.top());
stack.pop();
}
stack.pop();
while (!buffer.empty()) {
push(buffer.top());
buffer.pop();
}
return maxVal;
}
private:
stack<int> stack;
stack<int> maxStack;
};3 262
Задача: 1022. Sum of Root To Leaf Binary Numbers
Сложность: easy
Вам дан корень двоичного дерева, в котором каждый узел имеет значение 0 или 1. Каждый путь от корня к листьям представляет собой двоичное число, начиная со старшего бита. Например, если путь 0 -> 1 -> 1 -> 0 -> 1, то в двоичном виде это может представлять 01101, что равно 13. Для всех листьев дерева рассмотрите числа, представленные путем от корня к этому листу. Верните сумму этих чисел. Тестовые примеры генерируются таким образом, чтобы ответ помещался в 32-битовое целое число.
Пример:
Input: root = [1,0,1,0,1,0,1] Output: 22👨💻 Алгоритм: 1⃣Рекурсивный обход дерева: Используйте функцию DFS (поиск в глубину) для обхода дерева, начиная от корня. Передавайте текущее значение числа по пути как параметр. 2⃣Анализ текущего узла: Если узел является листом (не имеет потомков), добавьте текущее значение числа к общей сумме. Если узел не является листом, рекурсивно вызовите функцию DFS для левого и правого дочерних узлов, обновляя текущее значение числа. 3⃣Возврат результата: После завершения обхода верните общую сумму чисел, представленных путями от корня к листьям. 😎 Решение:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int sumRootToLeaf(TreeNode* root) {
return dfs(root, 0);
}
private:
int dfs(TreeNode* node, int current_value) {
if (!node) return 0;
current_value = (current_value << 1) | node->val;
if (!node->left && !node->right) return current_value;
return dfs(node->left, current_value) + dfs(node->right, current_value);
}
};3 262
Задача: 1012. Numbers With Repeated Digits
Сложность: hard
Задав целое число n, верните количество положительных целых чисел в диапазоне [1, n], у которых хотя бы одна цифра повторяется.
Пример:
Input: n = 20 Output: 1👨💻 Алгоритм: 1⃣Вычисление всех чисел с уникальными цифрами: Найдите количество чисел в диапазоне [1, n], у которых все цифры уникальны. Для этого используйте перебор всех чисел и проверку уникальности цифр. 2⃣Вычисление всех чисел в диапазоне [1, n]: Это значение равно n, поскольку это количество всех чисел от 1 до n включительно. 3⃣Вычисление результата: Вычтите количество чисел с уникальными цифрами из общего количества чисел, чтобы получить количество чисел с повторяющимися цифрами. 😎 Решение:
class Solution {
public:
int numDupDigitsAtMostN(int n) {
return n - countUniqueDigitNumbers(n);
}
private:
int countUniqueDigitNumbers(int x) {
string s = to_string(x);
int n = s.size();
int res = 0;
for (int i = 1; i < n; ++i) {
res += 9 * permutation(9, i - 1);
}
unordered_set<int> used;
for (int i = 0; i < n; ++i) {
for (int j = (i == 0 ? 1 : 0); j < s[i] - '0'; ++j) {
if (used.find(j) == used.end()) {
res += permutation(9 - i, n - i - 1);
}
}
if (used.find(s[i] - '0') != used.end()) {
break;
}
used.insert(s[i] - '0');
}
if (used.size() == n) {
res += 1;
}
return res;
}
int permutation(int m, int n) {
return n == 0 ? 1 : permutation(m, n - 1) * (m - n + 1);
}
};3 262
Задача: 929. Unique Email Addresses
Сложность: easy
Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.
Пример:
Input: emails = ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"] Output: 2👨💻 Алгоритм: 1⃣Создать множество для хранения уникальных обработанных адресов электронной почты. 2⃣Для каждого адреса в emails: Разделить адрес на локальное и доменное имя по символу '@'. Обработать локальное имя: Удалить все точки '.'. Обрезать часть после символа '+'. Объединить обработанное локальное имя и доменное имя. Добавить результат в множество уникальных адресов. 3⃣Вернуть количество уникальных адресов в множестве. 😎 Решение:
class Solution {
public int numUniqueEmails(String[] emails) {
Set<String> uniqueEmails = new HashSet<>();
for (String email : emails) {
String[] parts = email.split("@");
String local = parts[0].split("\\+")[0].replace(".", "");
uniqueEmails.add(local + "@" + parts[1]);
}
return uniqueEmails.size();
}
}3 262
Задача: 1110. Delete Nodes And Return Forest
Сложность: medium
Дан корень бинарного дерева, каждый узел в дереве имеет уникальное значение.
После удаления всех узлов со значением из to_delete, остаётся лес (несвязное объединение деревьев).
Верните корни деревьев в оставшемся лесу. Вы можете вернуть результат в любом порядке.
Пример:
Input: root = [1,2,3,4,5,6,7], to_delete = [3,5] Output: [[1,2,null,4],[6],[7]]👨💻 Алгоритм: 1⃣Инициализация: Преобразуйте массив to_delete в множество toDeleteSet для эффективного поиска. Создайте пустой список forest для хранения корней деревьев в результирующем лесу. 2⃣Рекурсивный обход: Выполните обход дерева в порядке пост-ордера, чтобы сначала обработать все дочерние узлы перед текущим узлом (node): - рекурсивно вызовите processNode для левого и правого дочерних узлов node и обновите левого и правого дочернего узла с возвращаемым значением. 3⃣Оценка узла: Проверьте, нужно ли удалить текущий узел, проверив, существует ли его значение в toDeleteSet. Если узел нужно удалить: - если у узла есть левый или правый дочерний узел, добавьте их в forest. - верните null для его родителя, чтобы эффективно удалить текущий узел, не подключая его обратно к родительскому узлу. Если узел не нужно удалять, верните сам узел. 😎 Решение:
class Solution {
fun delNodes(root: TreeNode?, to_delete: IntArray): List<TreeNode?> {
val toDeleteSet = to_delete.toSet()
val forest = mutableListOf<TreeNode?>()
fun processNode(node: TreeNode?): TreeNode? {
if (node == null) return null
node.left = processNode(node.left)
node.right = processNode(node.right)
if (toDeleteSet.contains(node.`val`)) {
node.left?.let { forest.add(it) }
node.right?.let { forest.add(it) }
return null
}
return node
}
val root = processNode(root)
if (root != null) forest.add(root)
return forest
}
}3 262
Задача: 977. Squares of a Sorted Array
Сложность: easy
Дан целочисленный массив nums, отсортированный в неубывающем порядке. Верните массив квадратов каждого числа, отсортированный в неубывающем порядке.
Пример:
Input: nums = [-4,-1,0,3,10] Output: [0,1,9,16,100] Explanation: After squaring, the array becomes [16,1,0,9,100]. After sorting, it becomes [0,1,9,16,100].👨💻 Алгоритм: 1⃣Создайте массив квадратов каждого элемента. 2⃣Отсортируйте массив квадратов. 3⃣Верните отсортированный массив квадратов. 😎 Решение:
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
size_t n = nums.size();
vector<int> ans(n);
for (size_t i = 0; i < n; i++) {
ans[i] = nums[i] * nums[i];
}
sort(ans.begin(), ans.end());
return ans;
}
};3 262
C++ разработчики в 2ГИС
Сейчас открыто две вакансии в разные команды:
— Middle C++ Developer в команду Transport Core
Делаем транспортный движок 2ГИС: маршруты, графы, расчёты и highload-обработку данных.
— Team Lead C++ в команду 3D Карты
Ищем сильного C++ разработчика на роль играющего тренера: часть времени — разработка, остальное — управление небольшой командой, техрешения и развитие процессов.
Важно: опыт именно в графике не обязателен. Если ты сильный плюсовик и хочешь попробовать себя в 3D-направлении — откликайся!
Что общего:
— современный C++
— сложные инженерные задачи
— большие объёмы данных
— сильные команды без лишней бюрократии
Можно удалённо
Вакансии:
Middle C++ Developer — Transport Core
Team Lead C++ — 3D Карты
Другие инженерные инсайты от 2ГИС → в Telegram-канале RnD
3 262
Главный навык на ближайшие годы — ВАЙБ-КОДИНГ
ИИ уже пишет код, чинит баги, генерирует тесты, документацию и помогает запускать продукты быстрее, чем это делали классические команды разработки. И это уже не "будущее когда-нибудь", а реальность, которая меняет рынок уже сегодня
И те, кто научится вайбкодить сейчас, будут увереннее конкурировать на рынке и зарабатывать больше тех, кто по-прежнему делает всё вручную.
Стартовать с нуля поможет канал Вайб-кодинг. Там ребята круглосуточно мониторят более 320 российских и зарубежных источников и публикуют только главное: релизы, инструменты, гайды, курсы и практические кейсы.
Подписывайтесь, нас уже 30 тысяч: @vibecoding_tg
3 262
Задача: 911. Online Election
Сложность: medium
Вам даны два целочисленных массива persons и times. На выборах i-й голос был отдан за person[i] в момент времени times[i]. Для каждого запроса в момент времени t найдите человека, который лидировал на выборах в момент времени t. Голоса, отданные в момент времени t, будут учитываться в нашем запросе. В случае равенства голосов побеждает тот, кто проголосовал последним (среди равных кандидатов). Реализация класса TopVotedCandidate: TopVotedCandidate(int[] persons, int[] times) Инициализирует объект с массивами persons и times. int q(int t) Возвращает номер человека, который лидировал на выборах в момент времени t в соответствии с указанными правилами.
Пример:
Input ["TopVotedCandidate", "q", "q", "q", "q", "q", "q"] [[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]] Output [null, 0, 1, 1, 0, 0, 1]👨💻 Алгоритм: 1⃣Использовать два массива для хранения лиц и времени голосования. 2⃣Поддерживать текущий счет для каждого кандидата и текущего лидера на момент времени. 3⃣На каждый запрос времени t, найти наибольший индекс времени, который не превышает t, и вернуть лидера на этот момент времени. 😎 Решение:
class TopVotedCandidate {
public:
TopVotedCandidate(vector<int>& persons, vector<int>& times) {
this->times = times;
unordered_map<int, int> counts;
int leader = -1;
for (int person : persons) {
counts[person]++;
if (counts[person] >= counts[leader]) {
leader = person;
}
leaders.push_back(leader);
}
}
int q(int t) {
auto it = upper_bound(times.begin(), times.end(), t);
return leaders[it - times.begin() - 1];
}
private:
vector<int> times;
vector<int> leaders;
};3 262
Задача: 842. Split Array into Fibonacci Sequence
Сложность: medium
Вам дана строка цифр num, такая как "123456579". Мы можем разделить её на последовательность, похожую на Фибоначчи [123, 456, 579].
Формально, последовательность, похожая на Фибоначчи, это список f неотрицательных целых чисел, таких что:
0 <= f[i] < 2^31 (то есть каждое число помещается в 32-битный знаковый целый тип),
f.length >= 3, и
f[i] + f[i + 1] == f[i + 2] для всех 0 <= i < f.length - 2.
Обратите внимание, что при разделении строки на части каждая часть не должна иметь лишних ведущих нулей, за исключением случая, если эта часть является числом 0.
Верните любую последовательность, похожую на Фибоначчи, из строки num, или верните [] если это невозможно.
Пример:
Input: num = "1101111" Output: [11,0,11,11] Explanation: The output [110, 1, 111] would also be accepted.👨💻 Алгоритм: 1⃣Переберите все возможные начальные элементы первой и второй части последовательности, проверяя, чтобы не было ведущих нулей. 2⃣Для каждой пары начальных элементов проверяйте, можно ли продолжить последовательность Фибоначчи, создавая следующую часть, которая должна быть суммой двух предыдущих частей. 3⃣Если последовательность Фибоначчи найдена, верните её, иначе продолжайте перебор. 😎 Решение:
class Solution {
public:
vector<int> splitIntoFibonacci(string S) {
int N = S.length();
for (int i = 0; i < min(10, N); ++i) {
if (S[0] == '0' && i > 0) break;
long a = stol(S.substr(0, i + 1));
if (a >= INT_MAX) break;
for (int j = i + 1; j < min(i + 10, N); ++j) {
if (S[i + 1] == '0' && j > i + 1) break;
long b = stol(S.substr(i + 1, j - i));
if (b >= INT_MAX) break;
vector<int> fib = {(int)a, (int)b};
int k = j + 1;
while (k < N) {
long nxt = (long)fib[fib.size() - 2] + fib[fib.size() - 1];
if (nxt > INT_MAX) break;
string nxtS = to_string(nxt);
if (S.substr(k).find(nxtS) == 0) {
k += nxtS.length();
fib.push_back((int)nxt);
} else {
break;
}
}
if (fib.size() >= 3) return fib;
}
}
return {};
}
};3 262
Задача: 850. Rectangle Area II
Сложность: hard
Вам дан двумерный массив прямоугольников, выровненных по осям. Каждый прямоугольник[i] = [xi1, yi1, xi2, yi2] обозначает i-й прямоугольник, где (xi1, yi1) — координаты нижнего левого угла, а (xi2, yi2) — координаты верхнего правого угла.
Вычислите общую площадь, покрытую всеми прямоугольниками на плоскости. Любая площадь, покрытая двумя или более прямоугольниками, должна учитываться только один раз.
Верните общую площадь. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.class Solution {
public:
int rectangleArea(vector<vector<int>>& rectangles) {
int N = rectangles.size();
set<int> Xvals, Yvals;
for (const auto& rec : rectangles) {
Xvals.insert(rec[0]);
Xvals.insert(rec[2]);
Yvals.insert(rec[1]);
Yvals.insert(rec[3]);
}
vector<int> imapx(Xvals.begin(), Xvals.end());
vector<int> imapy(Yvals.begin(), Yvals.end());
unordered_map<int, int> mapx, mapy;
for (int i = 0; i < imapx.size(); ++i) mapx[imapx[i]] = i;
for (int i = 0; i < imapy.size(); ++i) mapy[imapy[i]] = i;
vector<vector<bool>> grid(imapx.size(), vector<bool>(imapy.size()));
for (const auto& rec : rectangles)
for (int x = mapx[rec[0]]; x < mapx[rec[2]]; ++x)
for (int y = mapy[rec[1]]; y < mapy[rec[3]]; ++y)
grid[x][y] = true;
long ans = 0;
for (int x = 0; x < grid.size(); ++x)
for (int y = 0; y < grid[0].size(); ++y)
if (grid[x][y])
ans += (long)(imapx[x + 1] - imapx[x]) * (imapy[y + 1] - imapy[y]);
ans %= 1'000'000'007;
return ans;
}
};3 262
Задача: 1101. The Earliest Moment When Everyone Become Friends
Сложность: medium
В социальной группе есть n человек, пронумерованных от 0 до n - 1. Вам дан массив logs, где logs[i] = [timestampi, xi, yi] указывает, что xi и yi станут друзьями в момент времени timestampi.
Дружба является симметричной. Это означает, что если a является другом b, то b является другом a. Также человек a знаком с человеком b, если a является другом b или a является другом кого-то, кто знаком с b.
Верните самое раннее время, когда каждый человек стал знаком с каждым другим человеком. Если такого времени не существует, верните -1.
Пример:
Input: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4 Output: 3 Explanation: At timestamp = 3, all the persons (i.e., 0, 1, 2, and 3) become friends.👨💻 Алгоритм: 1⃣Отсортируйте логи по времени в хронологическом порядке, так как в задаче не указано, отсортированы ли они. 2⃣Пройдитесь по отсортированным логам, применяя структуру данных "Объединение-Поиск": Для каждого лога объедините двух участников, упомянутых в логе, с помощью функции union(a, b). Каждое объединение добавляет новые связи между участниками. 3⃣Следите за количеством групп: Изначально каждый участник рассматривается как отдельная группа. Количество групп уменьшается с каждым полезным объединением. Момент, когда количество групп уменьшается до одной, является самым ранним моментом, когда все участники становятся связанными (друзьями). Верните этот момент времени. Если такого момента не существует, верните -1. 😎 Решение:
class UnionFind {
public:
UnionFind(int n) {
parent.resize(n);
rank.resize(n, 1);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
bool unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
return false;
}
private:
vector<int> parent;
vector<int> rank;
};
class Solution {
public:
int earliestAcq(vector<vector<int>>& logs, int n) {
sort(logs.begin(), logs.end());
UnionFind uf(n);
int groupCount = n;
for (const auto& log : logs) {
int timestamp = log[0];
int friendA = log[1];
int friendB = log[2];
if (uf.unionSets(friendA, friendB)) {
groupCount--;
}
if (groupCount == 1) {
return timestamp;
}
}
return -1;
}
};3 262
Задача: 1021. Remove Outermost Parentheses
Сложность: easy
Например, "", "()", "(" + A + ")" или A + B, где A и B - допустимые строки со скобками, а + означает объединение строк. Все допустимые строки со скобками - "", "()", "(())()" и "(()(())".
Допустимая строка со скобками s является примитивной, если она непустая и не существует способа разбить ее на s = A + B, причем A и B - непустые допустимые строки со скобками. Если дана допустимая строка со скобками s, рассмотрим ее примитивное разложение: s = P1 + P2 + ... + Pk, где Pi - примитивные допустимые строки со скобками. Верните s после удаления крайних скобок из каждой примитивной строки в примитивном разложении s.
Пример:
Input: s = "(()())(())" Output: "()()()"👨💻 Алгоритм: 1⃣Инициализация переменных: Создайте пустую строку для хранения результата. Используйте счетчик для отслеживания уровня вложенности скобок.. 2⃣Обработка строки: Итерируйте по каждому символу строки. Если встречаете (, увеличивайте счетчик уровня вложенности. Если уровень вложенности больше 1, добавьте ( в результат. Если встречаете ), уменьшайте счетчик уровня вложенности. Если уровень вложенности больше 0 перед уменьшением, добавьте ) в результат. 3⃣Возврат результата: Верните результат, содержащий строку без крайних скобок из каждой примитивной строки. 😎 Решение:
class Solution {
public:
string removeOuterParentheses(string s) {
string result;
int level = 0;
for (char c : s) {
if (c == '(') {
if (level > 0) {
result += c;
}
level++;
} else {
level--;
if (level > 0) {
result += c;
}
}
}
return result;
}
};3 262
Задача: 1286. Iterator for Combination
Сложность: medium
Создайте класс CombinationIterator:
CombinationIterator(string characters, int combinationLength) Инициализирует объект строкой characters, содержащей отсортированные различные строчные буквы английского алфавита, и числом combinationLength в качестве аргументов.
next() Возвращает следующую комбинацию длины combinationLength в лексикографическом порядке.
hasNext() Возвращает true, если и только если существует следующая комбинация.
Пример:
Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]
Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next(); // return "ab"
itr.hasNext(); // return True
itr.next(); // return "ac"
itr.hasNext(); // return True
itr.next(); // return "bc"
itr.hasNext(); // return False
👨💻 Алгоритм:
1⃣Сгенерируйте все возможные бинарные битовые маски длины n: от 0 до 2^n - 1.
2⃣Используйте битовые маски с k установленными битами для генерации комбинаций из k элементов. Если n - 1 - j-й бит установлен в битовой маске, это указывает на присутствие символа characters[j] в комбинации и наоборот.
3⃣Теперь у вас есть все заранее вычисленные комбинации. Извлекайте их одну за другой по каждому запросу.
😎 Решение:
#include <vector>
#include <string>
class CombinationIterator {
private:
std::vector<std::string> combinations;
public:
CombinationIterator(std::string characters, int combinationLength) {
int n = characters.size();
int k = combinationLength;
for (int bitmask = 0; bitmask < (1 << n); ++bitmask) {
if (__builtin_popcount(bitmask) == k) {
std::string curr;
for (int j = 0; j < n; ++j) {
if (bitmask & (1 << (n - j - 1))) {
curr.push_back(characters[j]);
}
}
combinations.push_back(curr);
}
}
}
std::string next() {
std::string res = combinations.back();
combinations.pop_back();
return res;
}
bool hasNext() {
return !combinations.empty();
}
};3 262
Задача: 1269. Number of Ways to Stay in the Same Place After Some Steps
Сложность: hard
У вас есть указатель на индекс 0 в массиве размера arrLen. На каждом шаге вы можете перемещаться на 1 позицию влево, на 1 позицию вправо в массиве или оставаться на том же месте (указатель ни в коем случае не должен находиться за пределами массива). Учитывая два целых числа steps и arrLen, верните количество способов, при которых указатель все еще находится на индексе 0 после ровно шагов. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Пример:
Input: steps = 3, arrLen = 2 Output: 4👨💻 Алгоритм: 1⃣Инициализируйте массив для хранения количества способов достижения каждого индекса на каждом шаге. 2⃣Используйте динамическое программирование для подсчета количества способов достижения каждого индекса на каждом шаге. 3⃣Используйте динамическое программирование для подсчета количества способов достижения каждого индекса на каждом шаге. 😎 Решение:
class Solution {
public:
int numWays(int steps, int arrLen) {
const int mod = 1e9 + 7;
int max_pos = min(arrLen - 1, steps);
vector<int> dp(max_pos + 1, 0);
dp[0] = 1;
for (int step = 0; step < steps; ++step) {
vector<int> new_dp(max_pos + 1, 0);
for (int i = 0; i <= max_pos; ++i) {
new_dp[i] = dp[i] % mod;
if (i > 0) new_dp[i] = (new_dp[i] + dp[i - 1]) % mod;
if (i < max_pos) new_dp[i] = (new_dp[i] + dp[i + 1]) % mod;
}
dp = new_dp;
}
return dp[0];
}
};3 262
Задача: 1512. Number of Good Pairs
Сложность: easy
Дан массив целых чисел nums, верните количество хороших пар.
Пара (i, j) называется хорошей, если nums[i] == nums[j] и i < j.
Пример:
Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.class Solution {
public:
int numIdenticalPairs(vector<int>& nums) {
int ans = 0;
for (int i = 0; i < nums.size(); i++) {
for (int j = i + 1; j < nums.size(); j++) {
if (nums[i] == nums[j]) {
ans++;
}
}
}
return ans;
}
};3 262
Задача: 339. Nested List Weight Sum
Сложность: medium
Вам дан вложенный список целых чисел nestedList. Каждый элемент либо целое число, либо список, элементы которого также могут быть целыми числами или другими списками.
Глубина целого числа — это количество списков, в которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значения каждого целого числа, установленные в его глубину.
Верните сумму каждого целого числа в nestedList, умноженного на его глубину.
Пример:
Input: nestedList = [1,[4,[6]]] Output: 27 Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.👨💻 Алгоритм: 1⃣Инициализация и вызов рекурсивной функции: Создайте основную функцию, которая принимает вложенный список и вызывает вспомогательную рекурсивную функцию с начальной глубиной 1. 2⃣Рекурсивное исследование списка: В вспомогательной функции пройдите по каждому элементу списка. Если элемент является целым числом, добавьте его значение, умноженное на текущую глубину, к общей сумме. Если элемент является списком, вызовите вспомогательную функцию рекурсивно с увеличенной глубиной. 3⃣Возврат результата: Возвращайте общую сумму на каждом уровне рекурсии. Основная функция возвращает итоговую сумму. 😎 Решение:
class Solution {
public:
int depthSum(vector<NestedInteger>& nestedList) {
return dfs(nestedList, 1);
}
private:
int dfs(const vector<NestedInteger>& list, int depth) {
int total = 0;
for (const auto& nested : list) {
if (nested.isInteger()) {
total += nested.getInteger() * depth;
} else {
total += dfs(nested.getList(), depth + 1);
}
}
return total;
}
};3 262
Задача: 937. Reorder Data in Log Files
Сложность: medium
Вам дается массив журналов. Каждый журнал представляет собой строку слов, ограниченную пробелами, где первое слово является идентификатором. Существует два типа журналов: Буквенные журналы: Все слова (кроме идентификатора) состоят из строчных английских букв. Цифровые журналы: Все слова (кроме идентификатора) состоят из цифр. Упорядочите эти журналы таким образом: буквенные журналы идут перед всеми цифровыми журналами. Буквенные журналы сортируются лексикографически по их содержанию. Если их содержимое одинаково, то отсортируйте их лексикографически по их идентификаторам. Цифровые журналы сохраняют свой относительный порядок. Верните окончательный порядок журналов.
Пример:
Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"] Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]👨💻 Алгоритм: 1⃣Разделить журналы на буквенные и цифровые. 2⃣Отсортировать буквенные журналы: Лексикографически по содержимому. Если содержимое одинаково, отсортировать по идентификатору. Объединить отсортированные буквенные журналы и цифровые журналы в исходном порядке. 3⃣Вернуть окончательный результат. 😎 Решение:
class Solution {
public:
vector<string> reorderLogFiles(vector<string>& logs) {
auto compare = [](const string& log1, const string& log2) {
int pos1 = log1.find(' '), pos2 = log2.find(' ');
bool isDigit1 = isdigit(log1[pos1 + 1]), isDigit2 = isdigit(log2[pos2 + 1]);
if (!isDigit1 && !isDigit2) {
string s1 = log1.substr(pos1 + 1), s2 = log2.substr(pos2 + 1);
if (s1 != s2) return s1 < s2;
return log1 < log2;
}
return isDigit1 ? false : true;
};
stable_sort(logs.begin(), logs.end(), compare);
return logs;
}
};3 262
Задача: 228. Summary Ranges
Сложность: easy
Вам дан отсортированный массив уникальных целых чисел nums.
Диапазон [a,b] - это множество всех целых чисел от a до b (включительно).
Верните наименьший отсортированный список диапазонов, которые покрывают все числа в массиве точно. То есть, каждый элемент nums покрывается ровно одним из диапазонов, и не существует такого целого числа x, чтобы x находился в одном из диапазонов, но не находился в nums.
Каждый диапазон [a,b] в списке должен быть представлен в формате:
"a->b" если a != b
"a" если a == b
Пример:
Input: nums = [0,1,2,4,5,7] Output: ["0->2","4->5","7"] Explanation: The ranges are: [0,2] --> "0->2" [4,5] --> "4->5" [7,7] --> "7"👨💻 Алгоритм: 1⃣Создайте список строк ranges, который будет содержать решение задачи, и начните итерацию по всем элементам nums с указателем i = 0. Каждая итерация внешнего цикла представляет собой поиск одного диапазона. Для начала сохраните начало текущего диапазона в start = nums[i]. 2⃣Проверьте, отличается ли следующий элемент в nums на индексе i + 1 от nums[i] на 1 или больше. Если следующий элемент отличается на 1, увеличьте i на 1, чтобы включить (i+1)-й элемент в этот диапазон и продолжайте проверку следующего элемента. Продолжайте добавлять элементы в этот диапазон, пока последовательные элементы отличаются на 1, используя цикл while для выполнения этой логики. 3⃣Если следующий элемент отличается более чем на 1 или если все элементы в nums уже обработаны, проверьте, равен ли start значению nums[i]. Если start == nums[i], добавьте только start как строку в ranges, так как у нас есть только один элемент в этом диапазоне. Если start != nums[i], добавьте строку start->nums[i] в ranges. Увеличьте i на 1, чтобы начать новый диапазон. 😎 Решение:
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
vector<string> ranges;
for (int i = 0; i < nums.size(); i++) {
int start = nums[i];
while (i + 1 < nums.size() && nums[i] + 1 == nums[i + 1]) {
i++;
}
if (start != nums[i]) {
ranges.push_back(to_string(start) + "->" + to_string(nums[i]));
} else {
ranges.push_back(to_string(start));
}
}
return ranges;
}
};3 262
Задача: 1233. Remove Sub-Folders from the Filesystem
Сложность: medium
Если дан список папок folder, верните папки после удаления всех вложенных папок в этих папках. Вы можете вернуть ответ в любом порядке. Если папка[i] находится внутри другой папки[j], она называется ее вложенной папкой. Формат пути - это одна или несколько скомбинированных строк вида: '/', за которой следует одна или несколько строчных английских букв. Например, "/leetcode" и "/leetcode/problems" являются допустимыми путями, а пустая строка и "/" - нет.
Пример:
Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"] Output: ["/a","/c/d","/c/f"]👨💻 Алгоритм: 1⃣Сортировка папок: Сначала отсортируем список путей в лексикографическом порядке. Это обеспечит, что при обходе отсортированного списка мы всегда будем проверять родительскую папку перед вложенными папками. 2⃣Фильтрация вложенных папок: Будем использовать переменную для отслеживания текущей родительской папки. 3⃣При проходе по отсортированному списку проверим, является ли текущий путь вложенной папкой для отслеживаемой родительской папки. Если нет, обновим отслеживаемую папку и добавим ее в результирующий список. 😎 Решение:
class Solution {
public:
vector<string> removeSubfolders(vector<string>& folder) {
sort(folder.begin(), folder.end());
vector<string> result;
string parent = "";
for (const string& path : folder) {
if (parent.empty() || path.find(parent + "/") != 0) {
parent = path;
result.push_back(path);
}
}
return result;
}
};