C/C++ | LeetCode
Kanalga Telegram’da o‘tish
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Ko'proq ko'rsatish
Tarmoq:3 218
Obunachilar
-124 soatlar
-107 kun
-830 kun
Ma'lumotlar yuklanmoqda
O'xshash kanallar
Taglar buluti
Kirish va chiqish esdaliklari
---
---
---
---
---
---
Obunachilarni jalb qilish
Oktabr '26Okt '26
Oktabr '26
+24
0 kanalda
Sentabr '26
+42
0 kanalda
Get PRO
Avgust '26
+32
0 kanalda
Get PRO
Iyul '26
+42
0 kanalda
Get PRO
Iyun '26
+30
1 kanalda
Get PRO
May '26
+35
0 kanalda
Get PRO
Aprel '26
+35
0 kanalda
Get PRO
Mart '26
+32
0 kanalda
Get PRO
Fevral '26
+45
0 kanalda
Get PRO
Yanvar '26
+35
0 kanalda
Get PRO
Dekabr '25
+37
0 kanalda
Get PRO
Noyabr '25
+84
0 kanalda
Get PRO
Oktabr '25
+43
0 kanalda
Get PRO
Sentabr '25
+35
0 kanalda
Get PRO
Avgust '25
+40
0 kanalda
Get PRO
Iyul '25
+40
1 kanalda
Get PRO
Iyun '25
+43
0 kanalda
Get PRO
May '25
+44
0 kanalda
Get PRO
Aprel '25
+61
0 kanalda
Get PRO
Mart '25
+60
1 kanalda
Get PRO
Fevral '25
+179
3 kanalda
Get PRO
Yanvar '25
+79
53 kanalda
Get PRO
Dekabr '24
+64
0 kanalda
Get PRO
Noyabr '24
+91
1 kanalda
Get PRO
Oktabr '24
+424
13 kanalda
Get PRO
Sentabr '24
+1 488
331 kanalda
Get PRO
Avgust '24
+91
0 kanalda
Get PRO
Iyul '24
+826
219 kanalda
Get PRO
Iyun '24
+1 211
232 kanalda
| Sana | Obunachilarni jalb qilish | Esdaliklar | Kanallar | |
| 26 Oktabr | 0 | |||
| 25 Oktabr | 0 | |||
| 24 Oktabr | 0 | |||
| 23 Oktabr | 0 | |||
| 22 Oktabr | +1 | |||
| 21 Oktabr | 0 | |||
| 20 Oktabr | +3 | |||
| 19 Oktabr | 0 | |||
| 18 Oktabr | +1 | |||
| 17 Oktabr | +1 | |||
| 16 Oktabr | 0 | |||
| 15 Oktabr | +2 | |||
| 14 Oktabr | +2 | |||
| 13 Oktabr | +3 | |||
| 12 Oktabr | 0 | |||
| 11 Oktabr | +2 | |||
| 10 Oktabr | +1 | |||
| 09 Oktabr | 0 | |||
| 08 Oktabr | +1 | |||
| 07 Oktabr | 0 | |||
| 06 Oktabr | 0 | |||
| 05 Oktabr | +3 | |||
| 04 Oktabr | +2 | |||
| 03 Oktabr | 0 | |||
| 02 Oktabr | +1 | |||
| 01 Oktabr | +1 |
Kanal postlari
Задача: 906. Super Palindromes
Сложность: hard
Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию.
Пример:
Input: left = "4", right = "1000" Output: 4👨💻 Алгоритм: 1⃣Найти все палиндромы до корня из right. 2⃣Проверить, являются ли квадраты этих палиндромов палиндромами и лежат ли в диапазоне [left, right]. 3⃣Подсчитать количество таких суперпалиндромов. 😎 Решение:
class Solution {
public:
bool isPalindrome(long long x) {
string s = to_string(x);
return s == string(s.rbegin(), s.rend());
}
int superpalindromesInRange(string left, string right) {
long long leftNum = stoll(left);
long long rightNum = stoll(right);
int count = 0;
for (int i = 1; i < 100000; i++) {
string s = to_string(i);
long long palin1 = stoll(s + string(s.rbegin(), s.rend()));
long long palin2 = stoll(s + string(s.rbegin() + 1, s.rend()));
if (palin1 * palin1 > rightNum) {
break;
}
if (palin1 * palin1 >= leftNum && isPalindrome(palin1 * palin1)) {
count++;
}
if (palin2 * palin2 >= leftNum && palin2 * palin2 <= rightNum && isPalindrome(palin2 * palin2)) {
count++;
}
}
return count;
}
};| 2 | Задача: 726. Number of Atoms
Сложность: hard
Если задана строковая формула, представляющая химическую формулу, верните количество атомов. Атомный элемент всегда начинается с прописного символа, затем ноль или более строчных букв, представляющих его название. Если количество больше 1, за ним может следовать одна или более цифр, представляющих количество элементов. Например, "H2O" и "H2O2" возможны, а "H1O2" невозможен. Две формулы объединяются вместе, чтобы получить другую формулу. Например, "H2O2He3Mg4" также является формулой.
Формула, заключенная в круглые скобки, и счет (по желанию) также являются формулами. Например, "(H2O2)" и "(H2O2)3" являются формулами.
Возвращает количество всех элементов в виде строки в следующем виде: первое имя (в отсортированном порядке), затем его количество (если это количество больше 1), затем второе имя (в отсортированном порядке), затем его количество (если это количество больше 1) и т. д. Тестовые примеры генерируются таким образом, чтобы все значения в выводе помещались в 32-битное целое число.
Пример:
Input: formula = "H2O"
Output: "H2O"
👨💻 Алгоритм:
1⃣Используйте стек для отслеживания текущего уровня скобок.
2⃣Пройдите по строке формулы, анализируя каждый символ: Если символ - это открывающая скобка '(', создайте новый словарь для хранения атомов внутри скобок. Если символ - это закрывающая скобка ')', извлеките словарь из стека и умножьте количества атомов на последующее число, если оно присутствует. Если символ - это атом (начинается с заглавной буквы), извлеките имя атома и его количество, и добавьте его в текущий словарь.
3⃣После завершения обработки строки, объедините все словари из стека и отсортируйте результат.
😎 Решение:
class Solution {
public:
string countOfAtoms(string formula) {
stack<map<string, int>> stack;
stack.push(map<string, int>());
int n = formula.size();
int i = 0;
while (i < n) {
if (formula[i] == '(') {
stack.push(map<string, int>());
i++;
} else if (formula[i] == ')') {
map<string, int> top = stack.top();
stack.pop();
i++;
int start = i;
while (i < n && isdigit(formula[i])) {
i++;
}
int multiplicity = i > start ? stoi(formula.substr(start, i - start)) : 1;
for (const auto& [name, count] : top) {
stack.top()[name] += count * multiplicity;
}
} else {
int start = i;
i++;
while (i < n && islower(formula[i])) {
i++;
}
string name = formula.substr(start, i - start);
start = i;
while (i < n && isdigit(formula[i])) {
i++;
}
int multiplicity = i > start ? stoi(formula.substr(start, i - start)) : 1;
stack.top()[name] += multiplicity;
}
}
map<string, int> countMap = stack.top();
string result;
for (const auto& [name, count] : countMap) {
result += name;
if (count > 1) {
result += to_string(count);
}
}
return result;
}
};
Ставь 👍 и забирай 📚 Базу знаний | 196 |
| 3 |  🔥 Скрытые вакансии с удаленной работой для C/C++ разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.
🔹 C/C++ Jobs | Вакансии
🔸 Все каналы с вакансиями | 230 |
| 4 | Задача: 1137. N-th Tribonacci Number
Сложность: easy
Трибоначчи последовательность Tn определяется следующим образом:
T0 = 0, T1 = 1, T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 для n >= 0.
Дано n, вернуть значение Tn.
Пример:
Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4
👨💻 Алгоритм:
1⃣Если n < 3, вернуть значение n-го терма, как указано в описании задачи.
2⃣Инициализировать a, b и c как базовые случаи. Установить a = 0, b = 1, c = 1.
3⃣Для следующих n - 2 шагов обновлять a, b, c следующим образом: a = b, b = c, c = a + b + c. Вернуть c.
😎 Решение:
class Solution {
public:
int tribonacci(int n) {
if (n < 3) {
return n > 0 ? 1 : 0;
}
int a = 0, b = 1, c = 1;
for (int i = 0; i < n - 2; ++i) {
int tmp = a + b + c;
a = b;
b = c;
c = tmp;
}
return c;
}
};
Ставь 👍 и забирай 📚 Базу знаний | 336 |
| 5 | Задача: 834. Sum of Distances in Tree
Сложность: hard
Есть неориентированное связное дерево с n узлами, пронумерованными от 0 до n - 1, и n - 1 ребрами.
Вам даны целое число n и массив edges, где edges[i] = [ai, bi] указывает, что существует ребро между узлами ai и bi в дереве.
Верните массив answer длиной n, где answer[i] — это сумма расстояний между i-м узлом в дереве и всеми другими узлами.
Пример:
Input: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: The tree is shown above.
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.
Hence, answer[0] = 8, and so on.
👨💻 Алгоритм:
1⃣Постройте дерево и выполните обход в глубину (DFS) для расчета количества узлов в поддереве и суммы расстояний до всех узлов поддерева.
2⃣На основе полученных данных рассчитайте сумму расстояний для корня дерева.
3⃣Выполните второй обход в глубину (DFS) для корректировки суммы расстояний для каждого узла на основе суммы расстояний его родительского узла.
😎 Решение:
#include <vector>
#include <unordered_set>
using namespace std;
class Solution {
public:
vector<int> ans, count;
vector<unordered_set<int>> graph;
int N;
vector<int> sumOfDistancesInTree(int N, vector<vector<int>>& edges) {
this->N = N;
graph.resize(N);
ans.resize(N);
count.resize(N, 1);
for (auto& edge : edges) {
graph[edge[0]].insert(edge[1]);
graph[edge[1]].insert(edge[0]);
}
dfs(0, -1);
dfs2(0, -1);
return ans;
}
void dfs(int node, int parent) {
for (int child : graph[node]) {
if (child != parent) {
dfs(child, node);
count[node] += count[child];
ans[node] += ans[child] + count[child];
}
}
}
void dfs2(int node, int parent) {
for (int child : graph[node]) {
if (child != parent) {
ans[child] = ans[node] - count[child] + N - count[child];
dfs2(child, node);
}
}
}
};
Ставь 👍 и забирай 📚 Базу знаний | 260 |
| 6 | Задача: 647. Palindromic Substrings
Сложность: medium
Если задана строка s, верните количество палиндромных подстрок в ней. Строка является палиндромом, если она читается так же, как задом наперед. Подстрока - это непрерывная последовательность символов в строке.
Пример:
Input: s = "abc"
Output: 3
👨💻 Алгоритм:
1⃣Инициализируйте счетчик для подсчета палиндромных подстрок.
2⃣Для каждой позиции в строке используйте два метода расширения: один для палиндромов нечетной длины и один для палиндромов четной длины.
3⃣Расширяйте от центра, проверяя, является ли подстрока палиндромом, и увеличивайте счетчик, если условие выполняется.
😎 Решение:
int expandAroundCenter(const string& s, int left, int right) {
int count = 0;
while (left >= 0 && right < s.length() && s[left] == s[right]) {
count++;
left--;
right++;
}
return count;
}
int countSubstrings(string s) {
int totalCount = 0;
for (int i = 0; i < s.length(); i++) {
totalCount += expandAroundCenter(s, i, i);
totalCount += expandAroundCenter(s, i, i + 1);
}
return totalCount;
}
Ставь 👍 и забирай 📚 Базу знаний | 354 |
| 7 | Задача: 37. Sudoku Solver
Сложность: hard
Напишите программу, которая решает судоку, заполняя пустые клетки, соблюдая правила: цифры от 1 до 9 должны встречаться ровно один раз в каждой строке, столбце и каждом из девяти 3×3 блоков.
Пример:
Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
👨💻 Алгоритм:
1⃣Создаем матрицы для отслеживания наличия цифр 1–9 в строках, столбцах и блоках 3×3. Заполняем их по уже заданным цифрам на доске.
2⃣Запускаем рекурсивную функцию backtrack, которая ищет пустые клетки и пытается поместить туда цифры от 1 до 9, проверяя допустимость по строке, столбцу и блоку.
3⃣Если дошли до конца доски — судоку решено. Иначе откатываемся (backtrack) и пробуем другие варианты.
😎 Решение:
class Solution {
int n = 3;
int N = n * n;
std::vector<std::vector<int>> rows, cols, boxes;
std::vector<std::vector<char>> board;
bool sudoku_solved = false;
public:
Solution() : rows(N, std::vector<int>(N + 1, 0)), cols(N, std::vector<int>(N + 1, 0)), boxes(N, std::vector<int>(N + 1, 0)) {}
bool could_place(int d, int row, int col) {
int idx = (row / n) * n + col / n;
return rows[row][d] == 0 && cols[col][d] == 0 && boxes[idx][d] == 0;
}
void place_or_remove(int d, int row, int col, bool place) {
int idx = (row / n) * n + col / n;
int delta = place ? 1 : -1;
rows[row][d] += delta;
cols[col][d] += delta;
boxes[idx][d] += delta;
board[row][col] = place ? d + '0' : '.';
}
void backtrack(int row = 0, int col = 0) {
if (col == N) col = 0, row++;
if (row == N) {
sudoku_solved = true;
return;
}
if (board[row][col] == '.') {
for (int d = 1; d <= 9 && !sudoku_solved; d++) {
if (could_place(d, row, col)) {
place_or_remove(d, row, col, true);
backtrack(row, col + 1);
if (!sudoku_solved) place_or_remove(d, row, col, false);
}
}
} else
backtrack(row, col + 1);
}
void solveSudoku(std::vector<std::vector<char>>& in_board) {
board = in_board;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i][j] != '.') {
int d = board[i][j] - '0';
place_or_remove(d, i, j, true);
}
}
}
backtrack();
in_board = board;
}
};
Ставь 👍 и забирай 📚 Базу знаний | 315 |
| 8 | Задача: 33. Search in Rotated Sorted Array
Сложность: medium
Дан массив nums, отсортированный по возрастанию и повернутый на некотором неизвестном индексе. Необходимо найти индекс элемента target. Если он не найден — вернуть -1. Решение должно работать за O(log n).
Пример:
Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4
👨💻 Алгоритм:
1⃣Инициализируем границы бинарного поиска: left = 0, right = n-1.
2⃣В цикле проверяем значение в середине. Если совпадает с target — возвращаем индекс.
3⃣Определяем, какая половина массива отсортирована, и сужаем поиск к той части, где может находиться target.
😎 Решение:
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int m = (left + right) / 2;
if (nums[m] == target) {
return m;
}
if (nums[left] <= nums[m]) { // левая часть отсортирована
if (nums[left] <= target && target < nums[m]) {
right = m - 1;
} else {
left = m + 1;
}
} else { // правая часть отсортирована
if (nums[m] < target && target <= nums[right]) {
left = m + 1;
} else {
right = m - 1;
}
}
}
return -1;
}
};
Ставь 👍 и забирай 📚 Базу знаний | 299 |
| 9 | 🔥 Скрытые вакансии с удаленной работой для C/C++ разработчика, которые нигде больше не публикуются. Напрямую от компаний, с контактами рекрутеров.
🔹 C/C++ Jobs | Вакансии
🔸 Все каналы с вакансиями | 329 |
| 10 | Задача: 40. Combination Sum II
Сложность: medium
Дан массив candidates и число target. Найдите все уникальные комбинации, где сумма элементов равна target. Каждое число можно использовать только один раз.
Пример:
Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
👨💻 Алгоритм:
1⃣Отсортировать и подсчитать количество каждого уникального элемента, чтобы избежать дубликатов.
2⃣Запустить рекурсивный backtrack, на каждом шаге выбирая доступный элемент, уменьшая его частоту и остаток target.
3⃣Если remain == 0 — сохранить комбинацию; иначе — откатить шаг (уменьшение глубины, восстановление частоты и удаление элемента из комбинации).
😎 Решение:
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> results;
vector<int> comb;
map<int, int> counter;
for (int candidate : candidates) {
counter[candidate]++;
}
vector<pair<int, int>> counterList(counter.begin(), counter.end());
backtrack(comb, target, 0, counterList, results);
return results;
}
private:
void backtrack(vector<int>& comb, int remain, int curr,
vector<pair<int, int>>& counter,
vector<vector<int>>& results) {
if (remain == 0) {
results.push_back(comb);
return;
} else if (remain < 0) {
return;
}
for (int nextCurr = curr; nextCurr < counter.size(); ++nextCurr) {
auto& [candidate, freq] = counter[nextCurr];
if (freq == 0) continue;
comb.push_back(candidate);
--freq;
backtrack(comb, remain - candidate, nextCurr, counter, results);
++freq;
comb.pop_back();
}
}
};
Ставь 👍 и забирай 📚 Базу знаний | 334 |
| 11 | Задача: 1014. Best Sightseeing Pair
Сложность: easy
Вам дан целочисленный массив values, в котором values[i] представляет собой значение i-й достопримечательности. Две достопримечательности i и j имеют расстояние j - i между собой. Оценка пары (i < j) достопримечательностей равна values[i] + values[j] + i - j: сумма значений достопримечательностей минус расстояние между ними. Возвращается максимальная оценка пары достопримечательностей.
Пример:
Input: values = [8,1,5,2,6]
Output: 11
👨💻 Алгоритм:
1⃣Инициализация переменных:
Инициализируйте переменную max_score для хранения максимальной оценки пары.
Инициализируйте переменную max_i_plus_value для хранения максимального значения выражения values[i] + i при проходе по массиву.
2⃣Проход по массиву:
Пройдитесь по массиву начиная с первого элемента и для каждого элемента values[j] вычислите текущую оценку пары как values[j] - j + max_i_plus_value.
Обновите значение max_score, если текущая оценка больше.
Обновите значение max_i_plus_value, если текущий элемент values[j] + j больше предыдущего max_i_plus_value.
3⃣Возврат результата:
Верните значение max_score как максимальную оценку пары достопримечательностей.
😎 Решение:
class Solution {
public:
int maxScoreSightseeingPair(vector<int>& values) {
int max_score = 0;
int max_i_plus_value = values[0];
for (int j = 1; j < values.size(); ++j) {
max_score = max(max_score, max_i_plus_value + values[j] - j);
max_i_plus_value = max(max_i_plus_value, values[j] + j);
}
return max_score;
}
};
Ставь 👍 и забирай 📚 Базу знаний | 262 |
| 12 | Задача: 1034. Coloring A Border
Сложность: medium
Вам дана целочисленная матричная сетка m x n и три целых числа row, col и color. Каждое значение в сетке представляет собой цвет квадрата сетки в данном месте. Два квадрата называются смежными, если они находятся рядом друг с другом в любом из 4 направлений. Два квадрата принадлежат одному связанному компоненту, если они имеют одинаковый цвет и являются смежными.
Граница связанного компонента - это все квадраты в связанном компоненте, которые либо смежны (по крайней мере) с квадратом, не входящим в компонент, либо находятся на границе сетки (в первой или последней строке или столбце). Вы должны окрасить границу связанного компонента, содержащего квадрат grid[row][col], в цвет. Верните конечную сетку.
Пример:
Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]
👨💻 Алгоритм:
1⃣Поиск связанного компонента:
Используйте поиск в глубину (DFS) или поиск в ширину (BFS), чтобы найти все клетки, принадлежащие связанному компоненту, содержащему клетку grid[row][col].
Запомните все клетки, которые принадлежат этому компоненту.
2⃣Определение границ компонента:
Для каждой клетки в связанном компоненте проверьте, является ли она границей. Клетка является границей, если она находится на краю сетки или если хотя бы одна из её соседних клеток не принадлежит связанному компоненту или имеет другой цвет.
3⃣Окрашивание границы:
Измените цвет всех клеток, являющихся границами, на заданный цвет.
😎 Решение:
class Solution {
public:
vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
int m = grid.size(), n = grid[0].size();
int original_color = grid[row][col];
vector<vector<bool>> visited(m, vector<bool>(n, false));
vector<pair<int, int>> borders;
function<void(int, int)> dfs = [&](int r, int c) {
visited[r][c] = true;
bool is_border = false;
for (auto [dr, dc] : vector<pair<int, int>>{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
if (!visited[nr][nc]) {
if (grid[nr][nc] == original_color) {
dfs(nr, nc);
} else {
is_border = true;
}
}
} else {
is_border = true;
}
}
if (is_border || r == 0 || r == m - 1 || c == 0 || c == n - 1) {
borders.emplace_back(r, c);
}
};
dfs(row, col);
for (auto [r, c] : borders) {
grid[r][c] = color;
}
return grid;
}
};
Ставь 👍 и забирай 📚 Базу знаний | 204 |
| 13 | Задача: 527. Word Abbreviation
Сложность: hard
Дано массив уникальных строк words, верните минимально возможные сокращения для каждого слова.
Правила сокращения строки следующие:
Первоначальное сокращение для каждого слова: первый символ, затем количество символов между первым и последним символом, затем последний символ.
Если более одного слова имеют одинаковое сокращение, выполните следующее:
Увеличьте префикс (символы в первой части) каждого из их сокращений на 1.
Например, начнем с слов ["abcdef", "abndef"], оба изначально сокращены как "a4f". Последовательность операций будет следующей: ["a4f", "a4f"] -> ["ab3f", "ab3f"] -> ["abc2f", "abn2f"].
Эта операция повторяется до тех пор, пока каждое сокращение не станет уникальным.
В конце, если сокращение не сделало слово короче, оставьте его в исходном виде.
Пример:
Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]
👨💻 Алгоритм:
1⃣ Инициализация и создание начальных сокращений:
Создайте массив для хранения сокращений и массив для отслеживания длины префикса каждого слова.
Для каждого слова создайте начальное сокращение с использованием первого символа, количества символов между первым и последним символом и последнего символа.
2⃣ Обработка коллизий:
Для каждого слова проверьте, не совпадает ли его сокращение с уже существующими сокращениями.
Если сокращение не уникально, увеличьте длину префикса и повторите проверку.
3⃣ Возврат результата:
Верните окончательные сокращения для каждого слова, убедившись, что они минимально возможны и уникальны.
😎 Решение:
class Solution {
public:
vector<string> wordsAbbreviation(vector<string>& words) {
int n = words.size();
vector<string> ans(n);
vector<int> prefix(n, 0);
for (int i = 0; i < n; ++i)
ans[i] = abbrev(words[i], 0);
for (int i = 0; i < n; ++i) {
while (true) {
unordered_set<int> dupes;
for (int j = i + 1; j < n; ++j) {
if (ans[i] == ans[j])
dupes.insert(j);
}
if (dupes.empty()) break;
dupes.insert(i);
for (int k : dupes) {
ans[k] = abbrev(words[k], ++prefix[k]);
}
}
}
return ans;
}
private:
string abbrev(const string& word, int i) {
int n = word.size();
if (n - i <= 3) return word;
return word.substr(0, i + 1) + to_string(n - i - 2) + word.back();
}
};
Ставь 👍 и забирай 📚 Базу знаний | 180 |
| 14 | Задача: 952. Largest Component Size by Common Factor
Сложность: hard
Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае.
Пример:
Input: nums = [4,6,15,35]
Output: 4
👨💻 Алгоритм:
1⃣Построить граф, в котором узлы представляют числа из массива, а ребра между узлами существуют, если два числа имеют общий делитель больше 1.
2⃣Использовать алгоритм Union-Find для объединения узлов в связные компоненты.
Для каждого числа в массиве nums найти его простые делители и использовать их для объединения узлов.
3⃣Найти размер наибольшей связной компоненты.
😎 Решение:
class Solution {
public:
int largestComponentSize(vector<int>& nums) {
unordered_map<int, int> parent;
unordered_map<int, int> rank;
for (int num : nums) {
parent[num] = num;
rank[num] = 0;
}
function<int(int)> find = [&](int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
};
auto unionFind = [&](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]++;
}
}
};
auto primeFactors = [&](int n) {
unordered_set<int> factors;
int d = 2;
while (d * d <= n) {
while (n % d == 0) {
factors.insert(d);
n /= d;
}
d++;
}
if (n > 1) {
factors.insert(n);
}
return factors;
};
unordered_map<int, vector<int>> primeToIndex;
for (int num : nums) {
auto primes = primeFactors(num);
for (int prime : primes) {
primeToIndex[prime].push_back(num);
}
}
for (const auto& primes : primeToIndex) {
for (int i = 1; i < primes.second.size(); i++) {
unionFind(primes.second[0], primes.second[i]);
}
}
unordered_map<int, int> size;
for (int num : nums) {
int root = find(num);
size[root]++;
}
int maxSize = 0;
for (const auto& [key, value] : size) {
maxSize = max(maxSize, value);
}
return maxSize;
}
};
Ставь 👍 и забирай 📚 Базу знаний | 205 |
| 15 | Задача: 474. Ones and Zeroes
Сложность: medium
Дан массив двоичных строк strs и два целых числа m и n.
Верните размер наибольшего подмножества strs, такого что в подмножестве содержится не более m нулей и n единиц.
Множество x является подмножеством множества y, если все элементы множества x также являются элементами множества y.
Пример:
Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.
👨💻 Алгоритм:
1⃣Рассматриваем все возможные подмножества, прерывая цикл, если количество нулей превышает m или количество единиц превышает n.
2⃣Считаем количество нулей и единиц в каждом подмножестве.
3⃣Выбираем наибольшее подмножество, соответствующее условиям, и возвращаем его размер.
😎 Решение:
#include <vector>
#include <string>
#include <algorithm>
class Solution {
public:
int findMaxForm(std::vector<std::string>& strs, int m, int n) {
int maxlen = 0;
for (int i = 0; i < (1 << strs.size()); ++i) {
int zeroes = 0, ones = 0, len = 0;
for (int j = 0; j < 32; ++j) {
if ((i & (1 << j)) != 0) {
auto count = countZeroesOnes(strs[j]);
zeroes += count[0];
ones += count[1];
if (zeroes > m || ones > n)
break;
++len;
}
}
if (zeroes <= m && ones <= n)
maxlen = std::max(maxlen, len);
}
return maxlen;
}
std::vector<int> countZeroesOnes(const std::string& s) {
std::vector<int> c(2, 0);
for (char ch : s) {
++c[ch - '0'];
}
return c;
}
};
Ставь 👍 и забирай 📚 Базу знаний | 222 |
| 16 | Задача: 998. Maximum Binary Tree II
Сложность: medium
Максимальное дерево - это дерево, в котором каждый узел имеет значение большее, чем любое другое значение в его поддереве. Вам дан корень максимального двоичного дерева и целое число val. Как и в предыдущей задаче, данное дерево было построено из списка a (root = Construct(a)) рекурсивно с помощью следующей процедуры Construct(a): Если a пусто, верните null.
В противном случае пусть a[i] - наибольший элемент a. Создайте корневой узел со значением a[i]. Левым ребенком root будет Construct([a[0], a[1], ..., a[i - 1]]). Правым ребенком root будет Construct([a[i + 1], a[i + 2], ..., a[a.length])...., a[a.length - 1]]). Возвращаем root. Обратите внимание, что нам не было дано непосредственно a, а только корневой узел root = Construct(a). Предположим, что b - это копия a с добавленным к ней значением val. Гарантируется, что b имеет уникальные значения. Возвращаем Construct(b).
Пример:
Input: n = 2, trust = [[1,2]]
Output: 2
👨💻 Алгоритм:
1⃣Поиск места вставки:
Итерируйте через дерево, начиная с корня. Найдите место для вставки нового значения val так, чтобы дерево оставалось максимальным деревом. Если значение val больше, чем значение текущего узла, создайте новый узел с val и сделайте текущий узел его левым ребенком.
2⃣Вставка нового узла:
Если значение val меньше, чем значение текущего узла, продолжайте спускаться по правому поддереву, пока не найдете место для вставки.
3⃣Создание нового дерева:
После вставки нового узла убедитесь, что дерево сохраняет свои свойства максимального дерева.
😎 Решение:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* insertIntoMaxTree(TreeNode* root, int val) {
if (!root || val > root->val) {
TreeNode* newNode = new TreeNode(val);
newNode->left = root;
return newNode;
}
root->right = insertIntoMaxTree(root->right, val);
return root;
}
};
Ставь 👍 и забирай 📚 Базу знаний | 250 |
| 17 | Задача: 32. Longest Valid Parentheses
Сложность: hard
Учитывая строку, содержащую только символы «(» и «)», верните длину самой длинной допустимой (правильно сформированной) подстроки скобок.
Пример:
Input: s = "(()" Output: 2
👨💻 Алгоритм:
1⃣Используем стек для хранения индексов, начальное значение — -1.
2⃣Проходим по строке: если '(', кладем индекс в стек, если ')' — извлекаем элемент.
3⃣Если после извлечения стек пуст — кладем текущий индекс, иначе — обновляем максимум длины как i - stack.top().
😎 Решение:
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> stack;
int m = 0;
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.empty()) {
stack.push(i);
} else {
m = max(m, (i - stack.top()));
}
}
}
return m;
}
};
Ставь 👍 и забирай 📚 Базу знаний | 285 |
| 18 | Задача: 1365. How Many Numbers Are Smaller Than the Current Number
Сложность: easy
Дан массив nums. Для каждого элемента nums[i] определите, сколько чисел в массиве меньше его. То есть, для каждого nums[i] вам нужно посчитать количество допустимых j, таких что j != i и nums[j] < nums[i].
Верните ответ в виде массива.
Пример:
Input: nums = [6,5,4,8]
Output: [2,1,0,3]
👨💻 Алгоритм:
1⃣Создание копии и сортировка массива:
Создайте отсортированную копию массива nums, чтобы легко находить количество элементов, меньших текущего.
2⃣Поиск индекса каждого элемента:
Для каждого элемента nums[i] найдите его индекс в отсортированной копии массива. Этот индекс указывает количество элементов, меньших nums[i].
3⃣Формирование ответа:
Сформируйте массив ответов, где каждый элемент будет соответствовать количеству чисел, меньших текущего.
😎 Решение:
#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<int> smallerNumbersThanCurrent(std::vector<int>& nums) {
std::vector<int> sortedNums = nums;
std::sort(sortedNums.begin(), sortedNums.end());
std::vector<int> result;
for (int num : nums) {
result.push_back(std::find(sortedNums.begin(), sortedNums.end(), num) - sortedNums.begin());
}
return result;
}
};
Ставь 👍 и забирай 📚 Базу знаний | 337 |
| 19 | Задача: 1024. Video Stitching
Сложность: medium
Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается массивом clips, где clips[i] = [starti, endi] указывает, что i-й клип начинается в starti и заканчивается в endi. Мы можем произвольно разрезать эти клипы на сегменты. Например, клип [0, 7] может быть разрезан на сегменты [0, 1] + [1, 3] + [3, 7]. Верните минимальное количество клипов, необходимое для того, чтобы мы могли разрезать клипы на сегменты, охватывающие все спортивное событие [0, время]. Если задача невыполнима, верните -1.
Пример:
Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3
👨💻 Алгоритм:
1⃣Сортировка клипов:
Отсортируйте клипы по начальным значениям. Если начальные значения равны, отсортируйте по конечным значениям в убывающем порядке.
2⃣Выбор клипов:
Используйте жадный алгоритм для выбора клипов. Начните с начальной точки 0 и двигайтесь вперед, выбирая клип, который может покрыть наибольший диапазон.
Если обнаруживается, что начальная точка текущего клипа больше текущей позиции, это означает, что клипы не могут покрыть промежуток, и нужно вернуть -1.
3⃣Проверка покрытия:
Продолжайте процесс, пока не покроете весь диапазон от 0 до T. Если в конце процесса достигнута или превышена точка T, верните количество использованных клипов, иначе верните -1.
😎 Решение:
class Solution {
public:
int videoStitching(vector<vector<int>>& clips, int T) {
sort(clips.begin(), clips.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
});
int end = -1, end2 = 0, res = 0;
for (const auto& clip : clips) {
if (end2 >= T || clip[0] > end2) break;
if (end < clip[0] && clip[0] <= end2) {
res++;
end = end2;
}
end2 = max(end2, clip[1]);
}
return end2 >= T ? res : -1;
}
};
Ставь 👍 и забирай 📚 Базу знаний | 330 |
| 20 | Задача: 869. Reordered Power of 2
Сложность: medium
Дано целое число n. Мы можем переставить цифры числа в любом порядке (включая исходный порядок), при этом ведущая цифра не должна быть нулем.
Верните true, если и только если мы можем сделать это так, чтобы полученное число было степенью двойки.
Пример:
Input: n = 1
Output: true
👨💻 Алгоритм:
1⃣Сгенерируйте все перестановки цифр числа, размещая любую цифру на первой позиции (start = 0), затем любую из оставшихся цифр на второй позиции (start = 1) и так далее. В Python можно использовать встроенную функцию itertools.permutations.
2⃣Проверьте, что перестановка представляет собой степень двойки, убедившись, что в перестановке нет ведущего нуля, и удаляя все множители 2. Если результат равен 1 (то есть, он не содержал других множителей, кроме 2), то это была степень двойки. В Python можно использовать проверку bin(N).count('1') == 1.
3⃣Верните true, если хотя бы одна перестановка является степенью двойки, иначе верните false.
😎 Решение:
class Solution {
public:
bool reorderedPowerOf2(int N) {
string A = to_string(N);
sort(A.begin(), A.end());
for (int i = 0; i < 30; ++i) {
string B = to_string(1 << i);
sort(B.begin(), B.end());
if (A == B) return true;
}
return false;
}
};
Ставь 👍 и забирай 📚 Базу знаний | 290 |
