اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
C/C++ | LeetCode
رفتن به کانال در Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+zYofcX2VLTM3MGMy Вопросы собесов t.me/+BTbqlW1VbIFmYmVi Вакансии t.me/+za2mJYs4riAzMzFi
نمایش بیشتر3 249
مشترکین
-324 ساعت
-107 روز
-1530 روز
آرشیو پست ها
3 250
Осталось 3 часа до конца акции:
«Пожизненный PRO тариф — по цене 1 года»
Поиск работы отнимает силы, время и веру в себя, но не у тех кто использует easyoffer PRO. Успей сделать самую выгодную инвестицию в развитие своей карьеры.
Акция закончится уже сегодня 23 июня 23:59 по мск:
👉 https://easyoffer.ru/pro
3 250
Задача: 865. Smallest Subtree with all the Deepest Nodes
Сложность: medium
Дан корень бинарного дерева, глубина каждого узла — это кратчайшее расстояние до корня.
Верните наименьшее поддерево, которое содержит все самые глубокие узлы в исходном дереве.
Узел называется самым глубоким, если у него наибольшая возможная глубина среди всех узлов в дереве.
Поддерево узла — это дерево, состоящее из этого узла и всех его потомков.
Пример:
Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest nodes of the tree.
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.class Solution {
public:
TreeNode* subtreeWithAllDeepest(TreeNode* root) {
unordered_map<TreeNode*, int> depth = {{nullptr, -1}};
dfs(root, nullptr, depth);
int maxDepth = max_element(depth.begin(), depth.end(), [](const auto& a, const auto& b) {
return a.second < b.second;
})->second;
return answer(root, depth, maxDepth);
}
private:
void dfs(TreeNode* node, TreeNode* parent, unordered_map<TreeNode*, int>& depth) {
if (node) {
depth[node] = depth[parent] + 1;
dfs(node->left, node, depth);
dfs(node->right, node, depth);
}
}
TreeNode* answer(TreeNode* node, unordered_map<TreeNode*, int>& depth, int maxDepth) {
if (!node || depth[node] == maxDepth) return node;
TreeNode* L = answer(node->left, depth, maxDepth);
TreeNode* R = answer(node->right, depth, maxDepth);
return L && R ? node : L ? L : R;
}
};3 250
Последний день акции:
«Пожизненный PRO тариф — по цене 1 года»
🚀 PRO включает:
– Полный доступ ко всем грейдам и профессиям
– База live-coding задач и вопросов из технических собеседований с вероятностью их встречи
– Примеры лучших ответов от Senior разработчиков
– 1100+ записи реальных собеседований, в том числе в топовые компании (Сбер, Авито, Яндекс, WB, OZON, МТС и др.)
– База 400+ тестовых заданий от компаний.
– Автоотклики на вакансии в хедхантер
– Аналитика ТОП-требований из вакансий для лучшего написания резюме и прохождения ATS систем рекрутеров
– Генератор уникального резюме и CV под каждую вакансию
– Тренажеры подготовки к собеседованию: «Реальное собеседование» и «Проработка вопросов» по методике интервальных повторений (как Anki)
– (скоро) Агрегатор вакансий
– (скоро) Сообщество
Акция закончится уже сегодня 23 июня 23:59 по мск:
👉 https://easyoffer.ru/pro
3 250
Задача: 1162. As Far from Land as Possible
Сложность: medium
Дана сетка размером n x n, содержащая только значения 0 и 1, где 0 представляет воду, а 1 представляет землю. Найдите ячейку с водой, такое что её расстояние до ближайшей ячейки с землёй максимально, и верните это расстояние. Если в сетке нет ни земли, ни воды, верните -1.
Расстояние, используемое в этой задаче, - это манхэттенское расстояние: расстояние между двумя ячейками (x0, y0) и (x1, y1) равно |x0 - x1| + |y0 - y1|.
Пример:
Input: grid = [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all the land with distance 2.class Solution {
public:
const pair<int, int> direction[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int maxDistance(vector<vector<int>>& grid) {
int visited[grid.size()][grid[0].size()];
queue<pair<int, int>> q;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
visited[i][j] = grid[i][j];
if (grid[i][j]) {
q.push({i, j});
}
}
}
int distance = -1;
while (!q.empty()) {
int qSize = q.size();
while (qSize--) {
pair<int, int> landCell = q.front();
q.pop();
for (pair<int, int> dir : direction) {
int x = landCell.first + dir.first;
int y = landCell.second + dir.second;
if (x >= 0 && y >= 0 && x < grid.size() && y < grid[0].size() && visited[x][y] == 0) {
visited[x][y] = 1;
q.push({x, y});
}
}
}
distance++;
}
return distance == 0 ? -1 : distance;
}
};3 250
Пожизненный PRO тариф — по цене 1 года.
Покупаешь один раз — пользуешься всю жизнь:
👉 https://easyoffer.ru/pro
🚀 PRO-доступ закроет 99% проблем на пути к офферу:
1. Полный доступ ко всем грейдам и профессиям. Не важно, Junior вы или Senior, Тестировщик, Разработчик, Проджект — вы получите материалы под ваш текущий уровень и цели, без ограничений.
2. База live-coding задач и вопросов с реальных собесов с уникальной системой вероятности их встречи. Вы будете готовиться не вслепую, а точечно по тем темам, которые спрашивают чаще всего.
3. Эталонные ответы от Senior-разработчиков. Никакой воды и догадок — только четкие, структурированные решения, за которые дают «зеленый свет» к офферу
4. 1100+ записей реальных собеседований (включая топы: Сбер, Авито, Яндекс, WB, OZON, МТС). Вы увидите всё изнутри: как спрашивают, как отвечают сильные кандидаты и на каких ошибках проваливаются 80% проходящих.
5. База 400+ тестовых заданий. Если вы еще студент, то практикуйтесь на решении задач, которые помогут попасть на собес
6. Автоотклики на Хедхантере — пока вы спите, ваше резюме летит к рекрутерам автоматически. Это экономия сотен часов ручного кликанья.
7. Аналитика ТОП-требований из вакансий. Мы парсим рынок и показываем, какие скиллы сейчас в цене. Это позволит вам точечно апгрейдить резюме и проходить суровые ATS-фильтры (которые отсеивают до 75% резюме еще до просмотра рекрутером).
8. Генератор уникального резюме и CV под каждую вакансию. Забудьте про «универсальное» резюме — нейросеть адаптирует ваш опыт под конкретную позицию за минуту, повышая шансы на приглашение в разы.
9. Тренажеры подготовки к собеседованию:
«Реальное собеседование» — сценарий вопросов из реальных интервью
«Проработка вопросов» — флеш карточки с вопросами/ответами по методике интервальных повторений (как Anki)
10. (Скоро) Агрегатор вакансий — все вакансии из HH, Telegram, LinkedIn и других площадок в одной ленте.
11. (Скоро) Закрытое комьюнити — нетворкинг и помощь в сложных вопросах от таких же целеустремленных айтишников.
Завтра последний день акции:
👉 https://easyoffer.ru/pro
3 250
Задача: 852. Peak Index in a Mountain Array
Сложность: medium
Вам дан целочисленный массив горы arr длины n, где значения увеличиваются до пикового элемента, а затем уменьшаются.
Верните индекс пикового элемента.
Ваша задача — решить это с временной сложностью O(log(n)).
Пример:
Input: arr = [0,1,0]
Output: 1class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int i = 0;
while (arr[i] < arr[i + 1]) {
i++;
}
return i;
}
};3 250
Задача: 208. Implement Trie (Prefix Tree)
Сложность: medium
Реализуйте структуру данных Trie (префиксное дерево), поддерживающую следующие операции:
insert(word) — вставка слова
search(word) — проверка, было ли слово вставлено
startsWith(prefix) — проверка, начинается ли хоть одно вставленное слово с заданного префикса
Пример:
Input: ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] Output: [null, null, true, false, true, null, true]👨💻 Алгоритм: 1⃣Инициализация и вставка: Каждый узел (TrieNode) содержит массив из 26 указателей (по одной на каждую букву алфавита) и флаг isEnd. Метод insert создает недостающие узлы и в конце устанавливает isEnd = true для последнего символа слова. 2⃣Поиск строки: Метод search использует вспомогательную функцию searchPrefix, которая проходит по всем символам слова. Если найденный узел существует и отмечен как конец слова, возвращаем true. 3⃣Проверка префикса: Метод startsWith использует searchPrefix, и возвращает true, если удалось дойти до конца заданного префикса. 😎 Решение:
#include <vector>
#include <string>
class TrieNode {
private:
TrieNode* links[26];
bool isEnd;
public:
TrieNode() : isEnd(false) {
for (int i = 0; i < 26; ++i) {
links[i] = nullptr;
}
}
bool containsKey(char ch) {
return links[ch - 'a'] != nullptr;
}
TrieNode* get(char ch) {
return links[ch - 'a'];
}
void put(char ch, TrieNode* node) {
links[ch - 'a'] = node;
}
void setEnd() {
isEnd = true;
}
bool isEndNode() {
return isEnd;
}
};
class Trie {
private:
TrieNode* root;
TrieNode* searchPrefix(const std::string& word) {
TrieNode* node = root;
for (char ch : word) {
if (node->containsKey(ch)) {
node = node->get(ch);
} else {
return nullptr;
}
}
return node;
}
public:
Trie() {
root = new TrieNode();
}
void insert(const std::string& word) {
TrieNode* node = root;
for (char ch : word) {
if (!node->containsKey(ch)) {
node->put(ch, new TrieNode());
}
node = node->get(ch);
}
node->setEnd();
}
bool search(const std::string& word) {
TrieNode* node = searchPrefix(word);
return node != nullptr && node->isEndNode();
}
bool startsWith(const std::string& prefix) {
return searchPrefix(prefix) != nullptr;
}
};3 250
Задача: 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 250
Привет, ребята!
У нас для вас отличные новости — на easyoffer вышло сразу несколько крупных обновлений:
1. Автоотклики на HeadHunter
Снова работают в полную силу — можно смело возвращаться к активному поиску.
2. Новый раздел «Резюмейкер»
Теперь вы можете быстро создавать уникальные резюме, адаптированные под каждую вакансию, и сразу добавлять сопроводительное письмо. Это заметно повышает шансы получить приглашение на собеседование.
3. База вопросов стала чище
Мы навели порядок и удалили около 30% дубликатов.
Ориентироваться стало проще.
––––––––––––––––––
🔥 Акция в честь обновления
Пожизненный тариф easyoffer PRO — по цене одного года.
Успейте до 23 июня:
👉 https://easyoffer.ru/pro
––––––––––––––––––
Что дальше?
В ближайшие пару недель добавим ещё два раздела:
1. Сообщество с чатами по всем профессиональным направлениям.
2. Агрегатор вакансий, чтобы поиск работы стал ещё удобнее.
3 250
Задача: 944. Delete Columns to Make Sorted
Сложность: easy
Учитывая массив строк words, верните наименьшую строку, которая содержит каждую строку в words в качестве подстроки. Если существует несколько допустимых строк наименьшей длины, верните любую из них. Вы можете предположить, что ни одна строка в words не является подстрокой другой строки в words.
Пример:
Input: strs = ["cba","daf","ghi"] Output: 1👨💻 Алгоритм: 1⃣Инициализировать переменную count для отслеживания количества столбцов, которые нужно удалить. 2⃣Пройти по каждому столбцу от 0 до длины строки. Для каждого столбца проверить, отсортированы ли символы лексикографически. Если столбец не отсортирован, увеличить count. 3⃣Вернуть count. 😎 Решение:
class Solution {
public:
int minDeletionSize(vector<string>& strs) {
int count = 0;
int rows = strs.size();
int cols = strs[0].size();
for (int col = 0; col < cols; col++) {
for (int row = 1; row < rows; row++) {
if (strs[row][col] < strs[row - 1][col]) {
count++;
break;
}
}
}
return count;
}
};3 250
Задача: 1673. Find the Most Competitive Subsequence
Сложность: medium
Дан целочисленный массив nums и положительное целое число k. Верните наиболее конкурентоспособную подпоследовательность массива nums размера k.
Подпоследовательность массива — это результирующая последовательность, полученная путем удаления некоторых (возможно, нуля) элементов из массива.
Мы определяем, что подпоследовательность a более конкурентоспособна, чем подпоследовательность b (одинаковой длины), если в первой позиции, где они различаются, подпоследовательность a имеет число меньше, чем соответствующее число в b. Например, [1,3,4] более конкурентоспособна, чем [1,3,5], потому что первая позиция, где они различаются, это последнее число, и 4 меньше, чем 5.
Пример:
Input: nums = [3,5,2,6], k = 2
Output: [2,6]
Explanation: Among the set of every possible subsequence: {[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]}, [2,6] is the most competitive.class Solution {
public:
vector<int> mostCompetitive(vector<int>& nums, int k) {
deque<int> queue;
int additionalCount = nums.size() - k;
for (int num : nums) {
while (!queue.empty() && queue.back() > num && additionalCount > 0) {
queue.pop_back();
additionalCount--;
}
queue.push_back(num);
}
return vector<int>(queue.begin(), queue.begin() + k);
}
};3 250
Задача: 421. Maximum XOR of Two Numbers in an Array
Сложность: medium
Дан целочисленный массив nums, верните максимальный результат nums[i] XOR nums[j], где 0 <= i <= j < n.
Пример:
Input: nums = [3,10,5,25,2,8] Output: 28 Explanation: The maximum result is 5 XOR 25 = 28.👨💻 Алгоритм: 1⃣Вычислите количество битов L для использования. Это длина максимального числа в двоичном представлении. Инициализируйте max_xor = 0. 2⃣Запустите цикл от i = L−1 до i = 0 (от самого левого бита L−1 до самого правого бита 0): Сдвигайте max_xor влево, чтобы освободить следующий бит. Инициализируйте переменную curr_xor = max_xor | 1, установив 1 в самом правом бите max_xor. Теперь проверьте, можно ли выполнить curr_xor, используя доступные префиксы. 3⃣Вычислите все возможные префиксы длины L−i, итерируя по nums: Поместите в HashSet префиксы префикс текущего числа длиной L−i: num >> i. Итерируйте по всем префиксам и проверьте, можно ли выполнить curr_xor, используя два из них: p1 ^ p2 == curr_xor. Используя свойство самопреобразования XOR p1 ^ p2 ^ p2 = p1, можно переписать это как p1 == curr_xor ^ p2 и просто проверить для каждого p, если curr_xor ^ p есть в префиксах. Если так, установите max_xor равным curr_xor, т.е. установите 1-бит в самом правом бите. В противном случае, пусть max_xor оставит 0-бит в самом правом бите. 😎 Решение:
#include <vector>
#include <unordered_set>
using namespace std;
class Solution {
public:
int findMaximumXOR(vector<int>& nums) {
int maxNum = nums[0];
for (int num : nums) maxNum = max(maxNum, num);
int L = 32 - __builtin_clz(maxNum);
int maxXor = 0, currXor;
unordered_set<int> prefixes;
for (int i = L - 1; i >= 0; --i) {
maxXor <<= 1;
currXor = maxXor | 1;
prefixes.clear();
for (int num : nums) prefixes.insert(num >> i);
for (int p : prefixes) {
if (prefixes.count(currXor ^ p)) {
maxXor = currXor;
break;
}
}
}
return maxXor;
}
};3 250
Задача: 1057. Campus Bikes
Сложность: medium
В городке, изображенном на плоскости X-Y, есть n рабочих и m велосипедов, причем n <= m. Вам дан массив workers длины n, где workers[i] = [xi, yi] - положение i-го рабочего. Вам также дан массив bikes длины m, где bikes[j] = [xj, yj] - позиция j-го велосипеда. Все заданные позиции уникальны. Назначаем велосипед каждому работнику. Среди доступных велосипедов и работников мы выбираем пару (workeri, bikej) с наименьшим манхэттенским расстоянием между ними и назначаем велосипед этому работнику. Если существует несколько пар (workeri, bikej) с одинаковым наименьшим манхэттенским расстоянием, мы выбираем пару с наименьшим индексом работника. Если существует несколько способов сделать это, мы выбираем пару с наименьшим индексом велосипеда. Повторяем этот процесс до тех пор, пока не останется свободных работников. Возвращаем массив answer длины n, где answer[i] - индекс (с индексом 0) велосипеда, на который назначен i-й работник. Манхэттенское расстояние между двумя точками p1 и p2 равно Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|.
Пример:
Input: workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]] Output: [1,0]👨💻 Алгоритм: 1⃣Для каждой пары (работник, велосипед) вычисли Манхэттенское расстояние и сохрани все пары вместе с расстоянием в список. 2⃣Отсортируй список пар по расстоянию, а затем по индексу работника и велосипеда. Назначь велосипеды работникам, следуя отсортированному списку пар и отслеживая, какие работники и велосипеды уже были использованы. 3⃣Заполни и верни массив назначений. 😎 Решение:
class Solution {
public:
vector<int> assignBikes(vector<vector<int>>& workers, vector<vector<int>>& bikes) {
vector<tuple<int, int, int>> pairs;
for (int i = 0; i < workers.size(); i++) {
for (int j = 0; j < bikes.size(); j++) {
int distance = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]);
pairs.emplace_back(distance, i, j);
}
}
sort(pairs.begin(), pairs.end());
vector<int> result(workers.size(), -1);
vector<bool> bikeTaken(bikes.size(), false);
vector<bool> workerAssigned(workers.size(), false);
for (auto& [distance, workerIdx, bikeIdx] : pairs) {
if (!workerAssigned[workerIdx] && !bikeTaken[bikeIdx]) {
result[workerIdx] = bikeIdx;
bikeTaken[bikeIdx] = true;
workerAssigned[workerIdx] = true;
}
}
return result;
}
};3 250
Задача: 917. Reverse Only Letters
Сложность: easy
Задав строку s, переверните ее в соответствии со следующими правилами: все символы, не являющиеся английскими буквами, остаются в той же позиции. Все английские буквы (строчные или прописные) должны быть перевернуты. Верните s после перевертывания.
Пример:
Input: s = "ab-cd" Output: "dc-ba"👨💻 Алгоритм: 1⃣Создать массив для хранения только английских букв из строки s. 2⃣Перевернуть массив с английскими буквами. Пройти по строке s и заменить каждую английскую букву на соответствующую из перевернутого массива. 3⃣Вернуть результат. 😎 Решение:
class Solution {
public:
string reverseOnlyLetters(string s) {
vector<char> letters;
for (char c : s) {
if (isalpha(c)) {
letters.push_back(c);
}
}
reverse(letters.begin(), letters.end());
string result;
int idx = 0;
for (char c : s) {
if (isalpha(c)) {
result += letters[idx++];
} else {
result += c;
}
}
return result;
}
};3 250
Задача: 936. Stamping The Sequence
Сложность: hard
Вам даны две строки stamp и target. Изначально имеется строка s длины target.length со всеми s[i] == '?'. За один ход вы можете поместить штамп над s и заменить каждую букву в s на соответствующую букву из штампа. Например, если штамп = "abc" и target = "abcba", то s изначально будет "?????". За один ход вы можете: поместить штамп в индекс 0 s, чтобы получить "abc??", поместить штамп в индекс 1 s, чтобы получить "?abc?", или поместить штамп в индекс 2 s, чтобы получить "??abc". Обратите внимание, что штамп должен полностью находиться в границах s, чтобы штамповать (то есть вы не можете поместить штамп в индекс 3 s). Мы хотим преобразовать s в цель, используя не более 10 * target.length ходов. Верните массив индекса самой левой буквы, которая штампуется на каждом ходу. Если мы не можем получить цель из s за 10 * target.length оборотов, верните пустой массив
Пример:
Input: stamp = "abc", target = "ababc" Output: [0,2]👨💻 Алгоритм: 1⃣Инициализировать переменные: s как массив символов '?', длиной target.length. res как список для хранения результатов. done как массив булевых значений для отслеживания того, какие позиции уже штампованы. target как массив символов для удобства. 2⃣Использовать функцию canStamp для проверки, можно ли штамповать stamp в target начиная с индекса i. Использовать функцию doStamp для штампования stamp в target начиная с индекса i. Повторять шаги, пока штампы возможны или достигнут максимум ходов (10 * target.length): Перебрать все возможные начальные позиции для штампа. Проверить, можно ли штамповать в текущей позиции. Если можно, штамповать и добавить индекс в res. 3⃣Если все символы в s соответствуют символам в target, вернуть массив res в обратном порядке. Иначе, вернуть пустой массив. 😎 Решение:
class Solution {
public:
vector<int> movesToStamp(string stamp, string target) {
vector<int> res;
vector<bool> done(target.size(), false);
string t = target;
string s = stamp;
int m = s.size(), n = t.size();
auto canStamp = [&](int i) {
for (int j = 0; j < m; j++) {
if (t[i + j] != '?' && t[i + j] != s[j]) {
return false;
}
}
return true;
};
auto doStamp = [&](int i) {
for (int j = 0; j < m; j++) {
t[i + j] = '?';
}
res.push_back(i);
done[i] = true;
};
bool changed = true;
while (changed) {
changed = false;
for (int i = 0; i <= n - m; i++) {
if (!done[i] && canStamp(i)) {
doStamp(i);
changed = true;
}
}
}
for (char c : t) {
if (c != '?') {
return {};
}
}
reverse(res.begin(), res.end());
return res;
}
};3 250
Задача: 979. Distribute Coins in Binary Tree
Сложность: medium
Вам дан корень бинарного дерева с n узлами, где каждый узел в дереве содержит node.val монет. Всего по всему дереву распределено n монет.
За один ход мы можем выбрать два смежных узла и переместить одну монету из одного узла в другой. Ход может быть как от родителя к ребенку, так и от ребенка к родителю.
Верните минимальное количество ходов, необходимых для того, чтобы каждый узел имел ровно одну монету.
Пример:
Input: root = [3,0,0] Output: 2 Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.👨💻 Алгоритм: 1⃣Инициализация и определение рекурсивной функции. Инициализируйте переменную moves = 0. Определите рекурсивную функцию dfs, которая считает количество перемещений монет. Базовый случай: если текущий узел равен null, верните 0. 2⃣Рекурсивный обход дерева. Внутри dfs вызовите dfs для левого и правого поддеревьев, чтобы получить количество монет, которые нужно переместить в каждом поддереве. Вычислите количество перемещений для текущего узла: добавьте абсолютные значения перемещаемых монет в moves. 3⃣Возвращение результата. Верните количество монет, которые текущий узел может передать своему родителю: значение узла плюс количество монет в левом и правом поддеревьях минус 1. Вызовите dfs от корня дерева и верните moves. 😎 Решение:
class Solution {
public:
int distributeCoins(TreeNode* root) {
moves = 0;
dfs(root);
return moves;
}
private:
int moves;
int dfs(TreeNode* current) {
if (current == nullptr) return 0;
int leftCoins = dfs(current->left);
int rightCoins = dfs(current->right);
moves += abs(leftCoins) + abs(rightCoins);
return current->val - 1 + leftCoins + rightCoins;
}
};3 250
Задача: 583. Delete Operation for Two Strings
Сложность: medium
Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми.
На одном шаге можно удалить ровно один символ в любой строке.
Пример:
Input: word1 = "sea", word2 = "eat" Output: 2 Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".👨💻 Алгоритм: 1⃣ Инициализация массива: Создайте одномерный массив dp для хранения минимального количества удалений, необходимых для уравнивания строк word1 и word2. 2⃣ Заполнение массива: Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки. 3⃣ Обновление и результат: Скопируйте временный массив temp обратно в dp после обработки каждой строки. В конце верните значение из dp, представляющее минимальное количество удалений. 😎 Решение:
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size();
int n = word2.size();
vector<int> dp(n + 1, 0);
for (int i = 0; i <= m; ++i) {
vector<int> temp(n + 1, 0);
for (int j = 0; j <= n; ++j) {
if (i == 0 || j == 0) {
temp[j] = i + j;
} else if (word1[i - 1] == word2[j - 1]) {
temp[j] = dp[j - 1];
} else {
temp[j] = 1 + min(dp[j], temp[j - 1]);
}
}
dp = temp;
}
return dp[n];
}
};3 250
Задача: 1268. Search Suggestions System
Сложность: medium
Вам дан массив строк products и строка searchWord. Разработайте систему, которая предлагает не более трех названий продуктов после ввода каждого символа searchWord. Предлагаемые товары должны иметь общий префикс с searchWord. Если есть более трех продуктов с общим префиксом, возвращаются три лексикографически минимальных продукта. Возвращается список списков предложенных продуктов после ввода каждого символа searchWord.
Пример:
Input: products = ["havana"], searchWord = "havana" Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]👨💻 Алгоритм: 1⃣Отсортируйте массив продуктов. 2⃣Итерируйтесь по каждому символу в searchWord, находите все продукты, которые соответствуют текущему префиксу. 3⃣Сохраняйте не более трех лексикографически минимальных продуктов для каждого префикса. 😎 Решение:
class Solution {
public:
vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
sort(products.begin(), products.end());
vector<vector<string>> result;
string prefix = "";
for (char c : searchWord) {
prefix += c;
vector<string> suggestions;
for (const string& product : products) {
if (product.find(prefix) == 0) {
suggestions.push_back(product);
if (suggestions.size() == 3) break;
}
}
result.push_back(suggestions);
}
return result;
}
};3 250
Задача: 1514. Path with Maximum Probability
Сложность: medium
Вам дан неориентированный взвешенный граф из n узлов (индексация с нуля), представленный списком ребер, где edges[i] = [a, b] является неориентированным ребром, соединяющим узлы a и b с вероятностью успешного прохождения этого ребра succProb[i].
Даны два узла start и end, найдите путь с максимальной вероятностью успеха, чтобы перейти от start к end, и верните его вероятность успеха.
Если пути от start до end не существует, верните 0. Ваш ответ будет принят, если он отличается от правильного ответа не более чем на 1e-5.
Пример:
Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.class Solution {
public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<double> maxProb(n, 0.0);
maxProb[start] = 1.0;
for (int i = 0; i < n - 1; i++) {
bool hasUpdate = false;
for (int j = 0; j < edges.size(); j++) {
int u = edges[j][0];
int v = edges[j][1];
double pathProb = succProb[j];
if (maxProb[u] * pathProb > maxProb[v]) {
maxProb[v] = maxProb[u] * pathProb;
hasUpdate = true;
}
if (maxProb[v] * pathProb > maxProb[u]) {
maxProb[u] = maxProb[v] * pathProb;
hasUpdate = true;
}
}
if (!hasUpdate) {
break;
}
}
return maxProb[end];
}
};3 250
Задача: 1425. Constrained Subsequence Sum
Сложность: hard
Дан целочисленный массив nums и целое число k, верните максимальную сумму непустой подпоследовательности этого массива, такую, что для любых двух последовательных целых чисел в подпоследовательности nums[i] и nums[j], где i < j, выполняется условие j - i <= k.
Подпоследовательность массива получается путем удаления некоторого количества элементов (может быть ноль) из массива, оставляя оставшиеся элементы в их исходном порядке.
Пример:
Input: nums = [10,2,-10,5,20], k = 2 Output: 37 Explanation: The subsequence is [10, 2, 5, 20].👨💻 Алгоритм: 1⃣Инициализируйте очередь queue и массив dp той же длины, что и nums. 2⃣Итерируйте i по индексам nums: Если i минус первый элемент queue больше k, удалите элемент из начала queue. Установите dp[i] как dp[queue.front()] + nums[i]. Если queue пуст, используйте 0 вместо dp[queue.front()]. Пока dp[queue.back()] меньше dp[i], удаляйте элементы с конца queue. Если dp[i] > 0, добавьте i в конец queue. 3⃣Верните максимальное значение в массиве dp. 😎 Решение:
class Solution {
public:
int constrainedSubsetSum(vector<int>& nums, int k) {
deque<int> queue;
vector<int> dp(nums.size());
int maxSum = INT_MIN;
for (int i = 0; i < nums.size(); ++i) {
if (!queue.empty() && i - queue.front() > k) {
queue.pop_front();
}
dp[i] = (queue.empty() ? 0 : dp[queue.front()]) + nums[i];
while (!queue.empty() && dp[queue.back()] < dp[i]) {
queue.pop_back();
}
if (dp[i] > 0) {
queue.push_back(i);
}
maxSum = max(maxSum, dp[i]);
}
return maxSum;
}
};