اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
C/C++ | LeetCode
رفتن به کانال در Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+zYofcX2VLTM3MGMy Вопросы собесов t.me/+BTbqlW1VbIFmYmVi Вакансии t.me/+za2mJYs4riAzMzFi
نمایش بیشتر3 259
مشترکین
+424 ساعت
-17 روز
-430 روز
آرشیو پست ها
3 259
Задача: 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 259
Задача: 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 259
Задача: №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 259
Задача: 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 259
Задача: 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 259
Задача: 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 259
Задача: №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 259
Задача: 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 259
Задача: 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 259
Задача: 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 259
Задача: 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 259
Задача: 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 259
Задача: 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 259
Задача: 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 259
Задача: 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];
}
};3 259
Задача: 528. Random Pick with Weight
Сложность: medium
Вам дан массив положительных целых чисел w, где w[i] описывает вес индекса i.
Вам нужно реализовать функцию pickIndex(), которая случайным образом выбирает индекс в диапазоне [0, w.length - 1] (включительно) и возвращает его. Вероятность выбора индекса i равна w[i] / sum(w).
Например, если w = [1, 3], вероятность выбора индекса 0 составляет 1 / (1 + 3) = 0.25 (т.е. 25%), а вероятность выбора индекса 1 составляет 3 / (1 + 3) = 0.75 (т.е. 75%).
Пример:
Input ["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"] [[[1,3]],[],[],[],[],[]] Output [null,1,1,1,1,0] Explanation Solution solution = new Solution([1, 3]); solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4. solution.pickIndex(); // return 1 solution.pickIndex(); // return 1 solution.pickIndex(); // return 1 solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4. Since this is a randomization problem, multiple answers are allowed. All of the following outputs can be considered correct: [null,1,1,1,1,0] [null,1,1,1,1,1] [null,1,1,1,0,0] [null,1,1,1,0,1] [null,1,0,1,0,0] ...... and so on.👨💻 Алгоритм: 1⃣ Инициализация и предобработка весов: В конструкторе создайте массив накопительных сумм prefixSums, где каждая позиция будет содержать сумму всех предыдущих весов до текущего индекса включительно. Также в конструкторе сохраните общую сумму весов totalSum. 2⃣ Генерация случайного числа и выбор индекса: В функции pickIndex() сгенерируйте случайное число в диапазоне от 0 до общей суммы весов totalSum. Используйте линейный поиск, чтобы найти первый индекс в prefixSums, который больше или равен сгенерированному числу. 3⃣ Возврат результата: Верните найденный индекс. 😎 Решение:
class Solution {
private:
vector<int> prefixSums;
int totalSum;
public:
Solution(vector<int>& w) {
int prefixSum = 0;
for (int weight : w) {
prefixSum += weight;
prefixSums.push_back(prefixSum);
}
totalSum = prefixSum;
}
int pickIndex() {
double target = totalSum * ((double) rand() / RAND_MAX);
for (int i = 0; i < prefixSums.size(); ++i) {
if (target < prefixSums[i]) {
return i;
}
}
return prefixSums.size() - 1;
}
};3 259
Задача: 39. Combination Sum
Сложность: medium
Дан массив уникальных чисел candidates и целевое число target. Нужно вернуть все уникальные комбинации чисел из candidates, сумма которых равна target. Одно и то же число можно использовать неограниченное количество раз.
Пример:
Input: candidates = [2,3,5], target = 8 Output: [[2,2,2,2],[2,3,3],[3,5]]👨💻 Алгоритм: 1⃣Используем рекурсивный бэктрекинг: если остаток суммы remain == 0 — комбинация найдена, добавляем в результат. 2⃣Если remain < 0 — выходим из текущей ветки (комбинация невалидна). 3⃣Для каждой позиции i от start до конца candidates, пробуем включить элемент в комбинацию, вызываем рекурсию с уменьшенным remain, и откатываемся (pop_back) после вызова. 😎 Решение:
class Solution {
public:
void backtrack(int remain, vector<int>& comb, int start,
const vector<int>& candidates,
vector<vector<int>>& results) {
if (remain == 0) {
results.push_back(comb);
return;
} else if (remain < 0) {
return;
}
for (int i = start; i < candidates.size(); ++i) {
comb.push_back(candidates[i]);
backtrack(remain - candidates[i], comb, i, candidates, results);
comb.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> results;
vector<int> comb;
backtrack(target, comb, 0, candidates, results);
return results;
}
};3 259
Задача: 710. Random Pick with Blacklist
Сложность: hard
Вам дано целое число n и массив уникальных целых чисел blacklist. Разработайте алгоритм выбора случайного целого числа из диапазона [0, n - 1], не входящего в черный список. Любое целое число, находящееся в указанном диапазоне и не входящее в черный список, должно с равной вероятностью быть возвращено. Оптимизируйте алгоритм так, чтобы он минимизировал количество обращений к встроенной функции random вашего языка. Реализуйте класс Solution: Solution(int n, int[] blacklist) Инициализирует объект целым числом n и целым числом из черного списка blacklist. int pick() Возвращает случайное целое число в диапазоне [0, n - 1] и не входящее в черный список.
Пример:
Input ["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"] [[7, [2, 3, 5]], [], [], [], [], [], [], []] Output [null, 0, 4, 1, 6, 1, 0, 4]👨💻 Алгоритм: 1⃣Создайте маппинг для чисел, входящих в черный список, чтобы сопоставить их с числами из диапазона [n - len(blacklist), n - 1], которые не входят в черный список. 2⃣Создайте массив для хранения возможных чисел для выбора, исключая числа из черного списка. 3⃣При каждом вызове функции pick() используйте встроенную функцию random для выбора случайного индекса из массива возможных чисел и возвращайте соответствующее значение. 😎 Решение:
class Solution {
public:
Solution(int n, std::vector<int>& blacklist) {
bound = n - blacklist.size();
std::unordered_set<int> blackset(blacklist.begin(), blacklist.end());
int whitelist = bound;
for (int b : blacklist) {
if (b < bound) {
while (blackset.count(whitelist)) {
whitelist++;
}
map[b] = whitelist;
whitelist++;
}
}
}
int pick() {
int r = rand() % bound;
return map.count(r) ? map[r] : r;
}
private:
std::unordered_map<int, int> map;
int bound;
};3 259
Задача: 680. Valid Palindrome II
Сложность: easy
Дана строка s, вернуть true, если s может быть палиндромом после удаления не более одного символа из нее.
Пример:
Input: s = "aba"
Output: trueclass Solution {
bool checkPalindrome(const string& s, int i, int j) {
while (i < j) {
if (s[i] != s[j]) {
return false;
}
i++;
j--;
}
return true;
}
public:
bool validPalindrome(string s) {
int i = 0;
int j = s.size() - 1;
while (i < j) {
if (s[i] != s[j]) {
return checkPalindrome(s, i, j - 1) || checkPalindrome(s, i + 1, j);
}
i++;
j--;
}
return true;
}
};3 259
Задача: №28. Find the Index of the First Occurrence in a String
Сложность: easy
Учитывая две строки needle и haystack, верните индекс первого вхождения needle в haystack, либо -1, если needle не является частью haystack.
Пример:
Input: haystack = "sadbutsad", needle = "sad" Output: 0
class Solution {
public:
int strStr(string haystack, string needle) {
if(haystack.size() < needle.size()) return -1;
if(haystack.size() == needle.size()) {
if(haystack == needle) return 0;
else return -1;
}
for(int i = 0; i <= haystack.size() - needle.size(); i++) {
string s = haystack.substr(i, needle.size());
if(s == needle) {
return i;
}
}
return -1;
}
};