C/C++ | LeetCode
Ir al canal en Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
Mostrar más
Red:3 210
Suscriptores
-224 horas
-127 días
-1730 días
Archivo de publicaciones
3 210
Задача: 929. Unique Email Addresses
Сложность: easy
Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока больше не останется ни одного узла, зараженного таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим ровно один узел из initial, полностью удалив его и все связи от этого узла к любому другому узлу. Верните узел, который, если его удалить, минимизирует M(initial). Если для минимизации M(initial) можно удалить несколько узлов, верните такой узел с наименьшим индексом.
Пример:
Input: emails = ["test.email+alex@leetcode.com","test.e.mail+bob.cathy@leetcode.com","testemail+david@lee.tcode.com"] Output: 2👨💻 Алгоритм: 1⃣Создать множество для хранения уникальных обработанных адресов электронной почты. 2⃣Для каждого адреса в emails: Разделить адрес на локальное и доменное имя по символу '@'. Обработать локальное имя: Удалить все точки '.'. Обрезать часть после символа '+'. Объединить обработанное локальное имя и доменное имя. Добавить результат в множество уникальных адресов. 3⃣Вернуть количество уникальных адресов в множестве. 😎 Решение:
class Solution {
public int numUniqueEmails(String[] emails) {
Set<String> uniqueEmails = new HashSet<>();
for (String email : emails) {
String[] parts = email.split("@");
String local = parts[0].split("\\+")[0].replace(".", "");
uniqueEmails.add(local + "@" + parts[1]);
}
return uniqueEmails.size();
}
}3 210
Пожизненный PRO доступ на easyoffer — по цене одного года!
До 31 марта вы можете купить PRO навсегда. Запускаем акцию, чтобы ускорить развитие сервиса.
Что добавим в PRO в ближайшие полгода:
– Автоотклики
– Агрегатор вакансий
– Проход ATS без отсева
– Уникальные резюме и письма под каждую вакансию
Покупаешь один раз — пользуешься всю жизнь.
👉 Купить PRO со скидкой 70%: https://easyoffer.ru/pro
3 210
Задача: 861. Score After Flipping Matrix
Сложность: medium
Вам дана бинарная матрица grid размером m x n.
Ход состоит из выбора любой строки или столбца и переключения каждого значения в этой строке или столбце (т.е. изменение всех 0 на 1, и всех 1 на 0).
Каждая строка матрицы интерпретируется как двоичное число, и счёт матрицы — это сумма этих чисел.
Верните наивысший возможный счёт после выполнения любого количества ходов (включая ноль ходов).
Пример:
Input: grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation: 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39class Solution {
public:
int matrixScore(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; ++i) {
if (grid[i][0] == 0) {
for (int j = 0; j < n; ++j) {
grid[i][j] ^= 1;
}
}
}
for (int j = 1; j < n; ++j) {
int countZero = 0;
for (int i = 0; i < m; ++i) {
if (grid[i][j] == 0) {
countZero++;
}
}
if (countZero > m / 2) {
for (int i = 0; i < m; ++i) {
grid[i][j] ^= 1;
}
}
}
int score = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
score += 1 << (n - j - 1);
}
}
}
return score;
}
};3 210
Задача: 32. Longest Valid Parentheses
Сложность: hard
Учитывая строку, содержащую только символы «(» и «)», верните длину самой длинной допустимой (правильно сформированной) подстроки скобок.
Пример:
Input: s = "(()" Output: 2👨💻 Алгоритм: 1⃣Используем стек для хранения индексов, начальное значение — -1. 2⃣Проходим по строке: если '(', кладем индекс в стек, если ')' — извлекаем элемент. 3⃣Если после извлечения стек пуст — кладем текущий индекс, иначе — обновляем максимум длины как i - stack.top(). 😎 Решение:
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> stack;
int m = 0;
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.empty()) {
stack.push(i);
} else {
m = max(m, (i - stack.top()));
}
}
}
return m;
}
};3 210
Задача: 1102. Path With Maximum Minimum Value
Сложность: medium
Дана целочисленная матрица grid размером m x n. Верните максимальное значение пути, начинающегося в (0, 0) и заканчивающегося в (m - 1, n - 1), двигаясь в 4 кардинальных направлениях.
Значение пути определяется минимальным числом на этом пути.
Пример:
Input: grid = [[5,4,5],[1,2,6],[7,4,6]] Output: 4 Explanation: The path with the maximum score is highlighted in yellow.👨💻 Алгоритм: 1⃣Начните с оценки curScore = min(grid[0][0], grid[m-1][n-1]), где m и n - общее количество строк и столбцов входной матрицы. 2⃣Выполните BFS на матрице и проверьте, существует ли путь, где все значения больше или равны curScore: Используйте очередь (deque) для хранения всех непосещенных ячеек со значением, большим или равным curScore. Извлекайте ячейку из начала очереди, проверяйте, есть ли у нее непосещенные соседние ячейки, и добавляйте их в конец очереди. Если успешно достигли правой нижней ячейки, значит путь существует. Если очередь опустела до достижения правой нижней ячейки, пути не существует. 3⃣Если пути не существует, что означает, что curScore слишком велик, уменьшите его на 1 и повторите шаг 2. В противном случае, верните curScore как ответ. 😎 Решение:
class Solution {
vector<vector<int>> dirs{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
public:
int maximumMinimumPath(vector<vector<int>>& grid) {
int R = grid.size(), C = grid[0].size();
int curScore = min(grid[0][0], grid[R - 1][C - 1]);
while (curScore >= 0) {
if (pathExists(grid, curScore)) {
return curScore;
} else {
curScore--;
}
}
return -1;
}
bool pathExists(vector<vector<int>>& grid, int curScore) {
int R = grid.size(), C = grid[0].size();
vector<vector<bool>> visited(R, vector<bool>(C, false));
deque<pair<int, int>> dq{{0, 0}};
visited[0][0] = true;
auto push = [&](int row, int col) {
if (row >= 0 && col >= 0 && row < R && col < C && !visited[row][col] && grid[row][col] >= curScore) {
dq.push_back({row, col});
visited[row][col] = true;
}
};
while (!dq.empty()) {
int curRow = dq.front().first, curCol = dq.front().second;
dq.pop_front();
if (curRow == R - 1 && curCol == C - 1) {
return true;
}
for (auto dir : dirs) {
push(curRow + dir[0], curCol + dir[1]);
}
}
return false;
}
};3 210
Задача: 502. IPO
Сложность: hard
Предположим, что LeetCode скоро начнет свое IPO. Чтобы продать свои акции по хорошей цене венчурным капиталистам, LeetCode хочет выполнить несколько проектов для увеличения своего капитала перед IPO. Поскольку у компании ограниченные ресурсы, она может завершить не более k различных проектов до IPO. Помогите LeetCode разработать лучший способ максимизации общего капитала после завершения не более k различных проектов.
Вам дано n проектов, где i-й проект имеет чистую прибыль profits[i] и требует минимального капитала capital[i] для его начала.
Изначально у вас есть капитал w. Когда вы завершаете проект, вы получаете его чистую прибыль, и эта прибыль добавляется к вашему общему капиталу.
Выберите список из не более чем k различных проектов из данных, чтобы максимально увеличить ваш конечный капитал, и верните окончательно максимизированный капитал.
Ответ гарантированно поместится в 32-битное целое число со знаком.
Пример:
Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1] Output: 4 Explanation: Since your initial capital is 0, you can only start the project indexed 0. After finishing it you will obtain profit 1 and your capital becomes 1. With capital 1, you can either start the project indexed 1 or the project indexed 2. Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital. Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.👨💻 Алгоритм: 1⃣Сортировка и инициализация Отсортируйте проекты по возрастанию капитала. Создайте указатель ptr на первый недоступный проект в отсортированном массиве. Создайте приоритетную очередь для прибылей доступных проектов. Изначально очередь пуста. 2⃣Выбор проектов Выполните следующие действия k раз: добавьте в приоритетную очередь прибыли новых доступных проектов. Перемещайте указатель по отсортированному массиву, когда проекты становятся доступными. Если приоритетная очередь пуста, завершите алгоритм. 3⃣Увеличение капитала Максимальное значение в приоритетной очереди — это прибыль проекта, который будет запущен сейчас. Увеличьте капитал на это значение. Удалите его из очереди, так как он больше не может быть использован. 😎 Решение:
class Solution {
public:
int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
vector<pair<int, int>> projects;
for (int i = 0; i < profits.size(); ++i) {
projects.emplace_back(capital[i], profits[i]);
}
sort(projects.begin(), projects.end());
priority_queue<int> maxHeap;
int ptr = 0;
for (int i = 0; i < k; ++i) {
while (ptr < projects.size() && projects[ptr].first <= w) {
maxHeap.push(projects[ptr].second);
ptr++;
}
if (maxHeap.empty()) break;
w += maxHeap.top();
maxHeap.pop();
}
return w;
}
};3 210
Задача: 638. Shopping Offers
Сложность: medium
В магазине LeetCode Store есть n предметов для продажи. Каждый товар имеет свою цену. Однако существуют специальные предложения, и специальное предложение состоит из одного или нескольких различных видов товаров с распродажной ценой. Вам дан целочисленный массив price, где price[i] - цена i-го товара, и целочисленный массив needs, где needs[i] - количество штук i-го товара, который вы хотите купить. Вам также дан массив special, где special[i] имеет размер n + 1, где special[i][j] - количество штук j-го товара в i-м предложении, а special[i][n] (т.е., Возвращает наименьшую цену, которую вы можете заплатить за определенный товар из заданных, где вы могли бы оптимально использовать специальные предложения. Вам не разрешается покупать больше товаров, чем вы хотите, даже если это снизит общую цену. Вы можете использовать любое из специальных предложений столько раз, сколько захотите.
Пример:
Input: price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2] Output: 14👨💻 Алгоритм: 1⃣Рекурсивное вычисление стоимости: Определите функцию, которая рекурсивно вычисляет минимальную стоимость для оставшихся нужд, используя динамическое программирование для запоминания уже вычисленных значений. 2⃣Использование специальных предложений: Для каждой комбинации товаров в специальных предложениях, определите, можно ли использовать это предложение без превышения нужд. Если можно, вычислите новую стоимость, учитывая это предложение. 3⃣Выбор минимальной стоимости: Сравните стоимость при использовании специальных предложений и стоимость при покупке товаров по индивидуальным ценам, выбирая минимальную стоимость. 😎 Решение:
class Solution {
public:
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
unordered_map<string, int> memo;
return dfs(price, special, needs, memo);
}
private:
int dfs(vector<int>& price, vector<vector<int>>& special, vector<int>& needs, unordered_map<string, int>& memo) {
string key = serialize(needs);
if (memo.find(key) != memo.end()) {
return memo[key];
}
int minPrice = 0;
for (int i = 0; i < needs.size(); i++) {
minPrice += needs[i] * price[i];
}
for (vector<int>& offer : special) {
vector<int> newNeeds(needs.size());
bool valid = true;
for (int i = 0; i < needs.size(); i++) {
if (needs[i] < offer[i]) {
valid = false;
break;
}
newNeeds[i] = needs[i] - offer[i];
}
if (valid) {
minPrice = min(minPrice, offer.back() + dfs(price, special, newNeeds, memo));
}
}
memo[key] = minPrice;
return minPrice;
}
string serialize(vector<int>& needs) {
string key = "";
for (int need : needs) {
key += to_string(need) + ",";
}
return key;
}
};3 210
Задача: №30. Substring with Concatenation of All Words
Сложность: hard
Вам дана строка s и массив строк words, где все слова одинаковой длины. Найдите все стартовые индексы подстрок в s, которые являются конкатенацией всех слов из массива (в любом порядке, без дополнительных символов между ними).
Пример:
Input: s = "barfoothefoobarman", words = ["foo","bar"] Output: [0,9]👨💻 Алгоритм: 1⃣Вычисляем длину каждого слова и общее количество слов. 2⃣Используем скользящее окно с шагом = длине слова, и на каждом шаге проверяем, входят ли текущие слова в заданный набор. 3⃣Отслеживаем, сколько раз каждое слово встречается, используя unordered_map. 😎 Решение:
vector<int> findSubstring(string str, vector<string>& words) {
int len = words[0].length();
unordered_map<string, int> contain;
for (string s : words) contain[s]++;
vector<int> res;
for (int j = 0; j < len; j++) {
unordered_map<string, int> found;
int st = j;
for (int i = j; i <= str.size() - len; i += len) {
string curr = str.substr(i, len);
if (contain.find(curr) != contain.end()) {
found[curr]++;
while (found[curr] > contain[curr]) {
found[str.substr(st, len)]--;
st += len;
}
int size = (i - st + len) / len;
if (size == words.size()) {
res.push_back(st);
}
} else {
found.clear();
st = i + len;
}
}
}
return res;
}3 210
Задача: 341. Flatten Nested List Iterator
Сложность: medium
Вам дан вложенный список целых чисел nestedList. Каждый элемент либо является целым числом, либо списком, элементы которого также могут быть целыми числами или другими списками. Реализуйте итератор для его развёртки.
Реализуйте класс NestedIterator:
NestedIterator(List<NestedInteger> nestedList) Инициализирует итератор вложенным списком nestedList.
int next() Возвращает следующий целый элемент вложенного списка.
boolean hasNext() Возвращает true, если в вложенном списке еще остались целые числа, и false в противном случае.
Пример:
Input: nestedList = [[1,1],2,[1,1]] Output: [1,1,2,1,1] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].👨💻 Алгоритм: 1⃣Инициализация Сохраняйте исходный вложенный список в стеке или очереди. Используйте стек для сохранения состояния итерации по вложенным спискам. 2⃣Метод next() Возвращает следующий целый элемент из стека или очереди. Если текущий элемент является списком, развёртывайте его и добавляйте элементы в стек. 3⃣Метод hasNext() Проверяет, есть ли в стеке или очереди оставшиеся целые элементы. Если на вершине стека находится список, развёртывайте его до тех пор, пока не встретится целый элемент. 😎 Решение:
class NestedIterator {
public:
NestedIterator(vector<NestedInteger> &nestedList) {
flatten(nestedList);
}
int next() {
return stack.back().getInteger();
}
bool hasNext() {
while (!stack.empty() && !stack.back().isInteger()) {
auto ni = stack.back();
stack.pop_back();
flatten(ni.getList());
}
return !stack.empty();
}
private:
void flatten(const vector<NestedInteger> &nestedList) {
for (auto it = nestedList.rbegin(); it != nestedList.rend(); ++it) {
stack.push_back(*it);
}
}
vector<NestedInteger> stack;
};3 210
Задача: 914. X of a Kind in a Deck of Cards
Сложность: easy
Вам дан целочисленный массив deck, где deck[i] - число, написанное на i-й карте. Разделите карты на одну или несколько групп так, чтобы: в каждой группе было ровно x карт, где x > 1, и на всех картах в одной группе было написано одно и то же целое число. Верните true, если такое разделение возможно, или false в противном случае.
Пример:
Input: deck = [1,2,3,4,4,3,2,1] Output: true👨💻 Алгоритм: 1⃣Создать словарь для подсчета частоты каждого числа в массиве deck. 2⃣Найти наибольший общий делитель (НОД) всех частот. 3⃣Проверить, больше ли НОД 1, чтобы определить, можно ли разделить карты на группы. 😎 Решение:
class Solution {
public:
bool hasGroupsSizeX(vector<int>& deck) {
unordered_map<int, int> count;
for (int num : deck) {
count[num]++;
}
int g = 0;
for (auto& [_, freq] : count) {
g = gcd(g, freq);
}
return g > 1;
}
private:
int gcd(int a, int b) {
while (b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}
};3 210
Задача: 1238. Circular Permutation in Binary Representation
Сложность: medium
Даны 2 целых числа n и start. Ваша задача - вернуть любую перестановку p из (0,1,2.....,2^n -1) такую, что : p[0] = start p[i] и p[i+1] отличаются только одним битом в их двоичном представлении. p[0] и p[2^n -1] также должны отличаться только одним битом в их двоичном представлении.
Пример:
Input: n = 2, start = 3 Output: [3,2,0,1]👨💻 Алгоритм: 1⃣Генерация Грей-кода: Генерация Грей-кода для чисел от 0 до 2𝑛−1 2⃣Определение начальной позиции: Находим индекс числа start в последовательности Грей-кода. 3⃣Построение перестановки: Формируем перестановку, начиная с числа start и следуя по циклическому Грей-коду. 😎 Решение:
vector<int> grayCode(int n) {
vector<int> result;
int num_elements = 1 << n;
for (int i = 0; i < num_elements; ++i) {
result.push_back(i ^ (i >> 1));
}
return result;
}
vector<int> circularPermutation(int n, int start) {
vector<int> gray = grayCode(n);
auto start_iter = find(gray.begin(), gray.end(), start);
vector<int> result;
result.insert(result.end(), start_iter, gray.end());
result.insert(result.end(), gray.begin(), start_iter);
return result;
}3 210
Задача: №26. Remove Duplicates from Sorted Array
Сложность: easy
Учитывая целочисленный массив nums, отсортированный в неубывающем порядке, удалите дубликаты на месте, чтобы каждый уникальный элемент появлялся только один раз. Порядок должен сохраняться. Верните количество уникальных элементов k, а в начале массива должны находиться именно эти уникальные значения.
Пример:
Input: nums = [1,1,2] Output: 2👨💻 Алгоритм: 1⃣Если массив пуст, возвращаем 0. 2⃣Инициализируем k = 1 — позиция для следующего уникального элемента. 3⃣Проходим по массиву и при нахождении нового уникального значения — записываем его в nums[k] и увеличиваем k. 😎 Решение:
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.empty()) {
return 0;
}
int k = 1;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] != nums[i - 1]) {
nums[k] = nums[i];
k++;
}
}
return k;
}
};3 210
Задача: 852. Peak Index in a Mountain Array
Сложность: medium
Вам дан целочисленный массив горы arr длины n, где значения увеличиваются до пикового элемента, а затем уменьшаются.
Верните индекс пикового элемента.
Ваша задача — решить это с временной сложностью O(log(n)).
Пример:
Input: arr = [0,1,0]
Output: 1class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int i = 0;
while (arr[i] < arr[i + 1]) {
i++;
}
return i;
}
};3 210
Задача: 714. Best Time to Buy and Sell Stock with Transaction Fee
Сложность: medium
Вам дан массив prices, где prices[i] - это цена данной акции в i-й день, и целое число fee, представляющее собой комиссию за сделку. Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить сколько угодно сделок, но за каждую сделку вам придется заплатить комиссию. Примечание: Вы не можете совершать несколько сделок одновременно (то есть вы должны продать акции, прежде чем купить их снова). Комиссия за сделку взимается только один раз за каждую покупку и продажу акций.
Пример:
Input: prices = [1,3,2,8,4,9], fee = 2 Output: 8👨💻 Алгоритм: 1⃣Инициализируйте две переменные: cash, представляющую максимальную прибыль без наличия акций, и hold, представляющую максимальную прибыль с наличием акций. 2⃣Пройдите по каждому элементу массива prices и обновите значения cash и hold, используя текущую цену и комиссию. 3⃣Верните значение cash, которое будет максимальной прибылью без наличия акций. 😎 Решение:
int maxProfit(vector<int>& prices, int fee) {
int cash = 0, hold = -prices[0];
for (int price : prices) {
cash = max(cash, hold + price - fee);
hold = max(hold, cash - price);
}
return cash;
}3 210
Задача: 1234. Replace the Substring for Balanced String
Сложность: medium
Вам дана строка s длины n, содержащая только четыре вида символов: 'Q', 'W', 'E' и 'R'. Строка считается сбалансированной, если каждый из ее символов встречается n / 4 раз, где n - длина строки. Верните минимальную длину подстроки, которую можно заменить любой другой строкой той же длины, чтобы сделать s сбалансированной. Если s уже сбалансирована, верните 0.
Пример:
Input: s = "QWER" Output: 0👨💻 Алгоритм: 1⃣Проверка баланса: Сначала проверим, сбалансирована ли строка s. Если да, то возвращаем 0. 2⃣Подсчет частоты символов: Подсчитаем количество каждого символа в строке s. 3⃣Использование скользящего окна: Используем метод двух указателей (скользящее окно) для нахождения минимальной подстроки, которую можно заменить, чтобы строка стала сбалансированной. Начнем с окна, которое захватывает всю строку, и будем постепенно уменьшать его, проверяя при каждом шаге, становится ли строка сбалансированной. 😎 Решение:
class Solution {
public:
int balancedString(string s) {
int n = s.size();
unordered_map<char, int> count;
for (char c : s) count[c]++;
int target = n / 4;
auto is_balanced = [&]() {
return count['Q'] <= target && count['W'] <= target && count['E'] <= target && count['R'] <= target;
};
if (is_balanced()) return 0;
int min_length = n;
int left = 0;
for (int right = 0; right < n; ++right) {
count[s[right]]--;
while (is_balanced()) {
min_length = min(min_length, right - left + 1);
count[s[left]]++;
left++;
}
}
return min_length;
}
};3 210
Задача: 24. Swap Nodes in Pairs
Сложность: medium
Учитывая связанный список, поменяйте местами каждые два соседних узла и верните его голову. Вы должны решить проблему, не изменяя значения в узлах списка (т. е. изменять можно только сами узлы).
Пример:
Input: head = [1,2,3,4] Output: [2,1,4,3]👨💻 Алгоритм: 1⃣Создаем фиктивный узел temp, указывающий на head, чтобы упростить работу с началом списка. 2⃣Пока существуют хотя бы два узла для обмена — выполняем перестановку указателей для соседней пары. 3⃣Продвигаем указатель к следующей паре. 😎 Решение:
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode *temp = (ListNode*)malloc(sizeof(ListNode));
temp->next = head;
ListNode *ptr = temp, *swap1, *swap2;
while(ptr->next && ptr->next->next) {
swap1 = ptr->next;
swap2 = ptr->next->next;
swap1->next = swap2->next;
swap2->next = swap1;
ptr->next = swap2;
ptr = swap1;
}
return temp->next;
}
};3 210
Задача: 1053. Previous Permutation With One Swap
Сложность: medium
Учитывая массив целых положительных чисел arr (не обязательно различных), верните лексикографически наибольшую перестановку, которая меньше arr и может быть сделана ровно с одной подстановкой. Если это невозможно, то верните тот же массив. Обратите внимание, что перестановка меняет местами два числа arr[i] и arr[j].
Пример:
Input: arr = [3,2,1] Output: [3,1,2]👨💻 Алгоритм: 1⃣Определи общее количество покупателей, которые удовлетворены в минуты, когда владелец магазина не ворчлив. 2⃣Пройди по массиву, используя скользящее окно для учета эффекта от техники. 3⃣Найди максимальное количество дополнительных удовлетворенных покупателей, которые можно получить, используя технику на k минут подряд. 😎 Решение:
class Solution {
public:
vector<int> prevPermOpt1(vector<int>& arr) {
int n = arr.size();
int i;
for (i = n - 2; i >= 0; i--) {
if (arr[i] > arr[i + 1]) {
break;
}
}
if (i == -1) {
return arr;
}
int j;
for (j = n - 1; j > i; j--) {
if (arr[j] < arr[i] && (j == n - 1 || arr[j] != arr[j + 1])) {
break;
}
}
swap(arr[i], arr[j]);
return arr;
}
};3 210
Задача: 971. Flip Binary Tree To Match Preorder Traversal
Сложность: medium
Дано корневое дерево с n узлами, где каждому узлу уникально присвоено значение от 1 до n. Также дана последовательность из n значений voyage, которая является желаемым обходом дерева в порядке pre-order.
Любой узел в бинарном дереве можно перевернуть, поменяв местами его левое и правое поддеревья. Например, переворот узла 1 будет иметь следующий эффект:
Переверните минимальное количество узлов, чтобы обход дерева в порядке pre-order соответствовал voyage.
Верните список значений всех перевернутых узлов. Вы можете вернуть ответ в любом порядке. Если невозможно перевернуть узлы в дереве, чтобы сделать обход в порядке pre-order соответствующим voyage, верните список [-1].
Пример:
Input: root = [1,2], voyage = [2,1] Output: [-1] Explanation: It is impossible to flip the nodes such that the pre-order traversal matches voyage.👨💻 Алгоритм: 1⃣Выполните поиск в глубину. Если в каком-либо узле значение узла не соответствует значению в voyage, верните [-1]. 2⃣Иначе определите, когда нужно перевернуть: если следующее ожидаемое число в voyage (voyage[i]) отличается от следующего потомка. 3⃣Переверните узел, добавьте его значение в список перевернутых узлов и продолжите обход дерева, пока весь порядок обхода pre-order не будет соответствовать voyage. 😎 Решение:
class Solution {
public:
vector<int> flipped;
int index;
vector<int> voyage;
vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
flipped.clear();
index = 0;
this->voyage = voyage;
dfs(root);
if (!flipped.empty() && flipped[0] == -1) {
return {-1};
}
return flipped;
}
void dfs(TreeNode* node) {
if (node != nullptr) {
if (node->val != voyage[index++]) {
flipped = {-1};
return;
}
if (index < voyage.size() && node->left != nullptr && node->left->val != voyage[index]) {
flipped.push_back(node->val);
dfs(node->right);
dfs(node->left);
} else {
dfs(node->left);
dfs(node->right);
}
}
}
};3 210
Задача: 952. Largest Component Size by Common Factor
Сложность: hard
Для бинарного дерева T мы можем определить операцию переворота следующим образом: выбираем любой узел и меняем местами левое и правое дочерние поддеревья. Бинарное дерево X эквивалентно бинарному дереву Y тогда и только тогда, когда мы можем сделать X равным Y после некоторого количества операций переворота. Учитывая корни двух бинарных деревьев root1 и root2, верните true, если эти два дерева эквивалентны перевороту, или false в противном случае.
Пример:
Input: nums = [4,6,15,35] Output: 4👨💻 Алгоритм: 1⃣Построить граф, в котором узлы представляют числа из массива, а ребра между узлами существуют, если два числа имеют общий делитель больше 1. 2⃣Использовать алгоритм Union-Find для объединения узлов в связные компоненты. Для каждого числа в массиве nums найти его простые делители и использовать их для объединения узлов. 3⃣Найти размер наибольшей связной компоненты. 😎 Решение:
class Solution {
public:
int largestComponentSize(vector<int>& nums) {
unordered_map<int, int> parent;
unordered_map<int, int> rank;
for (int num : nums) {
parent[num] = num;
rank[num] = 0;
}
function<int(int)> find = [&](int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
};
auto unionFind = [&](int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
};
auto primeFactors = [&](int n) {
unordered_set<int> factors;
int d = 2;
while (d * d <= n) {
while (n % d == 0) {
factors.insert(d);
n /= d;
}
d++;
}
if (n > 1) {
factors.insert(n);
}
return factors;
};
unordered_map<int, vector<int>> primeToIndex;
for (int num : nums) {
auto primes = primeFactors(num);
for (int prime : primes) {
primeToIndex[prime].push_back(num);
}
}
for (const auto& primes : primeToIndex) {
for (int i = 1; i < primes.second.size(); i++) {
unionFind(primes.second[0], primes.second[i]);
}
}
unordered_map<int, int> size;
for (int num : nums) {
int root = find(num);
size[root]++;
}
int maxSize = 0;
for (const auto& [key, value] : size) {
maxSize = max(maxSize, value);
}
return maxSize;
}
};3 210
Задача: 730. Count Different Palindromic Subsequences
Сложность: hard
Поскольку ответ может быть очень большим, верните его по модулю 109 + 7. Подпоследовательность строки получается путем удаления из нее нуля или более символов. Последовательность является палиндромной, если она равна последовательности, обращенной назад. Две последовательности a1, a2, ... и b1, b2, ... различны, если существует некоторое i, для которого ai != bi.
Пример:
Input: s = "bccb" Output: 6👨💻 Алгоритм: 1⃣Используйте динамическое программирование для подсчета количества палиндромных подпоследовательностей. 2⃣Введите двумерный массив dp, где dp[i][j] представляет количество палиндромных подпоследовательностей в подстроке от i до j. 3⃣Итерируйте по длине подстрок от 1 до длины строки и обновляйте значения в dp на основе состояния предыдущих подстрок. 😎 Решение:
class Solution {
public:
int countPalindromicSubsequences(string s) {
const int MOD = 1000000007;
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) {
dp[i][i] = 1;
}
for (int length = 2; length <= n; ++length) {
for (int i = 0; i <= n - length; ++i) {
int j = i + length - 1;
if (s[i] == s[j]) {
int l = i + 1, r = j - 1;
while (l <= r && s[l] != s[i]) l++;
while (l <= r && s[r] != s[j]) r--;
if (l > r) {
dp[i][j] = dp[i + 1][j - 1] * 2 + 2;
} else if (l == r) {
dp[i][j] = dp[i + 1][j - 1] * 2 + 1;
} else {
dp[i][j] = dp[i + 1][j - 1] * 2 - dp[l + 1][r - 1];
}
} else {
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
}
dp[i][j] = (dp[i][j] + MOD) % MOD;
}
}
return dp[0][n - 1];
}
};