Endi mavjud! Telegram Tadqiqoti 2025 — yilning asosiy insaytlari 
C/C++ | LeetCode
Kanalga Telegram’da o‘tish
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+zYofcX2VLTM3MGMy Вопросы собесов t.me/+BTbqlW1VbIFmYmVi Вакансии t.me/+za2mJYs4riAzMzFi
Ko'proq ko'rsatish3 259
Obunachilar
+424 soatlar
-17 kunlar
-430 kunlar
Postlar arxiv
3 259
Задача: 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 259
Задача: 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 259
Задача: 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 259
Задача: 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 259
Задача: 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 259
Задача: 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 259
Задача: 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 259
Задача: 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 259
Задача: 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 259
Задача: 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;
}
};3 259
Задача: 984. String Without AAA or BBB
Сложность: medium
Даны два целых числа a и b, верните любую строку s, такую что:
s имеет длину a + b и содержит ровно a букв 'a' и ровно b букв 'b'.
Подстрока 'aaa' не встречается в s.
Подстрока 'bbb' не встречается в s.
Пример:
Input: a = 4, b = 1 Output: "aabaa"👨💻 Алгоритм: 1⃣Инициализация переменных: Завести пустую строку s и переменные a_count и b_count для отслеживания оставшихся 'a' и 'b' соответственно. 2⃣Создание строки: Добавляйте символы в строку s, попеременно добавляя 'a' и 'b', чтобы избегать подстрок 'aaa' и 'bbb'. Если в строке подряд уже два символа 'a' и осталось ещё 'b', добавьте 'b' и наоборот. Если оба символа возможны для добавления, выбирайте тот, которого осталось больше. 3⃣Добавление оставшихся символов: После основной логики добавления символов, добавьте оставшиеся 'a' или 'b' в конец строки, если они остались. 😎 Решение:
class Solution {
public:
string strWithout3a3b(int a, int b) {
string result;
while (a > 0 || b > 0) {
if (result.size() >= 2 && result[result.size() - 1] == result[result.size() - 2]) {
if (result.back() == 'a') {
result.push_back('b');
b--;
} else {
result.push_back('a');
a--;
}
} else {
if (a >= b) {
result.push_back('a');
a--;
} else {
result.push_back('b');
b--;
}
}
}
return result;
}
};3 259
Задача: 477. Total Hamming Distance
Сложность: medium
Хэммингово расстояние между двумя целыми числами — это количество позиций, в которых соответствующие биты отличаются.
Дан целочисленный массив nums, верните сумму Хэмминговых расстояний между всеми парами чисел в nums.
Пример:
Input: nums = [4,14,2] Output: 6 Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). The answer will be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.👨💻 Алгоритм: 1⃣Для каждой уникальной пары элементов из массива вычисляем битовое XOR, чтобы найти позиции, где биты различаются. Бит, равный 1 в результате, указывает на различие. 2⃣Для каждой пары элементов используем XOR, чтобы получить битовую разницу, и подсчитываем количество битов, равных 1, чтобы определить Хэммингово расстояние между парой. 3⃣Суммируем все Хэмминговы расстояния для всех пар, чтобы получить общую сумму Хэмминговых расстояний. 😎 Решение:
int totalHammingDistance(vector<int>& nums)
{
int ans = 0;
if (nums.empty())
return ans;
for (int i = 0; i < nums.size() - 1; i++)
for (int j = i + 1; j < nums.size(); j++)
ans += __builtin_popcount(nums[i] ^ nums[j]);
return ans;
}3 259
Задача: 732. My Calendar III
Сложность: hard
k-бронирование происходит, когда k событий имеют некоторое непустое пересечение (т.е, дано некоторое время, общее для всех k событий). Даны некоторые события [startTime, endTime), после каждого данного события верните целое число k, представляющее максимальное k-бронирование между всеми предыдущими событиями. Реализация класса MyCalendarThree: MyCalendarThree() Инициализирует объект. int book(int startTime, int endTime) Возвращает целое число k, представляющее наибольшее целое число, при котором в календаре существует k-бронирование.
Пример:
Input ["MyCalendarThree", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]] Output [null, 1, 1, 2, 3, 3, 3]👨💻 Алгоритм: 1⃣Создайте два словаря для хранения изменений времени бронирования: один для начала событий, другой для конца событий. 2⃣Для каждого нового события обновите словари начала и конца событий. 3⃣Поддерживайте текущее количество активных бронирований и обновляйте максимальное количество активных бронирований по мере добавления новых событий. 😎 Решение:
class MyCalendarThree {
public:
MyCalendarThree() {}
int book(int startTime, int endTime) {
events[startTime]++;
events[endTime]--;
int active = 0;
int maxActive = 0;
for (const auto& [time, count] : events) {
active += count;
maxActive = max(maxActive, active);
}
return maxActive;
}
private:
map<int, int> events;
};3 259
Задача: 1122. Relative Sort Array
Сложность: easy
Даны два массива arr1 и arr2, элементы arr2 уникальны, и все элементы arr2 также присутствуют в arr1.
Отсортируйте элементы arr1 таким образом, чтобы относительный порядок элементов в arr1 был таким же, как в arr2. Элементы, которые не встречаются в arr2, должны быть размещены в конце arr1 в порядке возрастания.
Пример:
Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] Output: [2,2,2,1,4,3,3,9,6,7,19]👨💻 Алгоритм: 1⃣Инициализация и подсчёт: Инициализируйте пустой массив result и массив remaining для хранения оставшихся элементов. Создайте хеш-таблицу countMap для хранения количества вхождений каждого элемента из arr2 в arr1. 2⃣Заполнение countMap и remaining: Пройдитесь по элементам arr1 и если элемент присутствует в countMap, увеличьте его счетчик. Если элемент не присутствует в arr2, добавьте его в remaining. 3⃣Формирование результирующего массива: Пройдитесь по arr2 и добавьте элементы в result в соответствии с их количеством в countMap. Отсортируйте массив remaining и добавьте его элементы в result. Верните result в виде массива. 😎 Решение:
class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
unordered_map<int, int> countMap;
vector<int> remaining;
vector<int> result;
for (int value : arr2) {
countMap[value] = 0;
}
for (int value : arr1) {
if (countMap.count(value)) {
countMap[value]++;
} else {
remaining.push_back(value);
}
}
sort(remaining.begin(), remaining.end());
for (int value : arr2) {
for (int i = 0; i < countMap[value]; i++) {
result.push_back(value);
}
}
result.insert(result.end(), remaining.begin(), remaining.end());
return result;
}
};3 259
Задача: 907. Sum of Subarray Minimums
Сложность: medium
Учитывая массив целых чисел arr, найдите сумму min(b), где b находится в каждом (смежном) подмассиве arr. Поскольку ответ может быть большим, верните ответ по модулю 109 + 7.
Пример:
Input: arr = [3,1,2,4] Output: 17👨💻 Алгоритм: 1⃣Использовать монотонный стек для нахождения ближайшего меньшего элемента слева и справа для каждого элемента массива. 2⃣Использовать эту информацию для вычисления количества подмассивов, где каждый элемент является минимальным. 3⃣Вычислить сумму минимальных значений для всех подмассивов и вернуть результат по модулю 10^9 + 7. 😎 Решение:
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
const int MOD = 1e9 + 7;
int n = arr.size();
vector<int> left(n), right(n);
stack<int> st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && arr[st.top()] > arr[i]) {
st.pop();
}
left[i] = st.empty() ? i + 1 : i - st.top();
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && arr[st.top()] >= arr[i]) {
st.pop();
}
right[i] = st.empty() ? n - i : st.top() - i;
st.push(i);
}
long long result = 0;
for (int i = 0; i < n; ++i) {
result = (result + (long long)arr[i] * left[i] * right[i]) % MOD;
}
return result;
}
};3 259
Задача: 507. Perfect Number
Сложность: easy
Совершенное число — это положительное целое число, которое равно сумме своих положительных делителей, исключая само число. Делитель целого числа x — это целое число, которое может делить x нацело.
Дано целое число n, верните true, если n является совершенным числом, в противном случае верните false.
Пример:
Input: num = 28 Output: true Explanation: 28 = 1 + 2 + 4 + 7 + 14 1, 2, 4, 7, and 14 are all divisors of 28.👨💻 Алгоритм: 1⃣Инициализация Если число num меньше или равно 0, вернуть false. Инициализируйте переменную sum значением 0. 2⃣Поиск делителей и вычисление суммы Переберите числа от 1 до квадратного корня num. Если число является делителем num, добавьте его к sum. Если делитель не равен квадратному корню num, добавьте к sum также результат деления num на делитель. 3⃣Проверка на совершенное число Вычтите num из sum. Если результат равен num, вернуть true, иначе вернуть false. 😎 Решение:
class Solution {
public:
bool checkPerfectNumber(int num) {
if (num <= 0) return false;
int sum = 0;
for (int i = 1; i * i <= num; ++i) {
if (num % i == 0) {
sum += i;
if (i * i != num) {
sum += num / i;
}
}
}
return sum - num == num;
}
};3 259
Задача: 229. Majority Element II
Сложность: medium
Дан массив целых чисел размера n, найдите все элементы, которые встречаются более ⌊ n/3 ⌋ раз.
Пример:
Input: nums = [3,2,3] Output: [3]👨💻 Алгоритм: 1⃣Поиск кандидатов: Пройдите через массив, используя алгоритм Бойера-Мура для поиска двух потенциальных кандидатов, которые могут встречаться более ⌊ n/3 ⌋ раз. Поддерживайте два счётчика и двух кандидатов. Если текущий элемент равен одному из кандидатов, увеличьте соответствующий счётчик. Если счётчик равен нулю, установите текущий элемент как кандидата и установите счётчик в 1. Если текущий элемент не совпадает ни с одним из кандидатов, уменьшите оба счётчика. 2⃣Подсчёт голосов: После определения двух кандидатов, пройдите через массив снова, чтобы посчитать фактическое количество появлений каждого кандидата. 3⃣Проверка порога: Проверьте, превышает ли количество появлений каждого кандидата порог ⌊ n/3 ⌋. Если да, добавьте кандидата в результат. 😎 Решение:
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
int count1 = 0, count2 = 0;
int candidate1 = INT_MIN, candidate2 = INT_MIN;
for (int n : nums) {
if (candidate1 == n) {
count1++;
} else if (candidate2 == n) {
count2++;
} else if (count1 == 0) {
candidate1 = n;
count1 = 1;
} else if (count2 == 0) {
candidate2 = n;
count2 = 1;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int n : nums) {
if (candidate1 == n) count1++;
if (candidate2 == n) count2++;
}
vector<int> result;
int n = nums.size();
if (count1 > n / 3) result.push_back(candidate1);
if (count2 > n / 3) result.push_back(candidate2);
return result;
}
};3 259
Задача: 956. Tallest Billboard
Сложность: hard
Вы устанавливаете рекламный щит и хотите, чтобы он имел наибольшую высоту. У рекламного щита будет две стальные опоры, по одной с каждой стороны. Каждая стальная опора должна быть одинаковой высоты. Вам дается набор стержней, которые можно сварить вместе. Например, если у вас есть стержни длиной 1, 2 и 3, вы можете сварить их вместе, чтобы получилась опора длиной 6. Верните наибольшую возможную высоту вашей рекламной установки. Если вы не можете установить рекламный щит, верните 0.
Пример:
Input: rods = [1,2,3,6] Output: 6👨💻 Алгоритм: 1⃣Определить количество строк n и длину каждой строки m. Создать массив delete_count длиной m, который будет отслеживать количество удаляемых столбцов. 2⃣Итеративно проверить каждую пару соседних строк для всех столбцов. Если для данной пары строк обнаружено нарушение лексикографического порядка, отметить соответствующий столбец для удаления. 3⃣Повторять процесс до тех пор, пока массив строк не станет лексикографически отсортированным. Вернуть количество удаленных столбцов. 😎 Решение:
class Solution {
public:
int minDeletionSize(vector<string>& strs) {
int n = strs.size();
int m = strs[0].length();
vector<bool> deleteCount(m, false);
auto isSorted = [&]() {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
if (deleteCount[j]) continue;
if (strs[i][j] > strs[i + 1][j]) return false;
if (strs[i][j] < strs[i + 1][j]) break;
}
}
return true;
};
while (!isSorted()) {
for (int j = 0; j < m; j++) {
if (deleteCount[j]) continue;
for (int i = 0; i < n - 1; i++) {
if (strs[i][j] > strs[i + 1][j]) {
deleteCount[j] = true;
break;
}
}
if (deleteCount[j]) break;
}
}
return count(deleteCount.begin(), deleteCount.end(), true);
}
};3 259
Задача: 1099. Two Sum Less Than K
Сложность: easy
Дан массив целых чисел nums и целое число k. Верните максимальную сумму, такую что существуют i < j, при которых nums[i] + nums[j] = sum и sum < k. Если не существует таких i и j, удовлетворяющих этому условию, верните -1.
Пример:
Input: nums = [34,23,1,24,75,33,54,8], k = 60 Output: 58 Explanation: We can use 34 and 24 to sum 58 which is less than 60.👨💻 Алгоритм: 1⃣Отсортируйте массив. 2⃣Установите указатели: левый на начало массива, правый на конец. 3⃣Пока левый указатель меньше правого: Если сумма элементов по указателям меньше k, обновите максимальную сумму и сдвиньте левый указатель вправо. Иначе сдвиньте правый указатель влево. Верните максимальную сумму. 😎 Решение:
class Solution {
public:
int twoSumLessThanK(vector<int>& nums, int k) {
int answer = -1;
int count[1001] = {};
for (int num : nums) {
count[num]++;
}
int lo = 1;
int hi = 1000;
while (lo <= hi) {
if (lo + hi >= k || count[hi] == 0) {
hi--;
} else {
if (count[lo] > (lo < hi ? 0 : 1)) {
answer = max(answer, lo + hi);
}
lo++;
}
}
return answer;
}
};3 259
Задача: 101. Symmetric Tree
Сложность: easy
Дан корень бинарного дерева. Проверьте, является ли это дерево зеркальным отражением самого себя (то есть симметричным относительно своего центра).
Пример:
Input: root = [1,2,2,3,4,4,3] Output: true👨💻 Алгоритм: 1⃣Дерево симметрично, если его левое и правое поддеревья являются зеркальным отражением друг друга. 2⃣Два дерева — зеркальные, если их корни равны и правое поддерево одного совпадает с левым другого. 3⃣Используйте рекурсию: сравните правое поддерево первого с левым поддеревом второго, и наоборот. 😎 Решение:
class Solution {
public:
bool isSymmetric(TreeNode* root) { return isMirror(root, root); }
bool isMirror(TreeNode* t1, TreeNode* t2) {
if (t1 == nullptr && t2 == nullptr) return true;
if (t1 == nullptr || t2 == nullptr) return false;
return (t1->val == t2->val) && isMirror(t1->right, t2->left) &&
isMirror(t1->left, t2->right);
}
};