C/C++ | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @easyoffer_adv
نمایش بیشتر
شبکه:3 237
مشترکین
+124 ساعت
+77 روز
-430 روز
آرشیو پست ها
3 237
Задача: 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 237
Задача: 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 237
Задача: 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 237
Задача: 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 237
Задача: 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 237
Задача: 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 237
Задача: 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 237
Задача: 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 237
Задача: 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 237
Задача: 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 237
Задача: №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;
}
};3 237
Задача: 779. K-th Symbol in Grammar
Сложность: medium
Мы строим таблицу из n строк (индексация начинается с 1). Начинаем с написания 0 в первой строке. Теперь в каждой следующей строке мы смотрим на предыдущую строку и заменяем каждое появление 0 на 01, и каждое появление 1 на 10.
Например, для n = 3, первая строка будет 0, вторая строка будет 01, и третья строка будет 0110.
Даны два целых числа n и k, вернуть k-й (индексация начинается с 1) символ в n-й строке таблицы из n строк.
Пример:
Input: n = 1, k = 1 Output: 0 Explanation: row 1: 0👨💻 Алгоритм: 1⃣Создайте метод depthFirstSearch, который принимает n количество строк в текущем дереве, k позицию целевого узла в последней строке и rootVal значение корня текущего дерева в качестве параметров. Если n равно 1, то в нашем дереве будет единственный узел, и этот узел является целевым узлом. Поэтому возвращаем его значение rootVal. 2⃣Найдите количество узлов в последней строке текущего дерева, totalNodes, которое равно 2^(n-1). Если текущий целевой узел k находится в левой половине последней строки текущего поддерева (то есть k <= totalNodes / 2), переходим в левое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 0, иначе следующее значение узла будет 1. Возвращаем вызов depthFirstSearch(n - 1, k, nextRootVal). 3⃣В противном случае, если текущий целевой узел k находится в правой половине последней строки текущего поддерева (то есть k > totalNodes / 2), переходим в правое поддерево. Если значение текущего узла rootVal равно 0, то значение следующего узла будет 1, иначе следующее значение узла будет 0. Кроме того, позиция целевого узла изменится на (k - (totalNodes / 2)). Возвращаем вызов depthFirstSearch(n - 1, newPosition, nextRootVal). 😎 Решение:
class Solution {
public:
int depthFirstSearch(int n, int k, int rootVal) {
if (n == 1) return rootVal;
int totalNodes = 1 << (n - 1);
if (k > totalNodes / 2) {
int nextRootVal = rootVal == 0 ? 1 : 0;
return depthFirstSearch(n - 1, k - totalNodes / 2, nextRootVal);
} else {
int nextRootVal = rootVal == 0 ? 0 : 1;
return depthFirstSearch(n - 1, k, nextRootVal);
}
}
int kthGrammar(int n, int k) {
return depthFirstSearch(n, k, 0);
}
};3 237
Задача: 171. Excel Sheet Column Number
Сложность: easy
Дана строка columnTitle, представляющая название столбца в Excel (например, "A", "AB", "ZY"). Нужно вернуть соответствующий номер столбца.
Пример:
Input: "A" → Output: 1👨💻 Алгоритм: 1⃣Представим строку как число в 26-ричной системе счисления, где A = 1, B = 2, ..., Z = 26. 2⃣Проходим по строке слева направо, на каждом шаге умножая результат на 26 и прибавляя значение текущего символа (s[i] - 'A' + 1). 3⃣Таким образом, "AB" = 1×26 + 2 = 28. 😎 Решение:
class Solution {
public:
int titleToNumber(string s) {
int result = 0;
for (char c : s) {
result = result * 26 + (c - 'A' + 1);
}
return result;
}
};3 237
Задача: 906. Super Palindromes
Сложность: hard
Если задан целочисленный массив nums, переместите все четные числа в начало массива, а затем все нечетные. Верните любой массив, удовлетворяющий этому условию.
Пример:
Input: left = "4", right = "1000" Output: 4👨💻 Алгоритм: 1⃣Найти все палиндромы до корня из right. 2⃣Проверить, являются ли квадраты этих палиндромов палиндромами и лежат ли в диапазоне [left, right]. 3⃣Подсчитать количество таких суперпалиндромов. 😎 Решение:
class Solution {
public:
bool isPalindrome(long long x) {
string s = to_string(x);
return s == string(s.rbegin(), s.rend());
}
int superpalindromesInRange(string left, string right) {
long long leftNum = stoll(left);
long long rightNum = stoll(right);
int count = 0;
for (int i = 1; i < 100000; i++) {
string s = to_string(i);
long long palin1 = stoll(s + string(s.rbegin(), s.rend()));
long long palin2 = stoll(s + string(s.rbegin() + 1, s.rend()));
if (palin1 * palin1 > rightNum) {
break;
}
if (palin1 * palin1 >= leftNum && isPalindrome(palin1 * palin1)) {
count++;
}
if (palin2 * palin2 >= leftNum && palin2 * palin2 <= rightNum && isPalindrome(palin2 * palin2)) {
count++;
}
}
return count;
}
};3 237
Задача: 771. Jewels and Stones
Сложность: medium
Вам даны строки jewels, представляющие типы камней, которые являются драгоценностями, и stones, представляющие камни, которые у вас есть. Каждый символ в stones является типом камня, который у вас есть. Вы хотите узнать, сколько из камней, которые у вас есть, также являются драгоценностями.
Буквы чувствительны к регистру, поэтому "a" считается другим типом камня, чем "A".
Пример:
Input: jewels = "aA", stones = "aAAbbbb"
Output: 3class Solution {
public:
int numJewelsInStones(string J, string S) {
int ans = 0;
for (char s : S)
for (char j : J)
if (j == s) {
ans++;
break;
}
return ans;
}
};3 237
Задача: 685. Redundant Connection II
Сложность: hard
В этой задаче корневое дерево — это направленный граф, в котором существует ровно один узел (корень), для которого все остальные узлы являются потомками этого узла, плюс каждый узел имеет ровно одного родителя, за исключением корневого узла, у которого нет родителей.
Данный ввод представляет собой направленный граф, который изначально был корневым деревом с n узлами (со значениями от 1 до n), и к которому добавлено одно дополнительное направленное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее.
Результирующий граф представлен в виде двумерного массива ребер. Каждый элемент массива edges — это пара [ui, vi], представляющая направленное ребро, соединяющее узлы ui и vi, где ui является родителем ребенка vi.
Верните ребро, которое можно удалить, чтобы результирующий граф стал корневым деревом с n узлами. Если существует несколько ответов, верните ответ, который встречается последним в данном двумерном массиве.
Пример:
Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]class Solution {
public:
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
int N = edges.size();
unordered_map<int, int> parent;
vector<vector<int>> candidates;
for (auto& edge : edges) {
if (parent.count(edge[1])) {
candidates.push_back({parent[edge[1]], edge[1]});
candidates.push_back(edge);
} else {
parent[edge[1]] = edge[0];
}
}
int root = orbit(1, parent).node;
if (candidates.empty()) {
auto cycle = orbit(root, parent).seen;
vector<int> ans = {0, 0};
for (auto& edge : edges) {
if (cycle.count(edge[0]) && cycle.count(edge[1])) {
ans = edge;
}
}
return ans;
}
unordered_map<int, vector<int>> children;
for (auto& p : parent) {
children[p.second].push_back(p.first);
}
vector<bool> seen(N + 1, false);
seen[0] = true;
stack<int> stk;
stk.push(root);
while (!stk.empty()) {
int node = stk.top();
stk.pop();
if (!seen[node]) {
seen[node] = true;
for (int c : children[node]) {
stk.push(c);
}
}
}
for (bool b : seen) {
if (!b) {
return candidates[0];
}
}
return candidates[1];
}
private:
struct OrbitResult {
int node;
unordered_set<int> seen;
OrbitResult(int n, unordered_set<int> s) : node(n), seen(s) {}
};
OrbitResult orbit(int node, unordered_map<int, int>& parent) {
unordered_set<int> seen;
while (parent.count(node) && !seen.count(node)) {
seen.insert(node);
node = parent[node];
}
return OrbitResult(node, seen);
}
};3 237
Задача: 717. 1-bit and 2-bit Characters
Сложность: easy
У нас есть два специальных символа: первый символ может быть представлен одним битом 0. Второй символ может быть представлен двумя битами (10 или 11). Если задан двоичный массив bits, который заканчивается 0, верните true, если последний символ должен быть однобитным.
Пример:
Input: bits = [1,0,0] Output: true👨💻 Алгоритм: 1⃣Инициализируйте индекс для итерации по массиву. 2⃣Пройдите по массиву, увеличивая индекс на 1, если текущий бит равен 0, и на 2, если текущий бит равен 1. 3⃣Проверьте, достиг ли индекс последнего элемента массива, и верните результат. 😎 Решение:
bool isOneBitCharacter(vector<int>& bits) {
int i = 0;
while (i < bits.size() - 1) {
i += bits[i] + 1;
}
return i == bits.size() - 1;
}3 237
Задача: 731. My Calendar II
Сложность: medium
Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к тройному бронированию. Тройное бронирование происходит, когда три события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Реализация класса MyCalendarTwo: MyCalendarTwo() Инициализирует объект календаря. boolean book(int start, int end) Возвращает true, если событие может быть успешно добавлено в календарь, не вызывая тройного бронирования. В противном случае возвращается false и событие не добавляется в календарь.
Пример:
Input ["MyCalendarTwo", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]] Output [null, true, true, true, false, true, true]👨💻 Алгоритм: 1⃣Создайте два списка: один для отслеживания всех событий, второй для отслеживания пересечений. подпоследовательностей. 2⃣При добавлении нового события сначала проверьте, не пересекается ли оно с любыми существующими пересечениями. 3⃣Если пересечение не обнаружено, добавьте новое событие и обновите список пересечений при необходимости. 😎 Решение:
class MyCalendarTwo {
public:
MyCalendarTwo() {}
bool book(int start, int end) {
for (const auto& overlap : overlaps) {
if (start < overlap[1] && end > overlap[0]) {
return false;
}
}
for (const auto& event : events) {
if (start < event[1] && end > event[0]) {
overlaps.push_back({max(start, event[0]), min(end, event[1])});
}
}
events.push_back({start, end});
return true;
}
private:
vector<pair<int, int>> events;
vector<pair<int, int>> overlaps;
};3 237
Задача: 340. Longest Substring with At Most K Distinct Characters
Сложность: medium
Дана строка s и целое число k. Верните длину самой длинной подстроки s, которая содержит не более k различных символов.
Пример:
Input: n = 27 Output: true Explanation: 27 = 3^3👨💻 Алгоритм: 1⃣Инициализация Используйте два указателя (left и right) для отслеживания текущего окна в строке. Создайте словарь для отслеживания количества каждого символа в текущем окне. Инициализируйте переменные для хранения максимальной длины подстроки (max_length). 2⃣Раздвижение окна Перемещайте правый указатель (right) по строке и обновляйте словарь. Если количество различных символов в словаре превышает k, перемещайте левый указатель (left) вправо, уменьшая счетчик символов, пока количество различных символов снова не станет меньше или равно k. 3⃣Обновление максимальной длины На каждом шаге проверяйте и обновляйте максимальную длину подстроки, если текущее окно содержит не более k различных символов. В конце верните максимальную длину подстроки. 😎 Решение:
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
int left = 0, right = 0;
unordered_map<char, int> charCount;
int maxLength = 0;
while (right < s.length()) {
charCount[s[right]]++;
while (charCount.size() > k) {
charCount[s[left]]--;
if (charCount[s[left]] == 0) {
charCount.erase(s[left]);
}
left++;
}
maxLength = max(maxLength, right - left + 1);
right++;
}
return maxLength;
}
};3 237
Задача: 1208. Get Equal Substrings Within Budget
Сложность: medium
Вам даны две строки s и t одинаковой длины и целое число maxCost.
Вы хотите преобразовать s в t. Изменение i-го символа строки s на i-й символ строки t стоит |s[i] - t[i]| (т.е. абсолютная разница между значениями ASCII символов).
Верните максимальную длину подстроки s, которую можно изменить, чтобы она соответствовала соответствующей подстроке t с затратами, не превышающими maxCost. Если нет подстроки из s, которую можно изменить на соответствующую подстроку из t, верните 0.
Пример:
Input: s = "abcd", t = "bcdf", maxCost = 3 Output: 3 Explanation: "abc" of s can change to "bcd". That costs 3, so the maximum length is 3.👨💻 Алгоритм: 1⃣Инициализация переменных: maxLen для хранения максимальной длины подстроки с затратами, не превышающими maxCost. start для хранения начального индекса текущей подстроки. currCost для хранения текущих затрат на преобразование подстроки s в t. 2⃣Итерация по индексам от 0 до N-1: Добавить текущие затраты на преобразование символа s[i] в t[i] к currCost. Удалять элементы с левого конца, уменьшая затраты до тех пор, пока currCost не станет меньше или равным maxCost. Обновить maxLen длиной текущей подстроки. 3⃣Возврат maxLen как результата. 😎 Решение:
class Solution {
public:
int equalSubstring(string s, string t, int maxCost) {
int N = s.length();
int maxLen = 0;
int start = 0;
int currCost = 0;
for (int i = 0; i < N; i++) {
currCost += abs(s[i] - t[i]);
while (currCost > maxCost) {
currCost -= abs(s[start] - t[start]);
start++;
}
maxLen = max(maxLen, i - start + 1);
}
return maxLen;
}
};