اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
C/C++ | LeetCode
رفتن به کانال در Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+zYofcX2VLTM3MGMy Вопросы собесов t.me/+BTbqlW1VbIFmYmVi Вакансии t.me/+za2mJYs4riAzMzFi
نمایش بیشتر3 259
مشترکین
+424 ساعت
-17 روز
-430 روز
آرشیو پست ها
3 259
Задача: 1535. Find the Winner of an Array Game
Сложность: medium
Дан целочисленный массив
arr из различных целых чисел и целое число k.
Игра будет проводиться между первыми двумя элементами массива (т.е. arr[0] и arr[1]). В каждом раунде игры мы сравниваем arr[0] с arr[1], большее число побеждает и остается на позиции 0, а меньшее число перемещается в конец массива. Игра заканчивается, когда одно число выигрывает k подряд раундов.
Верните число, которое выиграет игру.
Гарантируется, что у игры будет победитель.
Пример:
Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round | arr | winner | win_count
1 | [2,1,3,5,4,6,7] | 2 | 1
2 | [2,3,5,4,6,7,1] | 3 | 1
3 | [3,5,4,6,7,1,2] | 5 | 1
4 | [5,4,6,7,1,2,3] | 5 | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.class Solution {
public:
int getWinner(vector<int>& arr, int k) {
int maxElement = arr[0];
queue<int> queue;
for (int i = 1; i < arr.size(); i++) {
maxElement = max(maxElement, arr[i]);
queue.push(arr[i]);
}
int curr = arr[0];
int winstreak = 0;
while (!queue.empty()) {
int opponent = queue.front();
queue.pop();
if (curr > opponent) {
queue.push(opponent);
winstreak++;
} else {
queue.push(curr);
curr = opponent;
winstreak = 1;
}
if (winstreak == k || curr == maxElement) {
return curr;
}
}
return -1;
}
};3 259
Задача: 243. Shortest Word Distance
Сложность: easy
Дан массив строк и два слова. Нужно вернуть минимальное расстояние между ними в массиве.
Пример:
Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice" Output: 3👨💻 Алгоритм: 1⃣Проходим по массиву один раз, запоминая последние индексы, где встречались word1 и word2 2⃣При каждом новом вхождении одного из слов, если другое уже найдено — обновляем минимальное расстояние 3⃣Возвращаем минимальное расстояние 😎 Решение:
class Solution {
public:
int shortestDistance(vector<string>& words, string word1, string word2) {
int idx1 = -1, idx2 = -1, minDist = words.size();
for (int i = 0; i < words.size(); ++i) {
if (words[i] == word1) idx1 = i;
else if (words[i] == word2) idx2 = i;
if (idx1 != -1 && idx2 != -1) {
minDist = min(minDist, abs(idx1 - idx2));
}
}
return minDist;
}
};3 259
Задача: 484. Find Permutation
Сложность: medium
Перестановка perm из n целых чисел всех чисел в диапазоне [1, n] может быть представлена в виде строки s длиной n - 1, где:
s[i] == 'I', если perm[i] < perm[i + 1], и
s[i] == 'D', если perm[i] > perm[i + 1].
Дана строка s, восстановите лексикографически наименьшую перестановку perm и верните её.
Пример:
Input: s = "I" Output: [1,2] Explanation: [1,2] is the only legal permutation that can represented by s, where the number 1 and 2 construct an increasing relationship.👨💻 Алгоритм: 1⃣Инициализация Создайте пустой стек stack. Создайте пустой список result для хранения конечной перестановки. 2⃣Для каждого числа i Если текущий символ в строке s равен 'D', добавьте i в стек. Если текущий символ в строке s равен 'I', добавьте i в стек, затем извлеките все элементы из стека и добавьте их в result. 3⃣Завершение Добавьте n в стек и извлеките все элементы из стека, добавив их в result. Верните список result, который представляет лексикографически наименьшую перестановку. 😎 Решение:
class Solution {
public:
vector<int> findPermutation(string s) {
vector<int> res(s.length() + 1);
stack<int> stack;
int j = 0;
for (int i = 1; i <= s.length(); i++) {
if (s[i - 1] == 'I') {
stack.push(i);
while (!stack.empty()) {
res[j++] = stack.top();
stack.pop();
}
} else {
stack.push(i);
}
}
stack.push(s.length() + 1);
while (!stack.empty()) {
res[j++] = stack.top();
stack.pop();
}
return res;
}
};3 259
Задача: 21. Merge Two Sorted Lists
Сложность: easy
Вам даны заголовки двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем сращивания узлов первых двух списков. Возвращает заголовок объединенного связанного списка.
Пример:
Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"] Output: "steps"👨💻 Алгоритм: 1⃣Создаем фиктивный узел dummy и указатель cur, указывающий на него. 2⃣Пока list1 и list2 не пусты — сравниваем значения, добавляем меньший узел в результат, передвигаем соответствующий указатель. 3⃣После выхода из цикла, добавляем оставшиеся элементы от одного из списков (если остались). 😎 Решение:
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while (list1 && list2) {
if (list1->val > list2->val) {
cur->next = list2;
list2 = list2->next;
} else {
cur->next = list1;
list1 = list1->next;
}
cur = cur->next;
}
cur->next = list1 ? list1 : list2;
return dummy->next;
}
};3 259
Задача: 1254. Number of Closed Islands
Сложность: medium
Дана двумерная сетка, состоящая из 0 (земля) и 1 (вода).Остров - это максимальная 4-направленно связная группа из 0s, а закрытый остров - это остров, полностью (слева, сверху, справа, снизу) окруженный 1s. Верните количество закрытых островов.
Пример:
Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]] Output: 2👨💻 Алгоритм: 1⃣Пройдите по границам сетки и с помощью поиска в глубину (DFS) или поиска в ширину (BFS) замените все связанные земли (0) на воду (1). 2⃣Пройдите по всей сетке, используя DFS или BFS для поиска всех оставшихся островов (групп 0) 3⃣Подсчитайте количество таких островов. 😎 Решение:
class Solution {
public:
int closedIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j] == 0) {
dfs(grid, i, j);
}
}
}
int count = 0;
for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if (grid[i][j] == 0) {
dfs(grid, i, j);
count++;
}
}
}
return count;
}
private:
void dfs(vector<vector<int>>& grid, int x, int y) {
if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] == 1) {
return;
}
grid[x][y] = 1;
dfs(grid, x + 1, y);
dfs(grid, x - 1, y);
dfs(grid, x, y + 1);
dfs(grid, x, y - 1);
}
};3 259
Задача: 188. Best Time to Buy and Sell Stock IV
Сложность: hard
Дан массив целых чисел prices, где prices[i] — цена акции в i-й день, и целое число k.
Найдите максимальную прибыль, которую можно получить, совершив не более k транзакций (одна транзакция = покупка + продажа).
Нельзя участвовать в нескольких транзакциях одновременно — нужно сначала продать акцию, прежде чем покупать новую.
Пример:
Input: k = 2, prices = [2,4,1] Output: 2👨💻 Алгоритм: 1⃣Инициализация DP массива Создаем 3D массив dp[i][j][l], где: i — день, j — количество доступных транзакций, l — держим акцию (1) или нет (0). Базовые значения: dp[0][0][0] = 0, dp[0][1][1] = -prices[0]. 2⃣Переходы состояний dp[i][j][0] = max(dp[i−1][j][0], dp[i−1][j][1] + prices[i]) — максимальная прибыль без акции. dp[i][j][1] = max(dp[i−1][j][1], dp[i−1][j−1][0] - prices[i]) — максимальная прибыль с акцией. 3⃣Оптимизация при большом k Если k * 2 >= n, можно совершать сделки каждый день — используем жадный подсчет всех выгодных дней. Решение:
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
if (n <= 0 || k <= 0) {
return 0;
}
if (k * 2 >= n) {
int res = 0;
for (int i = 1; i < n; i++) {
res += max(0, prices[i] - prices[i - 1]);
}
return res;
}
vector<vector<vector<int>>> dp(
n, vector<vector<int>>(k + 1, vector<int>(2, 0)));
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++) {
dp[i][j][0] = INT_MIN / 2;
dp[i][j][1] = INT_MIN / 2;
}
}
dp[0][0][0] = 0;
dp[0][1][1] = -prices[0];
for (int i = 1; i < n; i++) {
for (int j = 0; j <= k; j++) {
dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
if (j > 0) {
dp[i][j][1] =
max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
}
}
}
int res = 0;
for (int j = 0; j <= k; j++) {
res = max(res, dp[n - 1][j][0]);
}
return res;
}
};3 259
Задача: 1422. Maximum Score After Splitting a String
Сложность: easy
Дана строка s из нулей и единиц. Верните максимальное количество очков после разбиения строки на две непустые подстроки (т.е. левую подстроку и правую подстроку).
Количество очков после разбиения строки - это количество нулей в левой подстроке плюс количество единиц в правой подстроке.
Пример:
Input: s = "011101" Output: 5 Explanation: All possible ways of splitting s into two non-empty substrings are: left = "0" and right = "11101", score = 1 + 4 = 5 left = "01" and right = "1101", score = 1 + 3 = 4 left = "011" and right = "101", score = 1 + 2 = 3 left = "0111" and right = "01", score = 1 + 1 = 2 left = "01110" and right = "1", score = 2 + 1 = 3👨💻 Алгоритм: 1⃣Посчитайте количество единиц в строке и инициализируйте счётчики нулей и максимального значения. 2⃣Перебирайте символы строки до предпоследнего символа, обновляя счётчики нулей и единиц. 3⃣Обновляйте максимальное значение, если текущая сумма нулей и единиц больше предыдущего максимума. 😎 Решение:
class Solution {
public:
int maxScore(string s) {
int ones = count(s.begin(), s.end(), '1');
int zeros = 0, ans = 0, countOnes = ones;
for (int i = 0; i < s.length() - 1; ++i) {
if (s[i] == '1') {
countOnes--;
} else {
zeros++;
}
ans = max(ans, zeros + countOnes);
}
return ans;
}
};3 259
Задача: 233. Number of Digit One
Сложность: hard
Дано целое число n, посчитайте общее количество единиц, встречающихся во всех неотрицательных числах, меньших или равных n.
Пример:
Input: n = 13 Output: 6👨💻 Алгоритм: 1⃣Итерация по степеням 10: Итеративно увеличивайте значение i от 1 до n, увеличивая i в 10 раз на каждом шаге. Это позволяет анализировать каждую цифру числа n. 2⃣Подсчет групповых единиц: Для каждой итерации добавляйте (n / (i * 10)) * i к счетчику countr, что представляет собой количество единиц, встречающихся в группах размера i после каждого интервала (i * 10). 3⃣Добавление дополнительных единиц: Для каждой итерации добавляйте min(max((n % (i * 10)) - i + 1, 0), i) к счетчику countr, что представляет собой дополнительные единицы, зависящие от цифры на позиции i. 😎 Решение:
int countDigitOne(int n) {
int countr = 0;
for (long long i = 1; i <= n; i *= 10) {
long long divider = i * 10;
countr += (n / divider) * i + std::min(std::max(n % divider - i + 1, 0LL), i);
}
return countr;
}3 259
Задача: 859. Buddy Strings
Сложность: easy
Даны две строки s и goal. Верните true, если вы можете поменять местами две буквы в s так, чтобы результат был равен goal, в противном случае верните false.
Обмен буквами определяется как взятие двух индексов i и j (нумерация с 0), таких что i != j, и обмен символов в s[i] и s[j].
Например, обмен символов на индексах 0 и 2 в строке "abcd" приводит к "cbad".
Пример:
Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.class Solution {
public:
bool buddyStrings(string s, string goal) {
if (s.size() != goal.size()) return false;
if (s == goal) {
vector<int> freq(26, 0);
for (char ch : s) {
if (++freq[ch - 'a'] > 1) return true;
}
return false;
}
int firstIndex = -1, secondIndex = -1;
for (int i = 0; i < s.size(); ++i) {
if (s[i] != goal[i]) {
if (firstIndex == -1) firstIndex = i;
else if (secondIndex == -1) secondIndex = i;
else return false;
}
}
return secondIndex != -1 &&
s[firstIndex] == goal[secondIndex] &&
s[secondIndex] == goal[firstIndex];
}
};3 259
Задача: 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 259
Сегодня последний день, когда можно приобрести пожизненный PRO тариф easyoffer
Акция до 20 февраля 00:00
Покупаешь сейчас один раз — пользуешься всю жизнь без лимита, включая все будущие функции.
👉 Смотри подробности тарифа и покупай на https://easyoffer.ru/
3 259
Задача: 1006. Clumsy Factorial
Сложность: medium
Факториал целого положительного числа n - это произведение всех целых положительных чисел, меньших или равных n. Например, факториал(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1.
Мы составляем неуклюжий факториал, используя целые числа в порядке убывания, заменяя операции умножения на фиксированную последовательность операций с умножением "*", делением "/", сложением "+" и вычитанием "-" в этом порядке. Например, clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1. Однако эти операции по-прежнему применяются с использованием обычного порядка операций арифметики. Мы выполняем все шаги умножения и деления перед шагами сложения и вычитания, а шаги умножения и деления выполняются слева направо. Кроме того, деление, которое мы используем, является делением с полом, так что 10 * 9 / 8 = 90 / 8 = 11. Учитывая целое число n, верните неуклюжий факториал n.
Пример:
Input: nums = [4,2,3], k = 1 Output: 5👨💻 Алгоритм: 1⃣Инициализация переменных и обработка первых трех чисел: Создайте переменные для хранения результата и текущего значения. Если n меньше или равен 3, обработайте случай отдельно, выполняя операции в порядке убывания, и верните результат. 2⃣Выполнение операций в цикле: Создайте цикл, который будет обрабатывать числа от n до 1 в порядке убывания. В цикле выполняйте операции *, /, +, и - последовательно. Обновляйте текущий результат на каждом шаге в зависимости от остатка от деления текущего индекса на 4. 3⃣Учет оставшихся операций и возврат результата: После завершения цикла добавьте или вычтите оставшиеся числа (если есть) к результату. Верните окончательный результат. 😎 Решение:
class Solution {
public:
int clumsy(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
if (n == 2) return 2 * 1;
if (n == 3) return 3 * 2 / 1;
int res = n * (n - 1) / (n - 2);
n -= 3;
if (n > 0) res += n--;
while (n > 0) {
res -= n * (n - 1) / (n - 2);
n -= 3;
if (n > 0) res += n--;
}
return res;
}
};3 259
Задача: 950. Reveal Cards In Increasing Order
Сложность: medium
Вам дана колода целочисленных массивов. Имеется колода карт, в которой каждая карта имеет уникальное целое число. Целое число на i-й карте - deck[i]. Вы можете упорядочить колоду в любом порядке. Изначально все карты в одной колоде лежат лицевой стороной вниз (нераскрытыми). Вы будете выполнять следующие действия несколько раз, пока все карты не будут раскрыты: возьмите верхнюю карту колоды, раскройте ее и выньте из колоды. Если в колоде еще есть карты, положите следующую верхнюю карту колоды на дно колоды. Если еще есть нераскрытые карты, вернитесь к шагу 1. В противном случае остановитесь. Верните порядок колоды, при котором карты раскрываются в порядке возрастания. Обратите внимание, что первая запись в ответе считается верхом колоды.
Пример:
Input: deck = [17,13,11,2,3,5,7] Output: [2,13,3,11,5,17,7]👨💻 Алгоритм: 1⃣Создать индексы карт в порядке, в котором они будут раскрываться. 2⃣Отсортировать колоду карт по возрастанию. 3⃣Заполнить результат раскрытия карт по ранее созданным индексам. 😎 Решение:
class Solution {
public:
vector<int> deckRevealedIncreasing(vector<int>& deck) {
int n = deck.size();
queue<int> index;
for (int i = 0; i < n; i++) {
index.push(i);
}
sort(deck.begin(), deck.end());
vector<int> result(n);
for (int card : deck) {
result[index.front()] = card;
index.pop();
if (!index.empty()) {
index.push(index.front());
index.pop();
}
}
return result;
}
};3 259
Завтра конец акции на возможность приобрести PRO тариф по цене одного года
Доступный функционал включает базы вопросов с собеседований, задач для live-coding, реальных интервью и тестовых заданий от топ-компаний, а также аналитику требований для резюме и тренажеры с режимом симуляции собеседования под конкретную компанию.
Акция до 20 февраля (включительно) на PRO-тариф. Покупаешь сейчас один раз — пользуешься всю жизнь без лимита, включая все будущие функции.
👉 Смотри подробности тарифа и покупай на https://easyoffer.ru/
3 259
Задача: 662. Maximum Width of Binary Tree
Сложность: medium
Дан корень бинарного дерева, верните максимальную ширину данного дерева.
Максимальная ширина дерева - это максимальная ширина среди всех уровней.
Ширина одного уровня определяется как расстояние между конечными узлами (самыми левыми и самыми правыми ненулевыми узлами), где нулевые узлы между конечными узлами, которые присутствовали бы в полном бинарном дереве, продолжающемся до этого уровня, также учитываются при вычислении длины.
Гарантируется, что ответ будет в диапазоне 32-битного знакового целого числа.
Пример:
Input: root = [1,3,2,5,3,null,9] Output: 4 Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).👨💻 Алгоритм: 1⃣Инициализация: Создайте очередь для хранения узлов и их позиций на уровне. Начните с корневого узла и его позиции 0. 2⃣Обработка каждого уровня: Для каждого уровня дерева получите его узлы и их позиции. Вычислите ширину уровня как разницу между максимальной и минимальной позициями плюс один. 3⃣Обновление максимальной ширины: Обновите максимальную ширину, если текущая ширина уровня больше. 😎 Решение:
#include <queue>
#include <utility>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
if (!root) return 0;
int maxWidth = 0;
std::queue<std::pair<TreeNode*, unsigned long long>> queue;
queue.push({root, 0});
while (!queue.empty()) {
int levelSize = queue.size();
unsigned long long firstPos = queue.front().second;
for (int i = 0; i < levelSize; i++) {
auto [node, pos] = queue.front();
queue.pop();
if (node->left) queue.push({node->left, 2 * pos});
if (node->right) queue.push({node->right, 2 * pos + 1});
}
maxWidth = std::max(maxWidth, queue.back().second - firstPos + 1);
}
return maxWidth;
}
};3 259
Задача: 905. Sort Array By Parity
Сложность: easy
Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию.
Пример:
Input: nums = [3,1,2,4] Output: [2,4,3,1]👨💻 Алгоритм: 1⃣Создать два списка: один для четных чисел, другой для нечетных. 2⃣Пройтись по массиву и добавить четные числа в один список, а нечетные в другой. 3⃣Объединить два списка и вернуть результат. 😎 Решение:
class Solution {
public:
vector<int> sortArrayByParity(vector<int>& nums) {
vector<int> evens, odds;
for (int num : nums) {
if (num % 2 == 0) {
evens.push_back(num);
} else {
odds.push_back(num);
}
}
evens.insert(evens.end(), odds.begin(), odds.end());
return evens;
}
};3 259
Задача: 1358. Number of Substrings Containing All Three Characters
Сложность: medium
Дана строка s, состоящая только из символов a, b и c.
Верните количество подстрок, содержащих хотя бы одно вхождение всех этих символов a, b и c.
Пример:
Input: s = "abc" Output: 1👨💻 Алгоритм: 1⃣Инициализация указателей и счетчиков: Создайте три указателя i, j, и count для отслеживания текущего положения в строке и подсчета подстрок. Используйте словарь для подсчета вхождений символов a, b, и c. 2⃣Расширение окна: Перемещайте правый указатель j по строке и увеличивайте счетчики символов в словаре. Как только все три символа (a, b, и c) присутствуют в текущем окне, начинайте уменьшать левый указатель i. 3⃣Уменьшение окна и подсчет подстрок: Для каждого сдвига i вправо, проверяйте наличие всех символов в текущем окне. Если все символы присутствуют, добавьте количество подстрок, заканчивающихся в позиции j, к общему счету. Сдвигайте i вправо до тех пор, пока условие выполнения не нарушится. Верните итоговое количество подстрок. 😎 Решение:
class Solution {
public:
int numberOfSubstrings(string s) {
int count = 0;
vector<int> charCount(3, 0);
int i = 0;
for (int j = 0; j < s.size(); j++) {
charCount[s[j] - 'a']++;
while (charCount[0] > 0 && charCount[1] > 0 && charCount[2] > 0) {
count += s.size() - j;
charCount[s[i] - 'a']--;
i++;
}
}
return count;
}
};3 259
Задача: 1218. Longest Arithmetic Subsequence of Given Difference
Сложность: medium
Дан массив целых чисел arr и целое число difference. Верните длину самой длинной подпоследовательности в arr, которая является арифметической последовательностью, так что разница между соседними элементами в подпоследовательности равна difference.
Подпоследовательность — это последовательность, которую можно получить из arr, удалив некоторые или ни одного элемента, не меняя порядок оставшихся элементов.
Пример:
Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2 Output: 4 Explanation: The longest arithmetic subsequence is [7,5,3,1].👨💻 Алгоритм: 1⃣Инициализируйте пустой хеш-таблицу dp и установите answer = 1. 2⃣Итеративно обработайте массив arr. Для каждого элемента arr[i]: Вычислите before_a, максимальную длину арифметической подпоследовательности, заканчивающейся на arr[i] - difference: - если arr[i] - difference существует в dp, установите before_a = dp[arr[i] - difference]. - в противном случае, установите before_a = 0. Установите dp[arr[i]] = before_a + 1, обновите answer как answer = max(answer, dp[arr[i]]). 3⃣Верните answer после завершения итерации. 😎 Решение:
class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
unordered_map<int, int> dp;
int answer = 1;
for (int a : arr) {
int beforeA = dp.count(a - difference) ? dp[a - difference] : 0;
dp[a] = beforeA + 1;
answer = max(answer, dp[a]);
}
return answer;
}
};3 259
Задача: 655. Print Binary Tree
Сложность: medium
Учитывая корень двоичного дерева, постройте строковую матрицу res с индексом 0 размером m x n, которая представляет собой форматированную раскладку дерева. Форматированная матрица должна быть построена по следующим правилам: высота дерева равна height, количество строк m должно быть равно height + 1. Количество столбцов n должно быть равно 2height+1 - 1. Поместите корневой узел в середину верхней строки (более формально, в позицию res[0][(n-1)/2]).
Для каждого узла, который был помещен в матрицу в позицию res[r][c], поместите его левого ребенка в res[r+1][c-2height-r-1], а правого - в res[r+1][c+2height-r-1]. Продолжайте этот процесс, пока не будут размещены все узлы дерева. Любые пустые ячейки должны содержать пустую строку "". Верните построенную матрицу res.
Пример:
Input: root = [1,2] Output: [["","1",""], ["2","",""]]👨💻 Алгоритм: 1⃣Найдите высоту дерева и определите размер матрицы (m x n). 2⃣Рекурсивно разместите узлы в матрице, начиная с корневого узла. 3⃣Верните заполненную матрицу. 😎 Решение:
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int findHeight(TreeNode* root) {
if (!root) return -1;
return 1 + max(findHeight(root->left), findHeight(root->right));
}
void fill(vector<vector<string>>& res, TreeNode* root, int r, int c, int height) {
if (!root) return;
res[r][c] = to_string(root->val);
if (root->left) {
fill(res, root->left, r + 1, c - (1 << (height - r - 1)), height);
}
if (root->right) {
fill(res, root->right, r + 1, c + (1 << (height - r - 1)), height);
}
}
vector<vector<string>> printTree(TreeNode* root) {
int height = findHeight(root);
int m = height + 1;
int n = (1 << (height + 1)) - 1;
vector<vector<string>> res(m, vector<string>(n, ""));
fill(res, root, 0, (n - 1) / 2, height);
return res;
}3 259
Пожизненная PRO подписка на easyoffer по цене одного года.
Акция до 20 февраля. Покупаешь сейчас один раз – пользуешься всю жизнь без лимита, включая все будущие функции.
Запланированные новые фичи на ближайшие пол года:
1. Агрегатор вакансий
2. Улучшение резюме, чтобы проходить ATS системы
3. Генерация уникального резюме и сопроводительного письма под вакансию
Покупай на https://easyoffer.ru/
