C/C++ | LeetCode
前往频道在 Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
显示更多
网络:3 211
订阅者
-224 小时
-127 天
-1730 天
帖子存档
3 210
Задача: 70. Climbing Stairs
Сложность: easy
Чтобы добраться до вершины лестницы с n ступенями, можно каждый раз делать шаг на 1 или 2 ступеньки.
Нужно посчитать, сколькими способами можно подняться на вершину.
Пример:
Input: n = 2 Output: 2 Варианты: 1 + 1 2👨💻 Алгоритм: 1⃣На каждом шаге есть 2 варианта: подняться на 1 или на 2 ступеньки — задача сводится к подсчёту всех таких комбинаций 2⃣Используем рекурсивную функцию: climb(i, n) = climb(i + 1, n) + climb(i + 2, n) — сумма способов дойти с текущей позиции i до цели n 3⃣Базовые случаи: если i == n — достигли цели, вернуть 1 если i > n — вышли за пределы, вернуть 0 😎 Решение:
class Solution {
public:
int climbStairs(int n) { return climb_Stairs(0, n); }
int climb_Stairs(int i, int n) {
if (i > n) return 0;
if (i == n) return 1;
return climb_Stairs(i + 1, n) + climb_Stairs(i + 2, n);
}
};3 210
Задача: 1493. Longest Subarray of 1's After Deleting One Element
Сложность: medium
Дан бинарный массив nums, из которого следует удалить один элемент.
Верните размер самой длинной непустой подмассивы, содержащей только 1, в результирующем массиве. Верните 0, если такого подмассива не существует.
Пример:
Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1's is [1,1,1,1,1].class Solution {
public:
int longestSubarray(vector<int>& nums) {
int zeroCount = 0;
int longestWindow = 0;
int start = 0;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] == 0) {
zeroCount++;
}
while (zeroCount > 1) {
if (nums[start] == 0) {
zeroCount--;
}
start++;
}
longestWindow = max(longestWindow, i - start);
}
return longestWindow;
}
};3 210
Задача: 1167. Minimum Cost to Connect Sticks
Сложность: medium
У вас есть несколько палочек с положительными целыми длинами. Эти длины даны в виде массива sticks, где sticks[i] — длина i-й палочки.
Вы можете соединить любые две палочки длиной x и y в одну палочку, заплатив стоимость x + y. Вы должны соединить все палочки, пока не останется только одна палочка.
Верните минимальную стоимость соединения всех данных палочек в одну палочку таким образом.
Пример:
Input: sticks = [5]
Output: 0
Explanation: There is only one stick, so you don't need to do anything. The total cost is 0.class Solution {
public:
int connectSticks(vector<int>& sticks) {
int totalCost = 0;
priority_queue<int, vector<int>, greater<int>> pq(sticks.begin(), sticks.end());
while (pq.size() > 1) {
int stick1 = pq.top();
pq.pop();
int stick2 = pq.top();
pq.pop();
int cost = stick1 + stick2;
totalCost += cost;
pq.push(cost);
}
return totalCost;
}
};3 210
Задача: 841. Keys and Rooms
Сложность: medium
Есть n комнат, пронумерованных от 0 до n - 1, и все комнаты закрыты, кроме комнаты 0. Ваша цель — посетить все комнаты. Однако вы не можете войти в закрытую комнату, не имея ключа от нее.
Когда вы посещаете комнату, вы можете найти в ней набор различных ключей. Каждый ключ имеет номер, указывающий, какую комнату он открывает, и вы можете взять их все с собой, чтобы открыть другие комнаты.
Дан массив rooms, где rooms[i] — это набор ключей, которые вы можете получить, если посетите комнату i. Верните true, если вы можете посетить все комнаты, или false в противном случае.
Пример:
Input: rooms = [[1],[2],[3],[]] Output: true Explanation: We visit room 0 and pick up key 1. We then visit room 1 and pick up key 2. We then visit room 2 and pick up key 3. We then visit room 3. Since we were able to visit every room, we return true.👨💻 Алгоритм: 1⃣Создайте массив seen для отслеживания посещенных комнат и стек stack для ключей, которые нужно использовать. 2⃣Поместите ключ от комнаты 0 в стек и отметьте комнату 0 как посещенную. 3⃣Пока стек не пуст, извлекайте ключи из стека и используйте их для открытия новых комнат, добавляя найденные ключи в стек. Если все комнаты посещены, верните true, иначе false. 😎 Решение:
class Solution {
public:
bool canVisitAllRooms(vector<vector<int>>& rooms) {
vector<bool> seen(rooms.size(), false);
seen[0] = true;
stack<int> stk;
stk.push(0);
while (!stk.empty()) {
int node = stk.top();
stk.pop();
for (int nei : rooms[node]) {
if (!seen[nei]) {
seen[nei] = true;
stk.push(nei);
}
}
}
for (bool v : seen) {
if (!v) return false;
}
return true;
}
};3 210
Задача: 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 210
Задача: 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 210
Задача: 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 210
Задача: 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 210
Задача: 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 210
Задача: 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 210
Задача: 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 210
Задача: 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 210
Задача: 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 210
Задача: 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 210
Сегодня последний день, когда можно приобрести пожизненный PRO тариф easyoffer
Акция до 20 февраля 00:00
Покупаешь сейчас один раз — пользуешься всю жизнь без лимита, включая все будущие функции.
👉 Смотри подробности тарифа и покупай на https://easyoffer.ru/
3 210
Задача: 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 210
Задача: 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 210
Завтра конец акции на возможность приобрести PRO тариф по цене одного года
Доступный функционал включает базы вопросов с собеседований, задач для live-coding, реальных интервью и тестовых заданий от топ-компаний, а также аналитику требований для резюме и тренажеры с режимом симуляции собеседования под конкретную компанию.
Акция до 20 февраля (включительно) на PRO-тариф. Покупаешь сейчас один раз — пользуешься всю жизнь без лимита, включая все будущие функции.
👉 Смотри подробности тарифа и покупай на https://easyoffer.ru/
3 210
Задача: 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 210
Задача: 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;
}
};