C/C++ | LeetCode
Kanalga Telegram’da o‘tish
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Ko'proq ko'rsatish
Tarmoq:3 231
Obunachilar
-124 soatlar
-87 kun
-530 kun
Postlar arxiv
3 231
Задача: 325. Maximum Size Subarray Sum Equals k
Сложность: medium
Дан целочисленный массив nums и целое число k. Верните максимальную длину подмассива, сумма которого равна k. Если такого подмассива не существует, верните 0.
Пример:
Input: nums = [1,-1,5,-2,3], k = 3 Output: 4 Explanation: The subarray [1, -1, 5, -2] sums to 3 and is the longest.👨💻 Алгоритм: 1⃣Инициализация переменных Инициализируйте prefixSum как 0 для отслеживания префиксной суммы nums. Инициализируйте longestSubarray как 0 для отслеживания самой длинной подмассы с суммой k. Инициализируйте хеш-карту indices для хранения префиксных сумм и их индексов. 2⃣Итерация по массиву На каждом индексе i, добавляйте nums[i] к prefixSum. Проверьте следующие условия: Если prefixSum == k, обновите longestSubarray как i + 1. Если prefixSum - k существует в indices, обновите longestSubarray, если текущая длина подмассива больше. Если текущий prefixSum еще не существует в indices, добавьте indices[prefixSum] = i. 3⃣Возврат результата Верните значение longestSubarray. 😎 Решение:
#include <vector>
#include <unordered_map>
class Solution {
public:
int maxSubArrayLen(std::vector<int>& nums, int k) {
int prefixSum = 0;
int longestSubarray = 0;
std::unordered_map<int, int> indices;
for (int i = 0; i < nums.size(); ++i) {
prefixSum += nums[i];
if (prefixSum == k) {
longestSubarray = i + 1;
}
if (indices.find(prefixSum - k) != indices.end()) {
longestSubarray = std::max(longestSubarray, i - indices[prefixSum - k]);
}
if (indices.find(prefixSum) == indices.end()) {
indices[prefixSum] = i;
}
}
return longestSubarray;
}
};3 231
Задача: 1199. Minimum Time to Build Blocks
Сложность: hard
Вам дан список блоков, где blocks[i] = t означает, что на строительство i-го блока требуется t единиц времени. Блок может быть построен только одним рабочим.
Рабочий может либо разделиться на двух рабочих (количество рабочих увеличивается на одного), либо построить блок и уйти домой. Оба решения требуют некоторого времени.
Время, затраченное на разделение одного рабочего на двух, задано целым числом split. Обратите внимание, что если два рабочих разделяются одновременно, они разделяются параллельно, поэтому затраты времени будут равны split.
Выведите минимальное время, необходимое для строительства всех блоков.
Изначально есть только один рабочий.
Пример:
Input: blocks = [1,2,3], split = 1 Output: 4 Explanation: Split 1 worker into 2, then assign the first worker to the last block and split the second worker into 2. Then, use the two unassigned workers to build the first two blocks. The cost is 1 + max(3, 1 + max(1, 2)) = 4.👨💻 Алгоритм: 1⃣Подготовка кучи строительного времени: Инициализируйте кучу строительного времени, изначально содержащую все значения времени из массива blocks. 2⃣Обработка кучи: Пока в куче больше одного элемента: - извлеките минимальное значение из кучи, обозначим его как x. - извлеките следующее минимальное значение из кучи, обозначим его как y. - создайте новое время строительства, которое равно split + y, и вставьте его обратно в кучу. 3⃣Возврат результата: Когда в куче останется только одно значение, оно и будет минимальным временем, необходимым для строительства всех блоков. 😎 Решение:
#include <vector>
#include <queue>
class Solution {
public:
int minBuildTime(std::vector<int>& blocks, int split) {
std::priority_queue<int, std::vector<int>, std::greater<int>> pq(blocks.begin(), blocks.end());
while (pq.size() > 1) {
int x = pq.top(); pq.pop();
int y = pq.top(); pq.pop();
pq.push(split + y);
}
return pq.top();
}
};3 231
Задача: 210. Course Schedule II
Сложность: medium
Дано число numCourses и список пар prerequisites, где каждая пара [a, b] означает: чтобы взять курс a, нужно сначала пройти курс b.
Верните один из возможных порядков прохождения курсов.
Если пройти все курсы невозможно (из-за циклов) — верните пустой массив.
Пример:
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] Output: [0,2,1,3]👨💻 Алгоритм: 1⃣Построение графа и подготовка к DFS Создаем список смежности adjList, где adjList[b] содержит все курсы, зависящие от b. Каждый курс помечаем цветом: WHITE = 1 — не посещён GRAY = 2 — в процессе обработки BLACK = 3 — полностью обработан 2⃣Обход в глубину (DFS) и детектирование цикла Для каждого непосещённого узла запускаем dfs. Если во время обхода обнаруживаем цикл (возврат к GRAY узлу), значит, пройти курсы невозможно. 3⃣Формирование ответа После завершения DFS по всем узлам формируем порядок курсов из стека (или массива) topologicalOrder, инвертируя его. 😎Решение:
cppКопироватьРедактироватьclass Solution {
public:
int WHITE = 1;
int GRAY = 2;
int BLACK = 3;
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
bool isPossible = true;
map<int, int> color;
map<int, vector<int>> adjList;
vector<int> topologicalOrder;
for (int i = 0; i < numCourses; i++) color[i] = WHITE;
for (vector<int> relation : prerequisites) {
int dest = relation[0];
int src = relation[1];
adjList[src].push_back(dest);
}
for (int i = 0; i < numCourses && isPossible; i++) {
if (color[i] == WHITE) {
dfs(i, color, adjList, isPossible, topologicalOrder);
}
}
vector<int> order;
if (isPossible) {
order.resize(numCourses);
for (int i = 0; i < numCourses; i++) {
order[i] = topologicalOrder[numCourses - i - 1];
}
}
return order;
}
void dfs(int node, map<int, int>& color, map<int, vector<int>>& adjList,
bool& isPossible, vector<int>& topologicalOrder) {
if (!isPossible) return;
color[node] = GRAY;
for (int neighbor : adjList[node]) {
if (color[neighbor] == WHITE) {
dfs(neighbor, color, adjList, isPossible, topologicalOrder);
} else if (color[neighbor] == GRAY) {
isPossible = false;
}
}
color[node] = BLACK;
topologicalOrder.push_back(node);
}
};3 231
Задача: 1217. Minimum Cost to Move Chips to The Same Position
Сложность: easy
У нас есть n фишек, где позиция i-й фишки равна position[i].
Нам нужно переместить все фишки в одну и ту же позицию. За один шаг мы можем изменить позицию i-й фишки с position[i] на:
position[i] + 2 или position[i] - 2 с затратами = 0.
position[i] + 1 или position[i] - 1 с затратами = 1.
Верните минимальные затраты, необходимые для перемещения всех фишек в одну и ту же позицию.
Пример:
Input: position = [2,2,2,3,3] Output: 2 Explanation: We can move the two chips at position 3 to position 2. Each move has cost = 1. The total cost = 2.👨💻 Алгоритм: 1⃣Посчитать количество фишек на четных и нечетных позициях. 2⃣Сравнить количество фишек на четных и нечетных позициях. 3⃣Вернуть минимальное количество фишек как минимальную стоимость для перемещения всех фишек в одну позицию. 😎 Решение:
class Solution {
public:
int minCostToMoveChips(vector<int>& position) {
int evenCount = 0;
int oddCount = 0;
for (int pos : position) {
if (pos % 2 == 0) {
evenCount++;
} else {
oddCount++;
}
}
return min(evenCount, oddCount);
}
};3 231
Задача: 1434. Number of Ways to Wear Different Hats to Each Other
Сложность: hard
Дано n человек и 40 видов шляп, пронумерованных от 1 до 40.
Дан двумерный целочисленный массив hats, где hats[i] — список всех шляп, предпочитаемых i-м человеком.
Вернуть количество способов, которыми n человек могут носить различные шляпы друг у друга.
Поскольку ответ может быть слишком большим, вернуть его по модулю 10^9 + 7.
Пример:
Input: hats = [[3,4],[4,5],[5]] Output: 1 Explanation: There is only one way to choose hats given the conditions. First person choose hat 3, Second person choose hat 4 and last one hat 5.👨💻 Алгоритм: 1⃣Инициализировать переменные: n - количество людей, done = 2^n - 1, MOD = 10^9 + 7, memo - двумерный массив размером 41 * done, заполненный -1, и hatsToPeople - отображение шляп на людей. 2⃣Заполнить hatsToPeople, сопоставив каждую шляпу людям, которые её предпочитают. Реализовать функцию dp(hat, mask), которая использует мемоизацию для вычисления количества способов распределения шляп. 3⃣Вернуть результат вызова dp(1, 0), который выполняет основное вычисление количества способов распределения шляп. 😎 Решение:
class Solution {
vector<vector<int>> memo;
int done;
int n;
const int MOD = 1000000007;
unordered_map<int, vector<int>> hatsToPeople;
public:
int numberWays(vector<vector<int>>& hats) {
n = hats.size();
for (int i = 0; i < n; i++) {
for (int hat: hats[i]) {
hatsToPeople[hat].push_back(i);
}
}
done = (1 << n) - 1;
memo = vector<vector<int>>(41, vector<int>(done, -1));
return dp(1, 0);
}
private:
int dp(int hat, int mask) {
if (mask == done) {
return 1;
}
if (hat > 40) {
return 0;
}
if (memo[hat][mask] != -1) {
return memo[hat][mask];
}
int ans = dp(hat + 1, mask);
if (hatsToPeople.count(hat)) {
for (int person: hatsToPeople[hat]) {
if ((mask & (1 << person)) == 0) {
ans = (ans + dp(hat + 1, mask | (1 << person))) % MOD;
}
}
}
memo[hat][mask] = ans;
return ans;
}
};3 231
Задача: 661. Image Smoother
Сложность: easy
Дан целочисленный матрица img размером m x n, представляющая градации серого изображения. Верните изображение после применения сглаживания к каждой его ячейке.
Пример:
Input: img = [[1,1,1],[1,0,1],[1,1,1]] Output: [[0,0,0],[0,0,0],[0,0,0]] Explanation: For the points (0,0), (0,2), (2,0), (2,2): floor(3/4) = floor(0.75) = 0 For the points (0,1), (1,0), (1,2), (2,1): floor(5/6) = floor(0.83333333) = 0 For the point (1,1): floor(8/9) = floor(0.88888889) = 0👨💻 Алгоритм: 1⃣Инициализация: Создайте новую матрицу такого же размера, чтобы сохранить результат сглаживания. 2⃣Обработка каждой ячейки: Для каждой ячейки исходной матрицы найдите всех её соседей (включая саму ячейку). Вычислите среднее значение этих ячеек и сохраните его в соответствующей ячейке результирующей матрицы. 3⃣Возврат результата: Верните результирующую матрицу после применения сглаживания ко всем ячейкам. 😎 Решение:
class Solution {
public:
vector<vector<int>> imageSmoother(vector<vector<int>>& img) {
int m = img.size(), n = img[0].size();
vector<vector<int>> result(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int count = 0, total = 0;
for (int ni = max(0, i - 1); ni <= min(m - 1, i + 1); ni++) {
for (int nj = max(0, j - 1); nj <= min(n - 1, j + 1); nj++) {
total += img[ni][nj];
count++;
}
}
result[i][j] = total / count;
}
}
return result;
}
};3 231
Задача: 591. Tag Validator
Сложность: hard
Дана строка, представляющая фрагмент кода, реализуйте валидатор тегов для разбора кода и определения его корректности.
Фрагмент кода считается корректным, если соблюдаются все следующие правила:
Код должен быть заключен в корректный закрытый тег. В противном случае код некорректен.
Закрытый тег (не обязательно корректный) имеет точно следующий формат: <TAG_NAME>TAG_CONTENT</TAG_NAME>. Среди них <TAG_NAME> — это начальный тег, а </TAG_NAME> — конечный тег. TAG_NAME в начальном и конечном тегах должен быть одинаковым. Закрытый тег корректен, если и только если TAG_NAME и TAG_CONTENT корректны.
Корректное TAG_NAME содержит только заглавные буквы и имеет длину в диапазоне [1, 9]. В противном случае TAG_NAME некорректен.
Корректное TAG_CONTENT может содержать другие корректные закрытые теги, cdata и любые символы (см. примечание 1), КРОМЕ неподходящих <, неподходящих начальных и конечных тегов, и неподходящих или закрытых тегов с некорректным TAG_NAME. В противном случае TAG_CONTENT некорректен.
Начальный тег неподходящий, если нет конечного тега с тем же TAG_NAME, и наоборот. Однако нужно также учитывать проблему несбалансированных тегов, когда они вложены.
< неподходящий, если не удается найти последующий >. И когда вы находите < или </, все последующие символы до следующего > должны быть разобраны как TAG_NAME (не обязательно корректный).
cdata имеет следующий формат: <![CDATA[CDATA_CONTENT]]>. Диапазон CDATA_CONTENT определяется как символы между <![CDATA[ и первым последующим ]]>.
CDATA_CONTENT может содержать любые символы. Функция cdata заключается в том, чтобы запретить валидатору разбирать CDATA_CONTENT, поэтому даже если в нем есть символы, которые могут быть разобраны как тег (корректный или некорректный), вы должны рассматривать их как обычные символы.
Пример:
Input: code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>" Output: true👨💻 Алгоритм: 1⃣Инициализируйте стек для отслеживания открытых тегов и флаг для определения наличия тегов. Используйте регулярное выражение для проверки корректности TAG_NAME, TAG_CONTENT и CDATA. 2⃣Пройдитесь по строке, проверяя каждый символ. Если встретите <, определите тип тега (начальный, конечный или CDATA). Обновите стек и индексы в зависимости от найденного типа. 3⃣В конце проверьте, что стек пуст (все теги корректно закрыты) и верните результат. 😎 Решение:
#include <string>
#include <stack>
#include <regex>
using namespace std;
class Solution {
stack<string> stack;
bool containsTag = false;
bool isValidTagName(const string& s, bool ending) {
if (ending) {
if (!stack.empty() && stack.top() == s) stack.pop();
else return false;
} else {
containsTag = true;
stack.push(s);
}
return true;
}
public:
bool isValid(string code) {
regex pattern("<[A-Z]{0,9}>([^<]*(<((\\/?[A-Z]{1,9}>)|(!\\[CDATA\\[(.*?)]]>)))?)*");
if (!regex_match(code, pattern)) return false;
int i = 0;
while (i < code.size()) {
bool ending = false;
if (stack.empty() && containsTag) return false;
if (code[i] == '<') {
if (code[i + 1] == '!') {
i = code.find("]]>", i + 1);
if (i == string::npos) return false;
continue;
}
if (code[i + 1] == '/') {
i++;
ending = true;
}
int closeIndex = code.find('>', i + 1);
if (closeIndex == string::npos || !isValidTagName(code.substr(i + 1, closeIndex - (i + 1)), ending)) return false;
i = closeIndex;
}
i++;
}
return stack.empty();
}
};3 231
Задача: 1469. Find All The Lonely Nodes
Сложность: easy
В бинарном дереве одиночный узел — это узел, который является единственным ребёнком своего родительского узла. Корень дерева не является одиночным, так как у него нет родительского узла.
Дано корневое значение бинарного дерева. Верните массив, содержащий значения всех одиночных узлов в дереве. Верните список в любом порядке.
Пример:
Input: root = [7,1,4,6,null,5,3,null,null,null,null,null,2]
Output: [6,2]
Explanation: Light blue nodes are lonely nodes.
Please remember that order doesn't matter, [2,6] is also an acceptable answer.#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
void DFS(TreeNode* root, bool isLonely, vector<int>& ans) {
if (root == NULL) {
return;
}
if (isLonely) {
ans.push_back(root->val);
}
DFS(root->left, root->right == NULL, ans);
DFS(root->right, root->left == NULL, ans);
}
vector<int> getLonelyNodes(TreeNode* root) {
vector<int> ans;
DFS(root, false, ans);
return ans;
}
};3 231
Задача: 283. Move Zeroes
Сложность: easy
Дан целочисленный массив nums. Переместите все нули в конец массива, сохраняя относительный порядок ненулевых элементов.
Обратите внимание, что вы должны сделать это на месте, не создавая копию массива.
Пример:
Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0]👨💻 Алгоритм: 1⃣Инициализация указателей: Инициализируйте два указателя: lastNonZeroFoundAt для отслеживания позиции последнего ненулевого элемента и cur для итерации по массиву. 2⃣Итерация и обмен элементами: Итерируйтесь по массиву с помощью указателя cur. Если текущий элемент ненулевой, поменяйте его местами с элементом, на который указывает lastNonZeroFoundAt, и продвиньте указатель lastNonZeroFoundAt. 3⃣Завершение итерации: Повторяйте шаг 2 до конца массива. В итоге все нули будут перемещены в конец массива, сохраняя относительный порядок ненулевых элементов. 😎 Решение:
void moveZeroes(vector<int>& nums) {
for (int lastNonZeroFoundAt = 0, cur = 0; cur < nums.size(); cur++) {
if (nums[cur] != 0) {
swap(nums[lastNonZeroFoundAt++], nums[cur]);
}
}
}3 231
Задача: 870. Advantage Shuffle
Сложность: medium
Даны два целочисленных массива nums1 и nums2 одинаковой длины. Преимущество nums1 относительно nums2 — это количество индексов i, для которых nums1[i] > nums2[i].
Верните любую перестановку nums1, которая максимизирует его преимущество относительно nums2.
Пример:
Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11]
Output: [2,11,7,15]class Solution {
public:
vector<int> advantageCount(vector<int>& A, vector<int>& B) {
vector<int> sortedA(A);
sort(sortedA.begin(), sortedA.end());
vector<pair<int, int>> sortedB;
for (int i = 0; i < B.size(); ++i)
sortedB.push_back({B[i], i});
sort(sortedB.begin(), sortedB.end());
unordered_map<int, deque<int>> assigned;
for (int b: B) assigned[b] = {};
deque<int> remaining;
int j = 0;
for (int a: sortedA) {
if (a > sortedB[j].first) {
assigned[sortedB[j++].first].push_back(a);
} else {
remaining.push_back(a);
}
}
vector<int> ans(B.size());
for (int i = 0; i < B.size(); ++i) {
if (assigned[B[i]].size() > 0) {
ans[i] = assigned[B[i]].front();
assigned[B[i]].pop_front();
} else {
ans[i] = remaining.front();
remaining.pop_front();
}
}
return ans;
}
};3 231
Задача: 775. Global and Local Inversions
Сложность: medium
Дан массив целых чисел nums длиной n, который представляет собой перестановку всех чисел в диапазоне [0, n - 1].
Число глобальных инверсий — это количество различных пар (i, j), где:
0 <= i < j < n
nums[i] > nums[j]
Число локальных инверсий — это количество индексов i, где:
0 <= i < n - 1
nums[i] > nums[i + 1]
Верните true, если количество глобальных инверсий равно количеству локальных инверсий.
Пример:
Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.class Solution {
public:
bool isIdealPermutation(vector<int>& A) {
int N = A.size();
for (int i = 0; i < N; ++i)
for (int j = i + 2; j < N; ++j)
if (A[i] > A[j]) return false;
return true;
}
};3 231
Задача: 733. Flood Fill
Сложность: easy
Изображение представлено в виде целочисленной сетки m x n, где image[i][j] - значение пикселя изображения. Вам также даны три целых числа sr, sc и color. Вы должны выполнить заливку изображения, начиная с пикселя image[sr][sc]. Чтобы выполнить заливку, рассмотрите начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с начальным пикселем, того же цвета, что и начальный пиксель, плюс все пиксели, соединенные по 4-м направлениям с этими пикселями (также того же цвета), и так далее. Замените цвет всех вышеупомянутых пикселей на цвет. Верните измененное изображение после выполнения заливки.
Пример:
Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2 Output: [[2,2,2],[2,2,0],[2,0,1]]👨💻 Алгоритм: 1⃣Получите цвет начального пикселя. 2⃣Используйте обход в глубину (DFS) или обход в ширину (BFS) для замены цвета всех пикселей, которые соединены с начальным пикселем и имеют тот же цвет. 3⃣Обновите изображение и верните его. 😎 Решение:
class Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
int originalColor = image[sr][sc];
if (originalColor == color) {
return image;
}
dfs(image, sr, sc, originalColor, color);
return image;
}
private:
void dfs(vector<vector<int>>& image, int x, int y, int originalColor, int newColor) {
if (x < 0 || x >= image.size() || y < 0 || y >= image[0].size() || image[x][y] != originalColor) {
return;
}
image[x][y] = newColor;
dfs(image, x + 1, y, originalColor, newColor);
dfs(image, x - 1, y, originalColor, newColor);
dfs(image, x, y + 1, originalColor, newColor);
dfs(image, x, y - 1, originalColor, newColor);
}
};3 231
Задача: 541. Reverse String II
Сложность: easy
Дана строка s и целое число k, переверните первые k символов для каждых 2k символов, начиная с начала строки.
Если осталось меньше k символов, переверните все. Если осталось меньше 2k, но больше или равно k символов, переверните первые k символов и оставьте остальные как есть.
Пример:
Input: s = "abcdefg", k = 2 Output: "bacdfeg"👨💻 Алгоритм: 1⃣Разворачиваем каждый блок из 2k символов непосредственно. Каждый блок начинается с кратного 2k: например, 0, 2k, 4k, 6k и так далее. 2⃣Будьте внимательны, если символов недостаточно, блок может не быть перевернут. 3⃣Для разворота блока символов с позиции i до j, меняем местами символы на позициях i++ и j--. 😎 Решение:
class Solution {
public:
string reverseStr(string s, int k) {
vector<char> a(s.begin(), s.end());
for (int start = 0; start < a.size(); start += 2 * k) {
int i = start, j = min(start + k - 1, (int)a.size() - 1);
while (i < j) {
char tmp = a[i];
a[i++] = a[j];
a[j--] = tmp;
}
}
return string(a.begin(), a.end());
}
};3 231
Задача: 1100. Find K-Length Substrings With No Repeated Characters
Сложность: medium
Дана строка s и целое число k. Верните количество подстрок в s длиной k, которые не содержат повторяющихся символов.
Пример:
Input: s = "havefunonleetcode", k = 5 Output: 6 Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'.👨💻 Алгоритм: 1⃣Если k > 26, верните 0, так как не может быть строки длиной более 26 символов с уникальными символами. Для остальных случаев, где k <= 26, проверьте каждую подстроку длиной k на наличие повторяющихся символов. 2⃣Итерация по строке s от индекса 0 до n - k (включительно), где n - длина строки s: Для каждого индекса i: Инициализируйте флаг isUnique как true и массив частот размером 26 для подсчета частот каждого символа. Итерируйте следующие k символов и увеличивайте частоту каждого встреченного символа в массиве частот. Если частота любого символа становится больше 1, установите isUnique в false и прекратите итерацию. Если после итерации по k символам флаг isUnique все еще равен true, увеличьте счетчик ответов на 1. 3⃣Верните количество подстрок без повторяющихся символов после итерации по всем индексам от 0 до n - k. 😎 Решение:
class Solution {
public:
int numKLenSubstrNoRepeats(string s, int k) {
if (k > 26) return 0;
int answer = 0;
int n = s.size();
for (int i = 0; i <= n - k; i++) {
int freq[26] = {0};
bool isUnique = true;
for (int j = i; j < i + k; j++) {
freq[s[j] - 'a']++;
if (freq[s[j] - 'a'] > 1) {
isUnique = false;
break;
}
}
if (isUnique) answer++;
}
return answer;
}
};3 231
Задача: 844. Backspace String Compare
Сложность: easy
Даны две строки s и t, верните true, если они равны после ввода в пустые текстовые редакторы. Символ '#' означает клавишу backspace.
Обратите внимание, что после нажатия backspace на пустом тексте, текст останется пустым.
Пример:
Input: s = "ab#c", t = "ad#c" Output: true Explanation: Both s and t become "ac".👨💻 Алгоритм: 1⃣Пройдите по строкам s и t с конца, учитывая символы '#' как backspace и пропуская соответствующие символы. 2⃣Сравнивайте текущие символы из обеих строк, пропуская символы, которые должны быть удалены. 3⃣Если все соответствующие символы совпадают и строки эквивалентны после всех backspace операций, верните true; в противном случае верните false. 😎 Решение:
class Solution {
public:
bool backspaceCompare(string S, string T) {
int i = S.length() - 1, j = T.length() - 1;
int skipS = 0, skipT = 0;
while (i >= 0 || j >= 0) {
while (i >= 0) {
if (S[i] == '#') { skipS++; i--; }
else if (skipS > 0) { skipS--; i--; }
else break;
}
while (j >= 0) {
if (T[j] == '#') { skipT++; j--; }
else if (skipT > 0) { skipT--; j--; }
else break;
}
if (i >= 0 && j >= 0 && S[i] != T[j]) {
return false;
}
if ((i >= 0) != (j >= 0)) {
return false;
}
i--; j--;
}
return true;
}
};3 231
Задача: 1094. Car Pooling
Сложность: medium
Есть автомобиль с пустыми сиденьями емкостью capacity. Автомобиль движется только на восток (то есть он не может повернуть и ехать на запад).
Дан целочисленный параметр capacity и массив поездок trips, где trips[i] = [numPassengersi, fromi, toi] указывает, что на i-й поездке numPassengersi пассажиров должны быть забраны на позиции fromi и высажены на позиции toi. Позиции заданы как количество километров на восток от начальной точки автомобиля.
Верните true, если возможно забрать и высадить всех пассажиров для всех указанных поездок, или false в противном случае.
Пример:
Input: trips = [[2,1,5],[3,3,7]], capacity = 4 Output: false👨💻 Алгоритм: 1⃣Простая идея заключается в том, чтобы пройти от начала до конца и проверить, превышает ли фактическая вместимость capacity. 2⃣Чтобы узнать фактическую вместимость, нужно просто знать изменение количества пассажиров в каждый момент времени. 3⃣Мы можем сохранить изменения количества пассажиров в каждый момент времени, отсортировать их по меткам времени и, наконец, пройтись по ним, чтобы проверить фактическую вместимость. 😎 Решение:
#include <vector>
#include <map>
using namespace std;
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
map<int, int> timestamp;
for (auto& trip : trips) {
timestamp[trip[1]] += trip[0];
timestamp[trip[2]] -= trip[0];
}
int usedCapacity = 0;
for (auto& change : timestamp) {
usedCapacity += change.second;
if (usedCapacity > capacity) {
return false;
}
}
return true;
}
};3 231
Задача: 1260. Shift 2D Grid
Сложность: easy
Дана двумерная сетка размером m x n и целое число k. Требуется сдвинуть сетку k раз. За одну операцию сдвига: элемент в grid[i][j] перемещается в grid[i][j + 1]. Элемент в grid[i][n - 1] перемещается в grid[i + 1][0]. Элемент в grid[m - 1][n - 1] перемещается в grid[0][0]. Верните двумерную сетку после применения операции сдвига k раз.
Пример:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1 Output: [[9,1,2],[3,4,5],[6,7,8]]👨💻 Алгоритм: 1⃣Преобразовать двумерную сетку в одномерный массив. 2⃣Выполнить сдвиг элементов в одномерном массиве. 3⃣Преобразовать одномерный массив обратно в двумерную сетку. 😎 Решение:
class Solution {
public:
vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
int total = m * n;
k = k % total;
if (k == 0) {
return grid;
}
vector<int> flatArray(total);
for (int i = 0; i < total; ++i) {
flatArray[i] = grid[i / n][i % n];
}
vector<int> newArray(total);
for (int i = 0; i < total; ++i) {
newArray[(i + k) % total] = flatArray[i];
}
vector<vector<int>> newGrid(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
newGrid[i][j] = newArray[i * n + j];
}
}
return newGrid;
}
};3 231
Задача: №30. Substring with Concatenation of All Words
Сложность: hard
Вам дана строка s и массив строк words, где все слова одинаковой длины. Найдите все стартовые индексы подстрок в s, которые являются конкатенацией всех слов из массива (в любом порядке, без дополнительных символов между ними).
Пример:
Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9]👨💻 Алгоритм: 1⃣Вычисляем длину каждого слова и общее количество слов. 2⃣Используем скользящее окно с шагом = длине слова, и на каждом шаге проверяем, входят ли текущие слова в заданный набор. 3⃣Отслеживаем, сколько раз каждое слово встречается, используя unordered_map. 😎 Решение:
vector<int> findSubstring(string str, vector<string>& words) {
int len = words[0].length();
unordered_map<string, int> contain;
for (string s : words) contain[s]++;
vector<int> res;
for (int j = 0; j < len; j++) {
unordered_map<string, int> found;
int st = j;
for (int i = j; i <= str.size() - len; i += len) {
string curr = str.substr(i, len);
if (contain.find(curr) != contain.end()) {
found[curr]++;
while (found[curr] > contain[curr]) {
found[str.substr(st, len)]--;
st += len;
}
int size = (i - st + len) / len;
if (size == words.size()) {
res.push_back(st);
}
} else {
found.clear();
st = i + len;
}
}
}
return res;
}3 231
Задача: 1372. Longest ZigZag Path in a Binary Tree
Сложность: medium
Вам дан корень бинарного дерева.
Зигзагообразный путь для бинарного дерева определяется следующим образом:
Выберите любой узел в бинарном дереве и направление (вправо или влево).
Если текущее направление вправо, перейдите к правому дочернему узлу текущего узла; иначе перейдите к левому дочернему узлу.
Измените направление с вправо на влево или с влево на вправо.
Повторяйте второй и третий шаги, пока не сможете двигаться по дереву.
Длина зигзагообразного пути определяется как количество посещенных узлов минус 1 (один узел имеет длину 0).
Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве.
Пример:
Input: s = "rat" Output: "art" Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.👨💻 Алгоритм: 1⃣Рекурсивная функция DFS: Создайте рекурсивную функцию dfs, которая будет выполнять обход дерева и отслеживать текущую длину зигзагообразного пути и направление движения (влево или вправо). 2⃣Обновление максимальной длины пути: При каждом вызове рекурсивной функции обновляйте максимальную длину зигзагообразного пути, если текущая длина больше текущего максимума. 3⃣Рекурсивный вызов для левого и правого дочерних узлов: Рекурсивно вызывайте функцию dfs для левого и правого дочерних узлов с обновленными параметрами длины и направления. 😎 Решение:
#include <algorithm>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int maxLength = 0;
int longestZigZag(TreeNode* root) {
dfs(root, true, 0);
dfs(root, false, 0);
return maxLength;
}
void dfs(TreeNode* node, bool isLeft, int length) {
if (!node) return;
maxLength = std::max(maxLength, length);
if (isLeft) {
dfs(node->left, false, length + 1);
dfs(node->right, true, 1);
} else {
dfs(node->right, true, length + 1);
dfs(node->left, false, 1);
}
}
};3 231
Задача: 347. Top K Frequent Elements
Сложность: medium
Дан массив целых чисел nums и целое число k. Верните k самых частых элементов. Вы можете вернуть ответ в любом порядке.
Пример:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]👨💻 Алгоритм: 1⃣Подсчет частоты: Используйте хеш-таблицу или словарь для подсчета количества вхождений каждого элемента в массиве nums. 2⃣Создание кучи: Создайте кучу, чтобы отсортировать элементы по их частоте и выбрать k самых частых элементов. 3⃣Возврат результата: Верните k самых частых элементов. 😎 Решение:
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> count;
for (int num : nums) {
count[num]++;
}
priority_queue<pair<int, int>> heap;
for (const auto& [num, freq] : count) {
heap.emplace(freq, num);
}
vector<int> result;
for (int i = 0; i < k; ++i) {
result.push_back(heap.top().second);
heap.pop();
}
return result;
}
};