C/C++ | LeetCode
Open in Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Show more
Network:3 232
Subscribers
-124 hours
-97 days
-630 days
Posts Archive
3 232
Задача: 1514. Path with Maximum Probability
Сложность: medium
Вам дан неориентированный взвешенный граф из n узлов (индексация с нуля), представленный списком ребер, где edges[i] = [a, b] является неориентированным ребром, соединяющим узлы a и b с вероятностью успешного прохождения этого ребра succProb[i].
Даны два узла start и end, найдите путь с максимальной вероятностью успеха, чтобы перейти от start к end, и верните его вероятность успеха.
Если пути от start до end не существует, верните 0. Ваш ответ будет принят, если он отличается от правильного ответа не более чем на 1e-5.
Пример:
Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<double> maxProb(n, 0.0);
maxProb[start] = 1.0;
for (int i = 0; i < n - 1; i++) {
bool hasUpdate = false;
for (int j = 0; j < edges.size(); j++) {
int u = edges[j][0];
int v = edges[j][1];
double pathProb = succProb[j];
if (maxProb[u] * pathProb > maxProb[v]) {
maxProb[v] = maxProb[u] * pathProb;
hasUpdate = true;
}
if (maxProb[v] * pathProb > maxProb[u]) {
maxProb[u] = maxProb[v] * pathProb;
hasUpdate = true;
}
}
if (!hasUpdate) {
break;
}
}
return maxProb[end];
}
};3 232
Задача: 1425. Constrained Subsequence Sum
Сложность: hard
Дан целочисленный массив nums и целое число k, верните максимальную сумму непустой подпоследовательности этого массива, такую, что для любых двух последовательных целых чисел в подпоследовательности nums[i] и nums[j], где i < j, выполняется условие j - i <= k.
Подпоследовательность массива получается путем удаления некоторого количества элементов (может быть ноль) из массива, оставляя оставшиеся элементы в их исходном порядке.
Пример:
Input: nums = [10,2,-10,5,20], k = 2 Output: 37 Explanation: The subsequence is [10, 2, 5, 20].👨💻 Алгоритм: 1⃣Инициализируйте очередь queue и массив dp той же длины, что и nums. 2⃣Итерируйте i по индексам nums: Если i минус первый элемент queue больше k, удалите элемент из начала queue. Установите dp[i] как dp[queue.front()] + nums[i]. Если queue пуст, используйте 0 вместо dp[queue.front()]. Пока dp[queue.back()] меньше dp[i], удаляйте элементы с конца queue. Если dp[i] > 0, добавьте i в конец queue. 3⃣Верните максимальное значение в массиве dp. 😎 Решение:
class Solution {
public:
int constrainedSubsetSum(vector<int>& nums, int k) {
deque<int> queue;
vector<int> dp(nums.size());
int maxSum = INT_MIN;
for (int i = 0; i < nums.size(); ++i) {
if (!queue.empty() && i - queue.front() > k) {
queue.pop_front();
}
dp[i] = (queue.empty() ? 0 : dp[queue.front()]) + nums[i];
while (!queue.empty() && dp[queue.back()] < dp[i]) {
queue.pop_back();
}
if (dp[i] > 0) {
queue.push_back(i);
}
maxSum = max(maxSum, dp[i]);
}
return maxSum;
}
};3 232
Задача: 1005. Maximize Sum Of Array After K Negations
Сложность: easy
Учитывая целочисленный массив nums и целое число k, измените массив следующим образом: выберите индекс i и замените nums[i] на -nums[i]. Вы должны применить этот процесс ровно k раз. Вы можете выбрать один и тот же индекс i несколько раз. Верните наибольшую возможную сумму массива после его модификации таким образом.
Пример:
Input: nums = [4,2,3], k = 1 Output: 5👨💻 Алгоритм: 1⃣Сортировка массива: Отсортируйте массив nums по возрастанию, чтобы наибольшее количество раз менять самые маленькие (отрицательные) значения на их противоположные. 2⃣Модификация массива: Пройдитесь по отсортированному массиву и замените k наименьших значений на их противоположные (умножьте на -1). Если встретите 0, прекратите дальнейшие изменения, так как изменение 0 на -0 не имеет смысла. 3⃣Проверка остатка изменений: Если после первого прохода остались изменения (k нечетное), то найдите минимальное значение в измененном массиве и еще раз поменяйте его знак. Это обеспечит максимальную сумму. 😎 Решение:
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); ++i) {
if (k > 0 && nums[i] < 0) {
nums[i] = -nums[i];
--k;
}
}
if (k % 2 == 1) {
sort(nums.begin(), nums.end());
nums[0] = -nums[0];
}
return accumulate(nums.begin(), nums.end(), 0);
}
};3 232
Задача: 685. Redundant Connection II
Сложность: hard
В этой задаче корневое дерево — это направленный граф, в котором существует ровно один узел (корень), для которого все остальные узлы являются потомками этого узла, плюс каждый узел имеет ровно одного родителя, за исключением корневого узла, у которого нет родителей.
Данный ввод представляет собой направленный граф, который изначально был корневым деревом с n узлами (со значениями от 1 до n), и к которому добавлено одно дополнительное направленное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее.
Результирующий граф представлен в виде двумерного массива ребер. Каждый элемент массива edges — это пара [ui, vi], представляющая направленное ребро, соединяющее узлы ui и vi, где ui является родителем ребенка vi.
Верните ребро, которое можно удалить, чтобы результирующий граф стал корневым деревом с n узлами. Если существует несколько ответов, верните ответ, который встречается последним в данном двумерном массиве.
Пример:
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]class Solution {
public:
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
int N = edges.size();
unordered_map<int, int> parent;
vector<vector<int>> candidates;
for (auto& edge : edges) {
if (parent.count(edge[1])) {
candidates.push_back({parent[edge[1]], edge[1]});
candidates.push_back(edge);
} else {
parent[edge[1]] = edge[0];
}
}
int root = orbit(1, parent).node;
if (candidates.empty()) {
auto cycle = orbit(root, parent).seen;
vector<int> ans = {0, 0};
for (auto& edge : edges) {
if (cycle.count(edge[0]) && cycle.count(edge[1])) {
ans = edge;
}
}
return ans;
}
unordered_map<int, vector<int>> children;
for (auto& p : parent) {
children[p.second].push_back(p.first);
}
vector<bool> seen(N + 1, false);
seen[0] = true;
stack<int> stk;
stk.push(root);
while (!stk.empty()) {
int node = stk.top();
stk.pop();
if (!seen[node]) {
seen[node] = true;
for (int c : children[node]) {
stk.push(c);
}
}
}
for (bool b : seen) {
if (!b) {
return candidates[0];
}
}
return candidates[1];
}
private:
struct OrbitResult {
int node;
unordered_set<int> seen;
OrbitResult(int n, unordered_set<int> s) : node(n), seen(s) {}
};
OrbitResult orbit(int node, unordered_map<int, int>& parent) {
unordered_set<int> seen;
while (parent.count(node) && !seen.count(node)) {
seen.insert(node);
node = parent[node];
}
return OrbitResult(node, seen);
}
};3 232
Задача: 1276. Number of Burgers with No Waste of Ingredients
Сложность: medium
Даны два целых числа tomatoSlices и cheeseSlices. Ингредиенты разных бургеров таковы: Jumbo Burger: 4 ломтика помидора и 1 ломтик сыра. Small Burger: 2 ломтика помидора и 1 ломтик сыра. Верните [total_jumbo, total_small] так, чтобы количество оставшихся tomatoSlices было равно 0, а количество оставшихся cheeseSlices было равно 0. Если невозможно сделать так, чтобы оставшиеся tomatoSlices и cheeseSlices были равны 0, верните [].
Пример:
Input: tomatoSlices = 16, cheeseSlices = 7 Output: [1,6]👨💻 Алгоритм: 1⃣Проверьте, возможно ли решить задачу, убедившись, что tomatoSlices четно и находится в допустимых пределах. 2⃣Решите систему уравнений: 4J + 2S = tomatoSlices J + S = cheeseSlices 3⃣Если решение существует, верните его, иначе верните пустой список. 😎 Решение:
class Solution {
public:
vector<int> numOfBurgers(int tomatoSlices, int cheeseSlices) {
if (tomatoSlices % 2 != 0 || tomatoSlices < 2 * cheeseSlices || tomatoSlices > 4 * cheeseSlices) {
return {};
}
int total_jumbo = (tomatoSlices - 2 * cheeseSlices) / 2;
int total_small = cheeseSlices - total_jumbo;
return {total_jumbo, total_small};
}
};3 232
Задача: 1305. All Elements in Two Binary Search Trees
Сложность: medium
Даны два бинарных дерева поиска root1 и root2. Вернуть список, содержащий все целые числа из обоих деревьев, отсортированные в порядке возрастания.
Пример:
Input: root1 = [2,1,4], root2 = [1,0,3] Output: [0,1,1,2,3,4]👨💻 Алгоритм: 1⃣Выполните итеративный обход в порядке возрастания обоих деревьев параллельно. 2⃣На каждом шаге добавляйте наименьшее доступное значение в выходной список. 3⃣Верните выходной список. 😎 Решение:
class TreeNode {
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {
stack<TreeNode*> stack1, stack2;
vector<int> output;
while (root1 || root2 || !stack1.empty() || !stack2.empty()) {
while (root1) {
stack1.push(root1);
root1 = root1->left;
}
while (root2) {
stack2.push(root2);
root2 = root2->left;
}
if (stack2.empty() || (!stack1.empty() && stack1.top()->val <= stack2.top()->val)) {
root1 = stack1.top();
stack1.pop();
output.push_back(root1->val);
root1 = root1->right;
} else {
root2 = stack2.top();
stack2.pop();
output.push_back(root2->val);
root2 = root2->right;
}
}
return output;
}
};3 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
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 232
Главный навык на ближайшие годы — ВАЙБ-КОДИНГ
ИИ уже пишет код, чинит баги, генерирует тесты, документацию и помогает запускать продукты быстрее, чем это делали классические команды разработки. И это уже не "будущее когда-нибудь", а реальность, которая меняет рынок уже сегодня
И те, кто научится вайбкодить сейчас, будут увереннее конкурировать на рынке и зарабатывать больше тех, кто по-прежнему делает всё вручную.
Стартовать с нуля поможет канал Вайб-кодинг. Там ребята круглосуточно мониторят более 320 российских и зарубежных источников и публикуют только главное: релизы, инструменты, гайды, курсы и практические кейсы.
Подписывайтесь, нас уже 30 тысяч: @vibecoding_tg
3 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
Задача: 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 232
Задача: 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();
}
};