C/C++ | LeetCode
Відкрити в Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
Показати більше
Сітка:3 237
Підписники
+124 години
+77 днів
-430 день
Архів дописів
3 237
Задача: 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 237
Сегодня последний день, когда можно приобрести пожизненный PRO тариф easyoffer
Акция до 20 февраля 00:00
Покупаешь сейчас один раз — пользуешься всю жизнь без лимита, включая все будущие функции.
👉 Смотри подробности тарифа и покупай на https://easyoffer.ru/
3 237
Задача: 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 237
Задача: 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 237
Завтра конец акции на возможность приобрести PRO тариф по цене одного года
Доступный функционал включает базы вопросов с собеседований, задач для live-coding, реальных интервью и тестовых заданий от топ-компаний, а также аналитику требований для резюме и тренажеры с режимом симуляции собеседования под конкретную компанию.
Акция до 20 февраля (включительно) на PRO-тариф. Покупаешь сейчас один раз — пользуешься всю жизнь без лимита, включая все будущие функции.
👉 Смотри подробности тарифа и покупай на https://easyoffer.ru/
3 237
Задача: 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 237
Задача: 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 237
Задача: 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 237
Задача: 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 237
Задача: 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 237
Пожизненная PRO подписка на easyoffer по цене одного года.
Акция до 20 февраля. Покупаешь сейчас один раз – пользуешься всю жизнь без лимита, включая все будущие функции.
Запланированные новые фичи на ближайшие пол года:
1. Агрегатор вакансий
2. Улучшение резюме, чтобы проходить ATS системы
3. Генерация уникального резюме и сопроводительного письма под вакансию
Покупай на https://easyoffer.ru/
3 237
Задача: 921. Minimum Add to Make Parentheses Valid
Сложность: medium
Строка со скобками допустима тогда и только тогда, когда: это пустая строка, ее можно записать как AB (A, совмещенное с B), где A и B - допустимые строки, или ее можно записать как (A), где A - допустимая строка. Вам дана строка s со скобками. За один ход вы можете вставить скобку в любую позицию строки. Например, если s = "()))", вы можете вставить открывающую скобку в виде "(()))" или закрывающую скобку в виде "())))". Верните минимальное количество ходов, необходимое для того, чтобы сделать s допустимой.
Пример:
Input: n = 3, goal = 3, k = 1 Output: 6👨💻 Алгоритм: 1⃣Инициализировать два счетчика open_needed и close_needed. 2⃣Пройти по строке s символ за символом: Если текущий символ - открывающая скобка (, увеличьте open_needed. Если текущий символ - закрывающая скобка ), проверьте: Если open_needed больше 0, уменьшите open_needed. Иначе увеличьте close_needed. 3⃣Суммируйте значения open_needed и close_needed, чтобы получить минимальное количество вставок. 😎 Решение:
class Solution {
public:
int minAddToMakeValid(string s) {
int openNeeded = 0, closeNeeded = 0;
for (char c : s) {
if (c == '(') {
openNeeded++;
} else if (c == ')') {
if (openNeeded > 0) {
openNeeded--;
} else {
closeNeeded++;
}
}
}
return openNeeded + closeNeeded;
}
};3 237
Задача: 923. 3Sum With Multiplicity
Сложность: medium
Если задан целочисленный массив arr и целое число target, верните количество кортежей i, j, k, таких, что i < j < k и arr[i] + arr[j] + arr[k] == target. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7.
Пример:
Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8 Output: 20👨💻 Алгоритм: 1⃣Отсортировать массив arr. 2⃣Инициализировать счетчик для количества кортежей. Пройти по массиву тремя указателями i, j, и k: Для каждого i, установить j на i + 1, и k на конец массива. Использовать двухуказательный метод для нахождения пар (j, k), таких что arr[i] + arr[j] + arr[k] == target. 3⃣Вернуть результат по модулю 10^9 + 7. 😎 Решение:
class Solution {
public:
int threeSumMulti(vector<int>& arr, int target) {
sort(arr.begin(), arr.end());
const int MOD = 1'000'000'007;
long long count = 0;
for (int i = 0; i < arr.size(); i++) {
int j = i + 1, k = arr.size() - 1;
while (j < k) {
int sum = arr[i] + arr[j] + arr[k];
if (sum == target) {
if (arr[j] == arr[k]) {
count += (k - j + 1) * (k - j) / 2;
break;
} else {
int left = 1, right = 1;
while (j + 1 < k && arr[j] == arr[j + 1]) {
left++;
j++;
}
while (k - 1 > j && arr[k] == arr[k - 1]) {
right++;
k--;
}
count += (long long)left * right;
j++;
k--;
}
} else if (sum < target) {
j++;
} else {
k--;
}
}
}
return count % MOD;
}
};3 237
Задача: 830. Positions of Large Groups
Сложность: easy
В строке s из строчных букв эти буквы образуют последовательные группы одного и того же символа.
Например, строка s = "abbxxxxzyy" имеет группы "a", "bb", "xxxx", "z" и "yy".
Группа идентифицируется интервалом [start, end], где start и end обозначают начальный и конечный индексы (включительно) группы. В приведенном выше примере "xxxx" имеет интервал [3,6].
Группа считается большой, если в ней 3 или более символов.
Верните интервалы каждой большой группы, отсортированные в порядке возрастания начального индекса.
Пример:
Input: s = "abcdddeeeeaabbbcd" Output: [[3,5],[6,9],[12,14]] Explanation: The large groups are "ddd", "eeee", and "bbb".👨💻 Алгоритм: 1⃣Поддерживайте указатели i и j, где i <= j. Указатель i представляет начало текущей группы, а j будет инкрементироваться вперед, пока не достигнет конца группы. 2⃣Когда j достигнет конца строки или S[j] != S[j+1], у нас будет группа [i, j]. Если длина группы больше или равна 3, добавьте её в результат. 3⃣Обновите i = j + 1 и начните новую группу. 😎 Решение:
#include <vector>
#include <string>
using namespace std;
class Solution {
public:
vector<vector<int>> largeGroupPositions(string S) {
vector<vector<int>> ans;
int i = 0, N = S.size();
for (int j = 0; j < N; ++j) {
if (j == N - 1 || S[j] != S[j + 1]) {
if (j - i + 1 >= 3) {
ans.push_back({i, j});
}
i = j + 1;
}
}
return ans;
}
};3 237
Задача: 18. 4Sum
Сложность: medium
Дан массив nums из n целых чисел и целое число target.
Найди все уникальные четверки чисел [nums[a], nums[b], nums[c], nums[d]], такие что сумма равна target, а индексы — различные.
Пример:
Input: nums = [1,0,-1,0,-2,2], target = 0 Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]👨💻 Алгоритм: 1⃣Отсортируй массив nums, чтобы можно было применять метод двух указателей. 2⃣Зафиксируй два элемента (a, b) с помощью вложенных циклов, и для оставшихся двух (c, d) используй два указателя. 3⃣Подбирай четверки, сумма которых равна target, и добавляй их в результат, проверяя на уникальность. 😎 Решение:
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for (int a = 0; a < n; a++) {
for (int b = a + 1; b < n; b++) {
int c = b + 1;
int d = n - 1;
while (c < d) {
long long sum = nums[a];
sum += nums[b];
sum += nums[c];
sum += nums[d];
if (sum < target) {
c++;
} else if (sum > target) {
d--;
} else {
vector<int> v = {nums[a], nums[b], nums[c], nums[d]};
if (find(ans.begin(), ans.end(), v) == ans.end()) {
ans.push_back(v);
}
c++;
d--;
}
}
}
}
return ans;
}
};3 237
Задача: 1119. Remove Vowels from a String
Сложность: easy
Дана строка s, удалите из нее гласные 'a', 'e', 'i', 'o' и 'u' и верните новую строку.
Пример:
Input: s = "leetcodeisacommunityforcoders" Output: "ltcdscmmntyfrcdrs"👨💻 Алгоритм: 1⃣Создайте метод isVowel(), который возвращает true, если переданный символ является одной из гласных [a, e, i, o, u], и false в противном случае. 2⃣Инициализируйте пустую строку ans. 3⃣Пройдитесь по каждому символу в строке s, и для каждого символа c проверьте, является ли он гласной, используя isVowel(c). Если нет, добавьте символ в строку ans. В конце верните строку ans. 😎 Решение:
class Solution {
public:
string removeVowels(string s) {
string ans;
for (char c : s) {
if (!isVowel(c)) {
ans += c;
}
}
return ans;
}
private:
bool isVowel(char c) {
return c == 'a' || c == 'i' || c == 'e' || c == 'o' || c == 'u';
}
};3 237
Задача: 1004. Max Consecutive Ones III
Сложность: medium
Если задан двоичный массив nums и целое число k, верните максимальное количество последовательных 1 в массиве, если можно перевернуть не более k 0.
Пример:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2 Output: 6👨💻 Алгоритм: 1⃣Инициализация оконного подхода: Используйте два указателя для создания скользящего окна. Инициализируйте левый указатель в начале массива, правый указатель будет двигаться по массиву. Создайте переменную для подсчета количества нулей в текущем окне. 2⃣Перемещение правого указателя и обновление окна: Перемещайте правый указатель по массиву, обновляя количество нулей в текущем окне. Если количество нулей превышает k, сдвиньте левый указатель вправо до тех пор, пока количество нулей снова не станет допустимым (меньше или равно k). 3⃣Подсчет максимального количества последовательных единиц: На каждом шаге обновляйте максимальное количество последовательных единиц, сравнивая текущую длину окна (разница между правым и левым указателями) с текущим максимумом. 😎 Решение:
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left = 0, max_ones = 0, zero_count = 0;
for (int right = 0; right < nums.size(); ++right) {
if (nums[right] == 0) {
++zero_count;
}
while (zero_count > k) {
if (nums[left] == 0) {
--zero_count;
}
++left;
}
max_ones = max(max_ones, right - left + 1);
}
return max_ones;
}
};3 237
Задача: 904. Fruit Into Baskets
Сложность: medium
Вы посещаете ферму, где в один ряд слева направо расположены фруктовые деревья. Деревья представлены целочисленным массивом fruits, где fruits[i] - это тип фрукта, который производит i-е дерево. Вы хотите собрать как можно больше фруктов. Однако у владельца есть строгие правила, которым вы должны следовать: у вас есть только две корзины, и каждая корзина может содержать только один тип фруктов. Количество фруктов в каждой корзине не ограничено. Начиная с любого дерева по вашему выбору, вы должны собрать ровно один фрукт с каждого дерева (включая начальное), двигаясь при этом вправо. Собранные фрукты должны поместиться в одну из ваших корзин. Как только вы достигнете дерева с фруктами, которые не могут поместиться в ваши корзины, вы должны остановиться. Учитывая целочисленный массив fruits, верните максимальное количество фруктов, которое вы можете собрать.
Пример:
Input: fruits = [1,2,1] Output: 3👨💻 Алгоритм: 1⃣Использовать метод скользящего окна для поддержания текущего подмассива, содержащего не более двух типов фруктов. 2⃣Перемещать правый указатель, расширяя окно, и обновлять количество каждого типа фрукта в окне. Если количество типов фруктов в окне превышает два, перемещать левый указатель, уменьшая окно, пока в окне снова не будет не более двух типов фруктов. 3⃣Подсчитывать максимальное количество фруктов, собранных на каждом шаге. 😎 Решение:
class Solution {
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int, int> basket;
int left = 0;
int maxFruits = 0;
for (int right = 0; right < fruits.size(); ++right) {
basket[fruits[right]]++;
while (basket.size() > 2) {
basket[fruits[left]]--;
if (basket[fruits[left]] == 0) {
basket.erase(fruits[left]);
}
++left;
}
maxFruits = max(maxFruits, right - left + 1);
}
return maxFruits;
}
};3 237
Задача: 1137. N-th Tribonacci Number
Сложность: easy
Трибоначчи последовательность Tn определяется следующим образом:
T0 = 0, T1 = 1, T2 = 1, и Tn+3 = Tn + Tn+1 + Tn+2 для n >= 0.
Дано n, вернуть значение Tn.
Пример:
Input: n = 4 Output: 4 Explanation: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4👨💻 Алгоритм: 1⃣Если n < 3, вернуть значение n-го терма, как указано в описании задачи. 2⃣Инициализировать a, b и c как базовые случаи. Установить a = 0, b = 1, c = 1. 3⃣Для следующих n - 2 шагов обновлять a, b, c следующим образом: a = b, b = c, c = a + b + c. Вернуть c. 😎 Решение:
class Solution {
public:
int tribonacci(int n) {
if (n < 3) {
return n > 0 ? 1 : 0;
}
int a = 0, b = 1, c = 1;
for (int i = 0; i < n - 2; ++i) {
int tmp = a + b + c;
a = b;
b = c;
c = tmp;
}
return c;
}
};3 237
Задача: 1086. High Five
Сложность: easy
Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.
Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.
Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.
Пример:
Input: items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]
Output: [[1,100],[7,100]]class Solution {
private:
int K = 5;
public:
vector<vector<int>> highFive(vector<vector<int>>& items) {
sort(items.begin(), items.end(),
[](const vector<int> &a, const vector<int> &b) {
if (a[0] != b[0])
return a[0] < b[0];
return a[1] > b[1];
});
vector<vector<int>> solution;
int n = items.size();
int i = 0;
while (i < n) {
int id = items[i][0];
int sum = 0;
for (int k = i; k < i + K; ++k)
sum += items[k][1];
while (i < n && items[i][0] == id)
i++;
solution.push_back({id, sum / K});
}
return solution;
}
};