C/C++ | LeetCode
前往频道在 Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
显示更多
网络:3 218
订阅者
无数据24 小时
-57 天
-830 天
帖子存档
3 218
Задача: 1370. Increasing Decreasing String
Сложность: easy
Дана строка s. Переставьте символы строки, используя следующий алгоритм:
Выберите наименьший символ из s и добавьте его к результату.
Выберите наименьший символ из s, который больше последнего добавленного символа, и добавьте его.
Повторяйте шаг 2, пока не сможете выбрать больше символов.
Выберите наибольший символ из s и добавьте его к результату.
Выберите наибольший символ из s, который меньше последнего добавленного символа, и добавьте его.
Повторяйте шаг 5, пока не сможете выбрать больше символов.
Повторяйте шаги с 1 по 6, пока не выберете все символы из s.
На каждом этапе, если наименьший или наибольший символ появляется более одного раза, вы можете выбрать любое его вхождение и добавить его к результату.
Верните результирующую строку после сортировки s с помощью этого алгоритма.
Пример:
Input: s = "rat" Output: "art" Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.👨💻 Алгоритм: 1⃣Инициализация и сортировка: Создайте словарь для подсчета количества каждого символа в строке s. Создайте результирующую строку result. 2⃣Перебор и добавление символов: Используйте два цикла: первый для добавления символов в возрастающем порядке, второй — в убывающем. В каждом цикле добавляйте символы к результату, обновляя их количество в словаре. 3⃣Проверка завершения: Повторяйте шаги 2 и 3, пока не будут добавлены все символы из строки s в result. 😎 Решение:
#include <string>
#include <vector>
class Solution {
public:
std::string sortString(std::string s) {
std::vector<int> charCount(26, 0);
for (char c : s) {
charCount[c - 'a']++;
}
std::string result;
while (result.size() < s.size()) {
for (char c = 'a'; c <= 'z'; c++) {
if (charCount[c - 'a'] > 0) {
result += c;
charCount[c - 'a']--;
}
}
for (char c = 'z'; c >= 'a'; c--) {
if (charCount[c - 'a'] > 0) {
result += c;
charCount[c - 'a']--;
}
}
}
return result;
}
};3 218
Задача: 1271. Hexspeak
Сложность: easy
Десятичное число можно преобразовать в его шестнадцатеричное представление, сначала преобразовав его в прописную шестнадцатеричную строку, а затем заменив все вхождения цифры '0' на букву 'O', а цифры '1' - на букву 'I'. Такое представление допустимо тогда и только тогда, когда оно состоит только из букв набора {'A', 'B', 'C', 'D', 'E', 'F', 'I', 'O'}. Получив строку num, представляющую десятичное целое число n, верните шестнадцатеричное представление n, если оно допустимо, иначе верните "ERROR".
Пример:
Input: num = "257" Output: "IOI"👨💻 Алгоритм: 1⃣Преобразуйте десятичное число в шестнадцатеричную строку в верхнем регистре. 2⃣Замените все вхождения цифры '0' на букву 'O', а цифры '1' на букву 'I' 3⃣Проверьте, что преобразованная строка содержит только допустимые символы. Если это так, верните строку, иначе верните "ERROR". 😎 Решение:
class Solution {
public:
string toHexString(string num) {
stringstream ss;
ss << hex << uppercase << stol(num);
string hexStr = ss.str();
for (char& c : hexStr) {
if (c == '0') c = 'O';
else if (c == '1') c = 'I';
else if (string("ABCDEFIO").find(c) == string::npos) return "ERROR";
}
return hexStr;
}
};3 218
🚨60 минут
Пожизненный PRO-доступ на easyoffer (подготовка к IT-собесам + поиск оффера) по цене одного года закрывается прямо сейчас. Один платёж — доступ навсегда.
Последнее напоминание 👇
👉 https://easyoffer.ru/pro
3 218
⚠️ 3 часа до конца акции.
Последний шанс забрать пожизненный PRO на easyoffer по цене одного года. Это полный доступ к подготовке к собесам и инструментам поиска работы (вопросы с реальных интервью, ответы сеньоров, автоотклики, тренажёры) — один раз и навсегда, вместо ежегодной оплаты.
В полночь цена возвращается к обычной.
👉 https://easyoffer.ru/pro
3 218
Задача: 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 218
⏳ Ребята, сегодня заканчивается акция, о которой стоит знать, если вы в поиске работы или планируете сменить её в ближайший год.
easyoffer — это платформа для подготовки к IT-собесам и поиска оффера. Внутри:
– база реальных вопросов и live-coding задач с собесов (с частотой их встречаемости)
– эталонные ответы от Senior-разработчиков
– 1100+ записей настоящих интервью (Сбер, Яндекс, Авито, WB, OZON, МТС)
– автоотклики на hh, генератор резюме под вакансию, тренажёры собеседований
Сегодня пожизненный PRO-доступ продаётся по цене одного года — платишь один раз и пользуешься всем этим всю жизнь, включая будущие фичи. С завтрашнего дня — только обычная годовая подписка.
👉 https://easyoffer.ru/pro
3 218
Задача: 201. Bitwise AND of Numbers Range
Сложность: medium
Даны два целых числа left и right, обозначающие диапазон [left, right].
Нужно вернуть результат побитового AND всех чисел в этом диапазоне (включительно).
Пример:
Input: left = 5, right = 7 Output: 4👨💻 Алгоритм: 1⃣Пока left < right, сдвигаем оба числа вправо (>>= 1), пока они не станут равны. Это находит общий префикс битов. 2⃣Подсчитываем количество сдвигов — это количество младших битов, которые могут изменяться в диапазоне, и обнуляются при AND. 3⃣После этого сдвигаем результат left обратно влево (<< shift) — возвращаем биты на место. 😎 Решение:
class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int shift = 0;
while (m < n) {
m >>= 1;
n >>= 1;
++shift;
}
return m << shift;
}
};3 218
Задача: 1043. Partition Array for Maximum Sum
Сложность: medium
Если задан целочисленный массив arr, разбейте его на (смежные) подмассивы длины не более k. После разбиения значения каждого подмассива меняются так, чтобы стать максимальным значением этого подмассива. Верните наибольшую сумму заданного массива после разбиения. Тестовые примеры генерируются таким образом, чтобы ответ умещался в 32-битное целое число.
Пример:
Input: arr = [1,15,7,9,2,5,10], k = 3 Output: 84👨💻 Алгоритм: 1⃣Инициализация: Создаем массив dp, где dp[i] будет хранить наибольшую сумму подмассива, заканчивающегося в позиции i. 2⃣Заполнение массива dp: Проходим по массиву arr и для каждой позиции i пытаемся разбить подмассив длины до k и обновить dp[i] с максимальной возможной суммой. 3⃣Поддержание максимального значения в подмассиве: Для каждого подмассива длины 1 до k, вычисляем максимальное значение в этом подмассиве и обновляем dp[i]. 😎 Решение:
class Solution {
public:
int maxSumAfterPartitioning(vector<int>& arr, int k) {
int n = arr.size();
vector<int> dp(n, 0);
for (int i = 0; i < n; ++i) {
int max_val = 0;
for (int j = 1; j <= k; ++j) {
if (i - j + 1 >= 0) {
max_val = max(max_val, arr[i - j + 1]);
if (i - j >= 0) {
dp[i] = max(dp[i], dp[i - j] + max_val * j);
} else {
dp[i] = max(dp[i], max_val * j);
}
}
}
}
return dp[n - 1];
}
};3 218
Пожизненный PRO — по цене одного года.
Покупаешь один раз — пользуешься всю жизнь:
👉 https://easyoffer.ru/pro
🚀 PRO-доступ закроет 99% проблем на пути к офферу:
1. 1100+ записей реальных собеседований (включая топы: Сбер, Авито, Яндекс, WB, OZON, МТС). Видите всё изнутри: как спрашивают, как отвечают сильные кандидаты и на каких ошибках проваливаются 80%.
2. База live-coding задач и вопросов с реальных собесов — с уникальной системой вероятности их встречи. Готовитесь не вслепую, а точечно по темам, которые спрашивают чаще всего.
3. Эталонные ответы от Senior-разработчиков. Никакой воды и догадок — только чёткие структурированные решения, за которые дают «зелёный свет» к офферу.
4. Полный доступ ко всем грейдам и профессиям. Junior вы или Senior, тестировщик, разработчик или проджект — вы получаете ВСЕ материалы easyoffer без ограничений. Безлимитно, Все, Навсегда.
5. База 400+ тестовых заданий. Прокачивайте навыки на реальных задачах — тех самых, что дают перед собесом.
6. Автоотклики на hh.ru — пока вы спите, резюме уходит рекрутерам автоматически. Экономия сотен часов ручного кликанья.
7. Аналитика ТОП-требований из вакансий. Парсим рынок и показываем, какие скиллы сейчас в цене. Апгрейдите резюме точечно и проходите ATS-фильтры (они отсеивают до 75% резюме ещё до рекрутера).
8. Генератор резюме и CV под каждую вакансию. Забудьте про «универсальное» резюме — нейросеть адаптирует ваш опыт под конкретную позицию за минуту и повышает шансы на приглашение в разы.
9. Тренажёры подготовки к собеседованию:
«Реальное собеседование» — сценарий вопросов из настоящих интервью. «Проработка вопросов» — флеш-карточки по методике интервальных повторений (как Anki)
10. 🔥 Самое важное: все будущие фичи
Вы платите один раз, а продукт растёт всю жизнь. Каждое обновление, каждый новый инструмент, каждая фича, которая появится за все годы проекта, автоматически падает вам в подписку без доплат. Вы фиксируете цену года, а получаете продукт, который через пару лет будет стоить в разы дороже
⭐️ Это уникальная акция пока сайт в режиме Beta.
Успей ей воспользоваться⏳ Завтра последний день.
👉 https://easyoffer.ru/pro
3 218
Задача: 748. Shortest Completing Word
Сложность: easy
Вам дан целочисленный массив nums, в котором наибольшее целое число уникально. Определите, является ли наибольший элемент массива по крайней мере в два раза больше всех остальных чисел в массиве. Если да, то верните индекс самого большого элемента, в противном случае верните -1.
Пример:
Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"] Output: "steps"👨💻 Алгоритм: 1⃣Извлечь все буквы из licensePlate, игнорируя цифры и пробелы, и создать словарь для подсчета частоты каждой буквы. 2⃣Пройти по массиву words, проверяя каждое слово на соответствие требованиям. 3⃣Найти самое короткое завершающее слово среди подходящих. 😎 Решение:
class Solution {
public:
string shortestCompletingWord(string licensePlate, vector<string>& words) {
unordered_map<char, int> licenseCount = getCharCount(licensePlate);
string result;
for (const string& word : words) {
if (isCompletingWord(word, licenseCount)) {
if (result.empty() || word.length() < result.length()) {
result = word;
}
}
}
return result;
}
private:
unordered_map<char, int> getCharCount(const string& s) {
unordered_map<char, int> count;
for (char c : s) {
if (isalpha(c)) {
count[tolower(c)]++;
}
}
return count;
}
bool isCompletingWord(const string& word, const unordered_map<char, int>& licenseCount) {
unordered_map<char, int> wordCount;
for (char c : word) {
wordCount[c]++;
}
for (const auto& entry : licenseCount) {
if (wordCount[entry.first] < entry.second) {
return false;
}
}
return true;
}
};3 218
🔥 Осталось 3 дня!
Пожизненный easyoffer PRO по цене одного года. Покупаешь один раз – пользуешься всю жизнь.
Что входит в PRO:
– Вопросы и задачи с реальных собеседований в конкретных компаниях
– Лучшие ответы и видео-примеры от middle/senior специалистов
– Записи реальных собеседований
– Обход фильтров ATS с топ-30 ключевых слов в резюме
– Автоотклики на hh
– Тренажёры и симуляторы для идеальной подготовки к интервью
⏳ Акция действует только до 2 сентября 23:59 по МСК
👉 Забрать PRO со скидкой 70%: https://easyoffer.ru/pro
3 218
Задача: 1380. Lucky Numbers in a Matrix
Сложность: easy
Дана матрица m x n из различных чисел, верните все счастливые числа в матрице в любом порядке.
Счастливое число — это элемент матрицы, который является минимальным элементом в своей строке и максимальным в своем столбце.
Пример:
Input: matrix = [[3,7,8],[9,11,13],[15,16,17]] Output: [15] Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column.👨💻 Алгоритм: 1⃣Сохраните минимум каждой строки в список rowMin и максимум каждого столбца в список colMax. 2⃣Итерируйте по каждому числу в матрице и проверяйте, равно ли оно rowMin[i] и colMax[j]. 3⃣Если число удовлетворяет условию, добавьте его в список luckyNumbers и верните luckyNumbers. 😎 Решение:
class Solution {
public:
vector<int> luckyNumbers (vector<vector<int>>& matrix) {
int N = matrix.size(), M = matrix[0].size();
vector<int> rowMin;
for (int i = 0; i < N; i++) {
int rMin = INT_MAX;
for (int j = 0; j < M; j++) {
rMin = min(rMin, matrix[i][j]);
}
rowMin.push_back(rMin);
}
vector<int> colMax;
for (int i = 0; i < M; i++) {
int cMax = INT_MIN;
for (int j = 0; j < N; j++) {
cMax = max(cMax, matrix[j][i]);
}
colMax.push_back(cMax);
}
vector<int> luckyNumbers;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j]) {
luckyNumbers.push_back(matrix[i][j]);
}
}
}
return luckyNumbers;
}
};3 218
Задача: 1133. Largest Unique Number
Сложность: easy
Вам Дан целочисленный массив nums, верните наибольшее целое число, которое встречается только один раз. Если ни одно целое число не встречается один раз, верните -1.
Пример:
Input: nums = [5,7,3,9,4,9,8,3,1] Output: 8 Explanation: The maximum integer in the array is 9 but it is repeated. The number 8 occurs only once, so it is the answer.👨💻 Алгоритм: 1⃣Создайте хеш-таблицу для хранения количества каждого числа в массиве. 2⃣Пройдите по массиву и заполните хеш-таблицу количеством каждого числа. 3⃣Инициализируйте результат значением -1. Пройдите по хеш-таблице и если значение ключа равно 1, установите результат равным максимальному значению между ключом и текущим результатом. Верните результат. 😎 Решение:
class Solution {
public:
int largestUniqueNumber(vector<int>& nums) {
unordered_map<int, int> count;
for (int num : nums) {
count[num]++;
}
int result = -1;
for (auto& entry : count) {
if (entry.second == 1) {
result = max(result, entry.first);
}
}
return result;
}
};3 218
Задача: CodeTestcaseTest ResultTest Result1187. Make Array Strictly Increasing
Сложность: hard
Даны два целочисленных массива arr1 и arr2. Верните минимальное количество операций (возможно, ноль), необходимых для того, чтобы сделать arr1 строго возрастающим.
В одной операции вы можете выбрать два индекса 0 <= i < arr1.length и 0 <= j < arr2.length и выполнить присваивание arr1[i] = arr2[j].
Если нет способа сделать arr1 строго возрастающим, верните -1.
Пример:
Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].class Solution {
public:
int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
sort(arr2.begin(), arr2.end());
int answer = dfs(0, -1, arr1, arr2);
return answer < 2001 ? answer : -1;
}
private:
unordered_map<pair<int, int>, int, hash_pair> dp;
int dfs(int i, int prev, vector<int>& arr1, vector<int>& arr2) {
if (i == arr1.size()) return 0;
pair<int, int> key = {i, prev};
if (dp.count(key)) return dp[key];
int cost = 2001;
if (arr1[i] > prev) {
cost = dfs(i + 1, arr1[i], arr1, arr2);
}
int idx = bisectRight(arr2, prev);
if (idx < arr2.size()) {
cost = min(cost, 1 + dfs(i + 1, arr2[idx], arr1, arr2));
}
dp[key] = cost;
return cost;
}
int bisectRight(const vector<int>& arr, int value) {
int left = 0, right = arr.size();
while (left < right) {
int mid = (left + right) / 2;
if (arr[mid] <= value) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
struct hash_pair {
template <class T1, class T2>
size_t operator()(const pair<T1, T2>& p) const {
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);
return hash1 ^ hash2;
}
};
};3 218
Задача: 715. Range Module
Сложность: hard
Модуль Range - это модуль, который отслеживает диапазоны чисел. Создайте структуру данных для отслеживания диапазонов, представленных в виде полуоткрытых интервалов, и запросов к ним. Полуоткрытый интервал [left, right) обозначает все вещественные числа x, где left <= x < right. Реализуйте класс RangeModule: RangeModule() Инициализирует объект структуры данных. void addRange(int left, int right) Добавляет полуоткрытый интервал [left, right), отслеживая каждое вещественное число в этом интервале. Добавление интервала, который частично перекрывает отслеживаемые в данный момент числа, должно добавить все числа в интервале [left, right), которые еще не отслеживаются. boolean queryRange(int left, int right) Возвращает true, если каждое действительное число в интервале [left, right) отслеживается в данный момент, и false в противном случае. void removeRange(int left, int right) Прекращает отслеживание каждого действительного числа, отслеживаемого в данный момент в полуоткрытом интервале [left, right).
Пример:
Input
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output
[null, null, null, true, false, true]class RangeModule {
public:
RangeModule() {}
void addRange(int left, int right) {
vector<pair<int, int>> newRanges;
int i = 0;
while (i < ranges.size() && ranges[i].second < left) {
newRanges.push_back(ranges[i]);
i++;
}
while (i < ranges.size() && ranges[i].first <= right) {
left = min(left, ranges[i].first);
right = max(right, ranges[i].second);
i++;
}
newRanges.push_back({left, right});
while (i < ranges.size()) {
newRanges.push_back(ranges[i]);
i++;
}
ranges = newRanges;
}
bool queryRange(int left, int right) {
for (auto& range : ranges) {
if (range.first <= left && right <= range.second) {
return true;
}
}
return false;
}
void removeRange(int left, int right) {
vector<pair<int, int>> newRanges;
for (auto& range : ranges) {
if (range.first < left) {
newRanges.push_back({range.first, min(range.second, left)});
}
if (right < range.second) {
newRanges.push_back({max(range.first, right), range.second});
}
}
ranges = newRanges;
}
private:
vector<pair<int, int>> ranges;
};3 218
Задача: 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 218
Задача: 17. Letter Combinations of a Phone Number
Сложность: medium
Дана строка, содержащая цифры от 2 до 9. Необходимо вернуть все возможные комбинации букв, которые может представлять эта строка, согласно клавиатуре мобильного телефона.
Цифра 1 не используется, и для неё нет соответствующих букв.
Пример:
Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]👨💻 Алгоритм: 1⃣Используем рекурсию и бэктрекинг. Для каждой цифры подставляем все возможные буквы. 2⃣На каждом шаге рекурсивно добавляем буквы для текущей цифры к текущей строке. 3⃣Когда строка достигла длины исходных digits — добавляем комбинацию в результат. 😎 Решение:
class Solution {
public:
void find(string digits, vector<string> v, vector<string>& res, string s, int k) {
if (k >= digits.size()) {
res.push_back(s);
return;
}
int a = digits[k] - '0';
for (int i = 0; i < v[a].size(); i++) {
s += v[a][i];
find(digits, v, res, s, k + 1);
s.pop_back();
}
}
vector<string> letterCombinations(string digits) {
vector<string> res;
if (digits.empty()) return res;
vector<string> v = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
string s = "";
find(digits, v, res, s, 0);
return res;
}
};3 218
Задача: 1261. Find Elements in a Contaminated Binary Tree
Сложность: medium
Дано двоичное дерево со следующими правилами: root.val == 0 Если treeNode.val == x и treeNode.left != null, то treeNode.left.val == 2 * x + 1 Если treeNode.val == x и treeNode.right != null, то treeNode.right.val == 2 * x + 2 Теперь двоичное дерево загрязнено, то есть все treeNode.val были изменены на -1. Реализация класса FindElements: FindElements(TreeNode* root) Инициализирует объект с загрязненным двоичным деревом и восстанавливает его. bool find(int target) Возвращает true, если целевое значение существует в восстановленном двоичном дереве.
Пример:
Input ["FindElements","find","find"] [[[-1,null,-1]],[1],[2]] Output [null,false,true]👨💻 Алгоритм: 1⃣Восстановление дерева: Начните с корневого узла, установите его значение на 0. Затем рекурсивно восстановите значения для всех узлов, используя правила left.val = 2 * parent.val + 1 и right.val = 2 * parent.val + 2. 2⃣Сохранение значений: Используйте структуру данных, такую как множество (set), для хранения всех восстановленных значений узлов. 3⃣Поиск значений: Реализуйте метод поиска, который проверяет, содержится ли целевое значение в множестве восстановленных значений. 😎 Решение:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class FindElements {
public:
TreeNode* root;
unordered_set<int> values;
FindElements(TreeNode* root) {
this->root = root;
root->val = 0;
values.insert(0);
recover(root);
}
void recover(TreeNode* node) {
if (node->left != nullptr) {
node->left->val = 2 * node->val + 1;
values.insert(node->left->val);
recover(node->left);
}
if (node->right != nullptr) {
node->right->val = 2 * node->val + 2;
values.insert(node->right->val);
recover(node->right);
}
}
bool find(int target) {
return values.find(target) != values.end();
}
};3 218
Задача: 1026. Maximum Difference Between Node and Ancestor
Сложность: medium
Учитывая корень бинарного дерева, найдите максимальное значение v, для которого существуют различные вершины a и b, где v = |a.val - b.val| и a является предком b. Вершина a является предком b, если: любой ребенок a равен b или любой ребенок a является предком b.
Пример:
Input: root = [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int maxAncestorDiff(TreeNode* root) {
return dfs(root, root->val, root->val);
}
private:
int dfs(TreeNode* node, int min_val, int max_val) {
if (!node) return max_val - min_val;
min_val = min(min_val, node->val);
max_val = max(max_val, node->val);
int left = dfs(node->left, min_val, max_val);
int right = dfs(node->right, min_val, max_val);
return max(left, right);
}
};3 218
Пожизненный PRO доступ на easyoffer — по цене одного года!
До 2 сентября вы можете купить PRO навсегда.
Покупаешь один раз — пользуешься всю жизнь.
– База вопросов и задач из собеседований
– Примеры видео-ответов на вопросы
– Записи реальных собеседований
– Тренажеры "Проработка вопросов" и "Реальное собеседование"
– Аналитика требований из вакансий
– Автоотклики на вакансии
– Агрегатор вакансий (скоро)
👉 Купить PRO со скидкой 70%: https://easyoffer.ru/pro
