C/C++ | LeetCode
Відкрити в Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Показати більше
Сітка:3 211
Підписники
-224 години
-127 днів
-1730 днів
Архів дописів
3 210
Задача: 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 210
Задача: 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 210
Задача: 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 210
Пожизненная PRO подписка на easyoffer по цене одного года.
Акция до 20 февраля. Покупаешь сейчас один раз – пользуешься всю жизнь без лимита, включая все будущие функции.
Запланированные новые фичи на ближайшие пол года:
1. Агрегатор вакансий
2. Улучшение резюме, чтобы проходить ATS системы
3. Генерация уникального резюме и сопроводительного письма под вакансию
Покупай на https://easyoffer.ru/
3 210
Задача: 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 210
Задача: 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 210
Задача: 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 210
Задача: 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 210
Задача: 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 210
Задача: 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 210
Задача: 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 210
Задача: 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 210
Задача: 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;
}
};3 210
Задача: 1000. Minimum Cost to Merge Stones
Сложность: hard
Имеется n кучек камней, расположенных в ряд. В i-й куче находятся камни stones[i]. Ход состоит в объединении ровно k последовательных куч в одну кучу, и стоимость этого хода равна общему количеству камней в этих k кучах. Верните минимальную стоимость объединения всех куч камней в одну кучу. Если это невозможно, верните -1.
Пример:
Input: stones = [3,2,4,1], k = 2 Output: 20👨💻 Алгоритм: 1⃣Проверка на возможность объединения: Проверьте, можно ли объединить все кучи в одну, если количество куч n не равно 1 по модулю k-1. Если нет, верните -1. 2⃣Инициализация и динамическое программирование: Создайте таблицу dp для хранения минимальных затрат на объединение подмассивов камней. Используйте таблицу prefix для хранения префиксных сумм камней, чтобы быстро вычислять сумму камней в подмассиве. 3⃣Заполнение таблицы dp: Заполните таблицу dp минимальными затратами на объединение подмассивов камней, используя динамическое программирование. Для каждого подмассива длиной от k до n, найдите минимальную стоимость его объединения. 😎 Решение:
class Solution {
public:
int mergeStones(vector<int>& stones, int k) {
int n = stones.size();
if ((n - 1) % (k - 1) != 0) return -1;
vector<int> prefix(n + 1, 0);
for (int i = 0; i < n; ++i) {
prefix[i + 1] = prefix[i] + stones[i];
}
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int m = k; m <= n; ++m) {
for (int i = 0; i <= n - m; ++i) {
int j = i + m - 1;
dp[i][j] = INT_MAX;
for (int t = i; t < j; t += k - 1) {
dp[i][j] = min(dp[i][j], dp[i][t] + dp[t + 1][j]);
}
if ((j - i) % (k - 1) == 0) {
dp[i][j] += prefix[j + 1] - prefix[i];
}
}
}
return dp[0][n - 1];
}
};3 210
Задача: 644. Maximum Average Subarray II
Сложность: hard
Вам дан целочисленный массив nums, состоящий из n элементов, и целое число k. Найдите смежный подмассив, длина которого больше или равна k и который имеет максимальное среднее значение, и верните это значение. Принимается любой ответ с погрешностью вычислений менее 10-5.
Пример:
Input: nums = [1,12,-5,-6,50,3], k = 4 Output: 12.75000👨💻 Алгоритм: 1⃣Используйте скользящее окно длины k для нахождения начального среднего значения. 2⃣Перемещайте окно по массиву, добавляя следующий элемент и убирая предыдущий, обновляя текущее среднее значение. 3⃣Следите за максимальным средним значением и верните его после проверки всех возможных окон. 😎 Решение:
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int n = nums.size();
int currSum = accumulate(nums.begin(), nums.begin() + k, 0);
int maxSum = currSum;
for (int i = k; i < n; i++) {
currSum += nums[i] - nums[i - k];
if (currSum > maxSum) {
maxSum = currSum;
}
}
return maxSum / (double) k;
}
};3 210
Задача: 1279. Traffic Light Controlled Intersection
Сложность: easy
Здесь есть пересечение двух дорог. Первая дорога - это дорога A, по которой автомобили движутся с севера на юг в направлении 1 и с юга на север в направлении 2. Вторая дорога - дорога B, по которой машины едут с запада на восток в направлении 3 и с востока на запад в направлении 4. На каждой дороге перед перекрестком есть светофор. Зеленый означает, что автомобили могут пересекать перекресток в обоих направлениях. Красный означает, что автомобили в обоих направлениях не могут пересекать перекресток и должны ждать, пока загорится зеленый свет. Светофор не может гореть зеленым одновременно на обеих дорогах. Это значит, что когда на дороге А горит зеленый свет, на дороге Б он красный, а когда на дороге Б горит зеленый свет, на дороге А он красный.
Изначально на дороге A горит зеленый сигнал светофора, а на дороге B - красный. Когда на одной дороге горит зеленый свет, все автомобили могут пересекать перекресток в обоих направлениях, пока на другой дороге не загорится зеленый.Два автомобиля, движущиеся по разным дорогам, не должны пересекать перекресток одновременно. Разработайте систему управления светофором на этом перекрестке без тупиков. Реализуйте функцию void carArrived(carId, roadId, direction, turnGreen, crossCar), где: carId - идентификатор автомобиля, который приехал. roadId - идентификатор дороги, по которой едет автомобиль.
direction - направление движения автомобиля. turnGreen - функция, которую можно вызвать, чтобы переключить светофор на зеленый свет на текущей дороге. crossCar - функция, которую можно вызвать, чтобы позволить текущему автомобилю пересечь перекресток. Ваш ответ считается правильным, если он позволяет избежать тупика на перекрестке.Переключение светофора на зеленый свет на дороге, где он уже был зеленым, считается неправильным ответом.
Пример:
Input: cars = [1,2,3,4,5], directions = [2,4,3,3,1], arrivalTimes = [10,20,30,40,40] Output: [ "Car 1 Has Passed Road A In Direction 2", // Traffic light on road A is green, car 1 can cross the intersection. "Traffic Light On Road B Is Green", // Car 2 requests green light for road B. "Car 2 Has Passed Road B In Direction 4", // Car 2 crosses as the light is green on road B now. "Car 3 Has Passed Road B In Direction 3", // Car 3 crosses as the light is green on road B now. "Traffic Light On Road A Is Green", // Car 5 requests green light for road A. "Car 5 Has Passed Road A In Direction 1", // Car 5 crosses as the light is green on road A now. "Traffic Light On Road B Is Green", // Car 4 requests green light for road B. Car 4 blocked until car 5 crosses and then traffic light is green on road B. "Car 4 Has Passed Road B In Direction 3" // Car 4 crosses as the light is green on road B now. ]👨💻 Алгоритм: 1⃣Если на дороге, по которой едет автомобиль, уже зеленый свет, вызываем функцию crossCar. 2⃣Если на дороге, по которой едет автомобиль, красный свет, вызываем функцию turnGreen, чтобы переключить свет на зеленый, и затем вызываем функцию crossCar. 3⃣Обеспечиваем, что функции turnGreen и crossCar вызываются атомарно для предотвращения гонок и тупиков. 😎 Решение:
class TrafficLight {
private:
int greenRoad = 1;
std::mutex mtx;
public:
void carArrived(
int carId,
int roadId,
int direction,
std::function<void()> turnGreen,
std::function<void()> crossCar
) {
std::lock_guard<std::mutex> lock(mtx);
if (greenRoad != roadId) {
turnGreen();
greenRoad = roadId;
}
crossCar();
}
};3 210
Задача: 762. Prime Number of Set Bits in Binary Representation
Сложность: hard
Если даны два целых числа left и right, верните количество чисел в диапазоне [left, right], имеющих простое число битов в двоичном представлении. Напомним, что число битов в двоичном представлении - это количество единиц, присутствующих в числе 1. Например, 21 в двоичном представлении - это 10101, которое имеет 3 бита.
Пример:
Input: left = 10, right = 15 Output: 5👨💻 Алгоритм: 1⃣Создайте функцию для подсчета количества единиц в двоичном представлении числа. 2⃣Создайте функцию для проверки, является ли число простым. 3⃣Пройдите через все числа в диапазоне [left, right] и подсчитайте числа, у которых количество битов в двоичном представлении является простым числом. 😎 Решение:
class Solution {
public:
int countPrimeSetBits(int left, int right) {
int count = 0;
for (int num = left; num <= right; num++) {
if (isPrime(__builtin_popcount(num))) {
count++;
}
}
return count;
}
private:
bool isPrime(int x) {
if (x < 2) return false;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
};3 210
Задача: 1406. Stone Game III
Сложность: hard
Алиса и Боб продолжают свои игры с кучами камней. Камни расположены в ряд, и каждый камень имеет ассоциированное значение, которое представлено целым числом в массиве stoneValue.
Алиса и Боб ходят по очереди, начиная с Алисы. В свой ход каждый игрок может взять 1, 2 или 3 камня из первых оставшихся камней в ряду.
Счет каждого игрока равен сумме значений взятых камней. Изначально счет каждого игрока равен 0.
Цель игры — закончить с наивысшим счетом, и победителем становится игрок с наивысшим счетом, при этом возможна ничья. Игра продолжается, пока все камни не будут взяты.
Предположим, что Алиса и Боб играют оптимально.
Верните "Alice", если Алиса выиграет, "Bob", если выиграет Боб, или "Tie", если они закончат игру с одинаковым счетом.
Пример:
Input: stoneValue = [1,2,3,7] Output: "Bob" Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.👨💻 Алгоритм: 1⃣Инициализируйте массив dp размером n+1 и установите dp[n] в 0. 2⃣Итеративно обновляйте dp[i] для всех i от n-1 до 0, вычисляя максимальную разницу в баллах, которые могут получить игроки при оптимальной игре. 3⃣Определите победителя, сравнивая dp[0] с 0: если больше, победит Алиса; если меньше, победит Боб; если равно, будет ничья. 😎 Решение:
class Solution {
public:
string stoneGameIII(vector<int>& stoneValue) {
int n = stoneValue.size();
vector<int> dp(n + 1, 0);
for (int i = n - 1; i >= 0; --i) {
dp[i] = stoneValue[i] - dp[i + 1];
if (i + 2 <= n) {
dp[i] = max(dp[i], stoneValue[i] + stoneValue[i + 1] - dp[i + 2]);
}
if (i + 3 <= n) {
dp[i] = max(dp[i], stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] - dp[i + 3]);
}
}
if (dp[0] > 0) return "Alice";
if (dp[0] < 0) return "Bob";
return "Tie";
}
};3 210
Задача: 719. Find K-th Smallest Pair Distance
Сложность: hard
Расстояние между парой целых чисел a и b определяется как абсолютная разность между a и b. Учитывая целочисленный массив nums и целое число k, верните k-е наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 <= i < j < nums.length.
Пример:
Input: nums = [1,3,1], k = 1 Output: 0👨💻 Алгоритм: 1⃣Отсортируйте массив nums. 2⃣Определите минимальное и максимальное возможные расстояния. 3⃣Используйте бинарный поиск, чтобы найти k-е наименьшее расстояние, проверяя количество пар с расстоянием меньше или равно текущему среднему значению. 😎 Решение:
int countPairs(const vector<int>& nums, int mid) {
int count = 0, j = 0;
for (int i = 0; i < nums.size(); i++) {
while (j < nums.size() && nums[j] - nums[i] <= mid) {
j++;
}
count += j - i - 1;
}
return count;
}
int smallestDistancePair(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int left = 0, right = nums.back() - nums.front();
while (left < right) {
int mid = (left + right) / 2;
if (countPairs(nums, mid) < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}3 210
Задача: 316. Remove Duplicate Letters
Сложность: medium
Дана строка
s, удалите повторяющиеся буквы так, чтобы каждая буква появилась один раз и только один раз. Вы должны сделать так, чтобы результат был наименьшим в лексикографическом порядке среди всех возможных результатов.
Пример:
Input: s = "bcabc" Output: "abc"👨💻 Алгоритм: 1⃣Инициализация стека Создайте стек, который будет хранить результат, построенный по мере итерации строки. 2⃣Итерация по строке На каждой итерации добавляйте текущий символ в стек, если он еще не был использован. Перед добавлением текущего символа удаляйте как можно больше символов из вершины стека, если это возможно и улучшает лексикографический порядок. 3⃣Удаление символов Удаляйте символы с вершины стека при выполнении следующих условий: Символ на вершине стека больше текущего символа. Символ может быть удален, так как он встречается позже в строке. На каждом этапе итерации по строке жадно минимизируйте содержимое стека. 😎 Решение:
class Solution {
public:
string removeDuplicateLetters(string s) {
vector<char> stack;
unordered_set<char> seen;
unordered_map<char, int> lastOccurrence;
for (int i = 0; i < s.size(); ++i) {
lastOccurrence[s[i]] = i;
}
for (int i = 0; i < s.size(); ++i) {
char c = s[i];
if (seen.find(c) == seen.end()) {
while (!stack.empty() && c < stack.back() && i < lastOccurrence[stack.back()]) {
seen.erase(stack.back());
stack.pop_back();
}
seen.insert(c);
stack.push_back(c);
}
}
return string(stack.begin(), stack.end());
}
};