Endi mavjud! Telegram Tadqiqoti 2025 — yilning asosiy insaytlari 
C/C++ | LeetCode
Kanalga Telegram’da o‘tish
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+zYofcX2VLTM3MGMy Вопросы собесов t.me/+BTbqlW1VbIFmYmVi Вакансии t.me/+za2mJYs4riAzMzFi
Ko'proq ko'rsatish3 251
Obunachilar
-324 soatlar
-107 kunlar
-1530 kunlar
Postlar arxiv
3 249
Задача: №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 249
Задача: 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 249
Задача: 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 249
Задача: 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 249
Задача: 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 249
Задача: 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 249
Задача: 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 249
Задача: 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 249
Задача: 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 249
Задача: 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 249
Задача: 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 249
Задача: 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 249
Задача: 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 249
Задача: №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 249
Задача: 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 249
Задача: 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 249
Задача: 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 249
Задача: 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 249
Задача: 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 249
Задача: 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;
}