اکنون در دسترس! پژوهش تلگرام ۲۰۲۵ — مهمترین بینشهای سال 
C/C++ | LeetCode
رفتن به کانال در Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+zYofcX2VLTM3MGMy Вопросы собесов t.me/+BTbqlW1VbIFmYmVi Вакансии t.me/+za2mJYs4riAzMzFi
نمایش بیشتر3 260
مشترکین
اطلاعاتی وجود ندارد24 ساعت
-27 روز
-230 روز
آرشیو پست ها
3 258
Задача: 433. Minimum Genetic Mutation
Сложность: medium
Пример:
Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"] Output: 1Алгоритм: 1⃣Инициализируем очередь и множество seen. Помещаем в них startGene. Начинаем BFS по возможным мутациям. 2⃣Для каждой строки из очереди проверяем, достигли ли endGene. Если нет, генерируем все возможные односимвольные мутации и добавляем допустимые в очередь. 3⃣Если очередь опустела, а endGene не найден — возвращаем -1. 😎 Решение:
class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
queue<string> queue;
unordered_set<string> seen;
queue.push(start);
seen.insert(start);
int steps = 0;
while (!queue.empty()) {
int nodesInQueue = queue.size();
for (int j = 0; j < nodesInQueue; j++) {
string node = queue.front();
queue.pop();
if (node == end) {
return steps;
}
for (char c: "ACGT") {
for (int i = 0; i < node.size(); i++) {
string neighbor = node;
neighbor[i] = c;
if (!seen.count(neighbor) && find(bank.begin(), bank.end(), neighbor) != bank.end()) {
queue.push(neighbor);
seen.insert(neighbor);
}
}
}
}
steps++;
}
return -1;
}
};3 258
Задача: 1345. Jump Game IV
Сложность: hard
Дан массив целых чисел arr, изначально вы находитесь на первом индексе массива.
За один шаг вы можете прыгнуть с индекса i на индекс:
- i + 1, где: i + 1 < arr.length.
- i - 1, где: i - 1 >= 0.
- j, где: arr[i] == arr[j] и i != j.
Вернуть минимальное количество шагов, чтобы достичь последнего индекса массива.
Обратите внимание, что нельзя прыгать за пределы массива в любой момент времени.
Пример:
Input: arr = [100,-23,-23,404,100,23,23,23,3,404] Output: 3 Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.👨💻 Алгоритм: 1⃣Построить граф, где ключи - значения из массива, а значения - списки индексов этих значений. Начать с первого индекса, добавив его в очередь текущего слоя и инициализировать набор посещенных индексов. 2⃣Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя. 3⃣Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь. 😎 Решение:
class Solution {
public:
int minJumps(vector<int>& arr) {
int n = arr.size();
if (n <= 1) return 0;
unordered_map<int, vector<int>> graph;
for (int i = 0; i < n; i++) {
graph[arr[i]].push_back(i);
}
vector<int> curs = {0};
unordered_set<int> visited = {0};
int step = 0;
while (!curs.empty()) {
vector<int> nex;
for (int node : curs) {
if (node == n - 1) return step;
for (int child : graph[arr[node]]) {
if (visited.find(child) == visited.end()) {
visited.insert(child);
nex.push_back(child);
}
}
graph[arr[node]].clear();
if (node + 1 < n && visited.find(node + 1) == visited.end()) {
visited.insert(node + 1);
nex.push_back(node + 1);
}
if (node - 1 >= 0 && visited.find(node - 1) == visited.end()) {
visited.insert(node - 1);
nex.push_back(node - 1);
}
}
curs = nex;
step++;
}
return -1;
}
};3 258
Задача: 126. Word Ladder II
Сложность: hard
Найдите все кратчайшие пути преобразования от beginWord до endWord, изменяя по одной букве за раз, так чтобы каждое промежуточное слово было из wordList.
Пример:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: [["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]👨💻 Алгоритм: 1⃣Используем BFS, чтобы построить граф уровней (adjList) от beginWord до всех достижимых слов. Каждое слово связано с соседними словами, отличающимися на одну букву. 2⃣Удаляем слова из wordList после каждого уровня, чтобы избежать повторных посещений и гарантировать, что пути будут минимальной длины. 3⃣После BFS используем обратный backtracking от endWord к beginWord, используя построенный adjList, чтобы восстановить все возможные кратчайшие пути. 😎 Решение:
class Solution {
public:
unordered_map<string, vector<string>> adjList;
vector<string> currPath;
vector<vector<string>> shortestPaths;
vector<string> findNeighbors(string &word, unordered_set<string> &wordList) {
vector<string> neighbors;
for (int i = 0; i < word.size(); i++) {
char oldChar = word[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c != oldChar) {
word[i] = c;
if (wordList.count(word)) neighbors.push_back(word);
}
}
word[i] = oldChar;
}
return neighbors;
}
void backtrack(string &source, string &destination) {
if (source == destination) {
shortestPaths.push_back(vector<string>(currPath.rbegin(), currPath.rend()));
return;
}
for (string& neighbor : adjList[source]) {
currPath.push_back(neighbor);
backtrack(neighbor, destination);
currPath.pop_back();
}
}
void bfs(string &beginWord, unordered_set<string> &wordList) {
queue<string> q;
q.push(beginWord);
unordered_set<string> visited;
visited.insert(beginWord);
while (!q.empty()) {
int size = q.size();
unordered_set<string> thisLevelVisited;
for (int i = 0; i < size; i++) {
string currWord = q.front();
q.pop();
vector<string> neighbors = findNeighbors(currWord, wordList);
for (string& neighbor : neighbors) {
if (!visited.count(neighbor)) {
if (!thisLevelVisited.count(neighbor)) {
q.push(neighbor);
thisLevelVisited.insert(neighbor);
}
adjList[neighbor].push_back(currWord);
}
}
}
for (const string& word : thisLevelVisited) {
wordList.erase(word);
visited.insert(word);
}
}
}
vector<vector<string>> findLadders(string beginWord, string endWord, vector<string> &wordList) {
unordered_set<string> wordSet(wordList.begin(), wordList.end());
if (!wordSet.count(endWord)) return {};
bfs(beginWord, wordSet);
currPath = {endWord};
backtrack(endWord, beginWord);
return shortestPaths;
}
};3 258
Задача: 997. Find the Town Judge
Сложность: easy
В городе есть n человек, помеченных от 1 до n. Ходят слухи, что один из этих людей тайно является городским судьей. Если городской судья существует, то: городской судья никому не доверяет. Все (кроме городского судьи) доверяют городскому судье. Существует ровно один человек, удовлетворяющий свойствам 1 и 2. Вам дан массив trust, где trust[i] = [ai, bi], представляющий, что человек, помеченный ai, доверяет человеку, помеченному bi. Если в массиве trust не существует доверительных отношений, то таких отношений не существует. Верните метку городского судьи, если городской судья существует и может быть идентифицирован, или верните -1 в противном случае.
Пример:
Input: n = 2, trust = [[1,2]] Output: 2👨💻 Алгоритм: 1⃣Создание счетчиков доверия: Инициализируйте массив для подсчета количества людей, которым доверяет каждый человек, и массив для подсчета количества людей, которые доверяют каждому человеку. 2⃣Подсчет доверия: Пройдитесь по каждому элементу в массиве trust и обновите счетчики: увеличьте количество доверий для того, кто доверяет, и увеличьте количество доверенных людей для того, кому доверяют. 3⃣Проверка условий судьи: Пройдитесь по массиву людей и найдите того, кто никому не доверяет (количество доверий равно 0) и кому доверяют все остальные (количество доверенных людей равно n-1). Верните метку этого человека. Если такого человека нет, верните -1. 😎 Решение:
class Solution {
public:
int findJudge(int n, vector<vector<int>>& trust) {
if (trust.empty() && n == 1) return 1;
vector<int> trust_count(n + 1, 0);
vector<int> trusted_by(n + 1, 0);
for (const auto& t : trust) {
trust_count[t[0]]++;
trusted_by[t[1]]++;
}
for (int i = 1; i <= n; ++i) {
if (trust_count[i] == 0 && trusted_by[i] == n - 1) {
return i;
}
}
return -1;
}
};3 258
Задача: 1043. Partition Array for Maximum Sum
Сложность: medium
Если задан целочисленный массив arr, разбейте его на (смежные) подмассивы длины не более k. После разбиения значения каждого подмассива меняются так, чтобы стать максимальным значением этого подмассива. Верните наибольшую сумму заданного массива после разбиения. Тестовые примеры генерируются таким образом, чтобы ответ умещался в 32-битное целое число.
Пример:
Input: arr = [1,15,7,9,2,5,10], k = 3 Output: 84👨💻 Алгоритм: 1⃣Инициализация: Создаем массив dp, где dp[i] будет хранить наибольшую сумму подмассива, заканчивающегося в позиции i. 2⃣Заполнение массива dp: Проходим по массиву arr и для каждой позиции i пытаемся разбить подмассив длины до k и обновить dp[i] с максимальной возможной суммой. 3⃣Поддержание максимального значения в подмассиве: Для каждого подмассива длины 1 до k, вычисляем максимальное значение в этом подмассиве и обновляем dp[i]. 😎 Решение:
class Solution {
public:
int maxSumAfterPartitioning(vector<int>& arr, int k) {
int n = arr.size();
vector<int> dp(n, 0);
for (int i = 0; i < n; ++i) {
int max_val = 0;
for (int j = 1; j <= k; ++j) {
if (i - j + 1 >= 0) {
max_val = max(max_val, arr[i - j + 1]);
if (i - j >= 0) {
dp[i] = max(dp[i], dp[i - j] + max_val * j);
} else {
dp[i] = max(dp[i], max_val * j);
}
}
}
}
return dp[n - 1];
}
};3 258
Задача: 863. All Nodes Distance K in Binary Tree
Сложность: medium
Дан корень бинарного дерева, значение целевого узла target и целое число k. Верните массив значений всех узлов, которые находятся на расстоянии k от целевого узла.
Ответ можно вернуть в любом порядке.
Пример:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.class Solution {
public:
vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
addParent(root, nullptr);
vector<int> answer;
unordered_set<TreeNode*> visited;
dfs(target, k, visited, answer);
return answer;
}
private:
void addParent(TreeNode* cur, TreeNode* parent) {
if (cur) {
cur->parent = parent;
addParent(cur->left, cur);
addParent(cur->right, cur);
}
}
void dfs(TreeNode* cur, int distance, unordered_set<TreeNode*>& visited, vector<int>& answer) {
if (!cur || visited.count(cur)) return;
visited.insert(cur);
if (distance == 0) {
answer.push_back(cur->val);
return;
}
dfs(cur->parent, distance - 1, visited, answer);
dfs(cur->left, distance - 1, visited, answer);
dfs(cur->right, distance - 1, visited, answer);
}
};
struct TreeNode {
int val;
TreeNode *left, *right, *parent;
TreeNode(int x) : val(x), left(nullptr), right(nullptr), parent(nullptr) {}
};3 258
Задача: 503. Next Greater Element II
Сложность: medium
Дан циклический массив целых чисел nums (т.е. следующий элемент после nums[nums.length - 1] это nums[0]), верните следующее большее число для каждого элемента в nums.
Следующее большее число для числа x — это первое большее число, следующее за ним в порядке обхода массива, что означает, что вы можете искать циклически, чтобы найти следующее большее число. Если оно не существует, верните -1 для этого числа.
Пример:
Input: nums = [1,2,1] Output: [2,-1,2] Explanation: The first 1's next greater number is 2; The number 2 can't find next greater number. The second 1's next greater number needs to search circularly, which is also 2.👨💻 Алгоритм: 1⃣Инициализация Создайте массив res той же длины, что и nums, и заполните его значениями -1. 2⃣Поиск следующего большего элемента Для каждого элемента nums[i], используя индекс j, ищите следующий больший элемент среди следующих (циклически) n-1 элементов. Если найден больший элемент, обновите res[i] и прервите внутренний цикл. 3⃣Возврат результата Верните массив res. 😎 Решение:
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, -1);
for (int i = 0; i < n; i++) {
for (int j = 1; j < n; j++) {
if (nums[(i + j) % n] > nums[i]) {
res[i] = nums[(i + j) % n];
break;
}
}
}
return res;
}
};3 258
Задача: 487. Max Consecutive Ones II
Сложность: medium
Дан бинарный массив nums, верните максимальное количество последовательных единиц в массиве, если можно перевернуть не более одного нуля.
Пример:
Input: nums = [1,0,1,1,0] Output: 4 Explanation: - If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones. - If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones. The max number of consecutive ones is 4.👨💻 Алгоритм: 1⃣Для каждого возможного начала последовательности в массиве nums начните считать количество нулей. 2⃣Для каждой последовательности проверяйте, сколько нулей содержится в ней. Если количество нулей не превышает одного, обновите максимальную длину последовательности единиц. 3⃣Продолжайте проверять все возможные последовательности в массиве, и верните максимальную длину последовательности единиц, удовлетворяющую условию. 😎 Решение:
class Solution {
public:
int findMaxConsecutiveOnes(vector<int>& nums) {
int longestSequence = 0;
for (int left = 0; left < nums.size(); ++left) {
int numZeroes = 0;
for (int right = left; right < nums.size(); ++right) {
if (nums[right] == 0) {
numZeroes++;
}
if (numZeroes <= 1) {
longestSequence = max(longestSequence, right - left + 1);
}
}
}
return longestSequence;
}
};3 258
Задача: 474. Ones and Zeroes
Сложность: medium
Дан массив двоичных строк strs и два целых числа m и n.
Верните размер наибольшего подмножества strs, такого что в подмножестве содержится не более m нулей и n единиц.
Множество x является подмножеством множества y, если все элементы множества x также являются элементами множества y.
Пример:
Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3
Output: 4
Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4.
Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}.
{"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3.
👨💻 Алгоритм:
1⃣Рассматриваем все возможные подмножества, прерывая цикл, если количество нулей превышает m или количество единиц превышает n.
2⃣Считаем количество нулей и единиц в каждом подмножестве.
3⃣Выбираем наибольшее подмножество, соответствующее условиям, и возвращаем его размер.
😎 Решение:
#include <vector>
#include <string>
#include <algorithm>
class Solution {
public:
int findMaxForm(std::vector<std::string>& strs, int m, int n) {
int maxlen = 0;
for (int i = 0; i < (1 << strs.size()); ++i) {
int zeroes = 0, ones = 0, len = 0;
for (int j = 0; j < 32; ++j) {
if ((i & (1 << j)) != 0) {
auto count = countZeroesOnes(strs[j]);
zeroes += count[0];
ones += count[1];
if (zeroes > m || ones > n)
break;
++len;
}
}
if (zeroes <= m && ones <= n)
maxlen = std::max(maxlen, len);
}
return maxlen;
}
std::vector<int> countZeroesOnes(const std::string& s) {
std::vector<int> c(2, 0);
for (char ch : s) {
++c[ch - '0'];
}
return c;
}
};3 258
Задача: 1230. Toss Strange Coins
Сложность: medium
У вас есть несколько монет. Вероятность выпадения орла для i-й монеты равна prob[i].
Верните вероятность того, что количество монет, на которых выпал орел, равно target, если вы подбросите каждую монету ровно один раз.
Пример:
Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0 Output: 0.03125👨💻 Алгоритм: 1⃣Инициализация: Создайте переменную n и инициализируйте её размером массива prob. Создайте 2D массив dp размером n + 1 строк и target + 1 столбцов, где dp[i][j] хранит вероятность получить j орлов, используя первые i монет. Установите базовый случай dp[0][0] = 1. 2⃣Итерация: Используйте два вложенных цикла для заполнения массива dp. Внешний цикл итерируется от i = 1 до n. Для каждого i установите dp[i][0], что обозначает вероятность получить 0 орлов при использовании i монет: dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1]). Внутренний цикл итерируется от j = 1 до target. Для каждого j вычислите dp[i][j] по формуле: dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1]). 3⃣Возврат результата: Верните значение dp[n][target], которое содержит искомую вероятность. 😎 Решение:
class Solution {
public:
double probabilityOfHeads(vector<double>& prob, int target) {
int n = prob.size();
vector<vector<double>> dp(n + 1, vector<double>(target + 1, 0.0));
dp[0][0] = 1.0;
for (int i = 1; i <= n; ++i) {
dp[i][0] = dp[i - 1][0] * (1 - prob[i - 1]);
for (int j = 1; j <= target; ++j) {
if (j <= i) {
dp[i][j] = dp[i - 1][j - 1] * prob[i - 1] + dp[i - 1][j] * (1 - prob[i - 1]);
}
}
}
return dp[n][target];
}
};3 258
Задача: 494. Target Sum
Сложность: medium
Вам дан массив целых чисел nums и целое число target.
Вы хотите создать выражение из nums, добавляя один из символов '+' или '-' перед каждым числом в nums, а затем объединяя все числа.
Например, если nums = [2, 1], вы можете добавить '+' перед 2 и '-' перед 1, а затем объединить их, чтобы получить выражение "+2-1".
Верните количество различных выражений, которые можно построить и которые оцениваются в target.
Пример:
Input: nums = [1,1,1,1,1], target = 3 Output: 5 Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3. -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3👨💻 Алгоритм: 1⃣Инициализация и вызов рекурсивной функции Создайте переменную для хранения количества решений (count). Вызовите рекурсивную функцию calculate с начальными параметрами (nums, начальный индекс 0, начальная сумма 0, и target). 2⃣Рекурсивная функция calculate Если текущий индекс равен длине массива, проверьте, равна ли текущая сумма значению target. Если да, увеличьте счетчик решений. В противном случае, вызовите функцию рекурсивно дважды: добавляя и вычитая текущее значение из суммы. 3⃣Возврат результата После завершения всех рекурсивных вызовов верните значение счетчика решений. 😎 Решение:
class Solution {
public:
int count = 0;
int findTargetSumWays(vector<int>& nums, int S) {
calculate(nums, 0, 0, S);
return count;
}
void calculate(vector<int>& nums, int i, int sum, int S) {
if (i == nums.size()) {
if (sum == S) {
count++;
}
} else {
calculate(nums, i + 1, sum + nums[i], S);
calculate(nums, i + 1, sum - nums[i], S);
}
}
};3 258
Задача: 326. Power of Three
Сложность: easy
Дано целое число n. Верните true, если оно является степенью тройки, иначе верните false.
Целое число n является степенью тройки, если существует целое число x такое, что n == 3^x.
Пример:
Input: n = 27 Output: true Explanation: 27 = 3^3👨💻 Алгоритм: 1⃣Проверка начального значения Если n меньше или равно нулю, вернуть false, так как степени тройки всегда положительны. 2⃣Цикл деления на 3 Пока n делится на 3 без остатка, делите n на 3. Повторяйте этот процесс до тех пор, пока n делится на 3. 3⃣Проверка конечного значения Если после всех делений значение n стало равно 1, значит исходное число является степенью тройки, вернуть true. В противном случае вернуть false. 😎 Решение:
class Solution {
public:
bool isPowerOfThree(int n) {
if (n <= 0) return false;
while (n % 3 == 0) {
n /= 3;
}
return n == 1;
}
};3 258
Задача: 949. Largest Time for Given Digits
Сложность: medium
Учитывая массив arr из 4 цифр, найдите самое позднее 24-часовое время, которое можно составить, используя каждую цифру ровно один раз. 24-часовое время имеет формат "ЧЧ:ММ", где ЧЧ - от 00 до 23, а ММ - от 00 до 59. Самое раннее 24-часовое время - 00:00, а самое позднее - 23:59. Верните самое позднее 24-часовое время в формате "HH:MM". Если не удается определить действительное время, возвращается пустая строка.
Пример:
Input: arr = [1,2,3,4] Output: "23:41"👨💻 Алгоритм: 1⃣Перебрать все возможные перестановки массива arr. 2⃣Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время. Найти самое позднее допустимое время среди всех перестановок. 3⃣Алгоритм Перебрать все возможные перестановки массива arr. Проверить каждую перестановку, можно ли из нее составить допустимое 24-часовое время. Найти самое позднее допустимое время среди всех перестановок. Вернуть найденное время в формате "HH ". Если допустимое время не найдено, вернуть пустую строку. 😎 Решение:
class Solution {
public:
string largestTimeFromDigits(vector<int>& arr) {
sort(arr.begin(), arr.end());
int maxTime = -1;
do {
int hours = arr[0] * 10 + arr[1];
int minutes = arr[2] * 10 + arr[3];
if (hours < 24 && minutes < 60) {
maxTime = max(maxTime, hours * 60 + minutes);
}
} while (next_permutation(arr.begin(), arr.end()));
if (maxTime == -1) {
return "";
}
char buffer[6];
sprintf(buffer, "%02d:%02d", maxTime / 60, maxTime % 60);
return string(buffer);
}
};3 258
Задача: 972. Equal Rational Numbers
Сложность: hard
Даны две строки s и t, каждая из которых представляет собой неотрицательное рациональное число. Вернуть true тогда и только тогда, когда они представляют одно и то же число. Строки могут использовать скобки для обозначения повторяющейся части рационального числа.
Рациональное число может быть представлено с использованием до трех частей: <ЦелаяЧасть>, <НеповторяющаясяЧасть> и <ПовторяющаясяЧасть>. Число будет представлено одним из следующих трех способов:
<ЦелаяЧасть>
Например, 12, 0 и 123.
<ЦелаяЧасть><.><НеповторяющаясяЧасть>
Например, 0.5, 1., 2.12 и 123.0001.
<ЦелаяЧасть><.><НеповторяющаясяЧасть><(><ПовторяющаясяЧасть><)>
Например, 0.1(6), 1.(9), 123.00(1212).
Повторяющаяся часть десятичного разложения обозначается в круглых скобках. Например:
1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66).
Пример:
Input: s = "0.(52)", t = "0.5(25)" Output: true Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.👨💻 Алгоритм: 1⃣Преобразование дроби. Определите и изолируйте повторяющуюся часть дроби. Преобразуйте строку, представляющую число, в выражение вида S=x/(10^k-1), где x — повторяющаяся часть, а k — её длина. 2⃣Вычисление геометрической суммы. Преобразуйте повторяющуюся часть в сумму вида S=x*(r/(1-r)), где r = 10^(-k). Найдите значение дроби для повторяющейся части, используя формулу геометрической прогрессии. 3⃣Обработка неповторяющейся части. Определите значение неповторяющейся части дроби как обычное число. Объедините результаты для повторяющейся и неповторяющейся частей для получения итогового значения. 😎 Решение:
class Fraction {
public:
long n, d;
Fraction(long n, long d) {
long g = gcd(n, d);
this->n = n / g;
this->d = d / g;
}
void iadd(const Fraction& other) {
long numerator = this->n * other.d + this->d * other.n;
long denominator = this->d * other.d;
long g = gcd(numerator, denominator);
this->n = numerator / g;
this->d = denominator / g;
}
static long gcd(long x, long y) {
return x != 0 ? gcd(y % x, x) : y;
}
};
class Solution {
public:
bool isRationalEqual(string S, string T) {
Fraction f1 = convert(S);
Fraction f2 = convert(T);
return f1.n == f2.n && f1.d == f2.d;
}
Fraction convert(string S) {
int state = 0;
Fraction ans(0, 1);
int decimal_size = 0;
vector<string> parts = split(S, ".()");
for (string& part : parts) {
state++;
if (part.empty()) continue;
long x = stol(part);
int sz = part.length();
if (state == 1) {
ans.iadd(Fraction(x, 1));
} else if (state == 2) {
ans.iadd(Fraction(x, pow(10, sz)));
decimal_size = sz;
} else {
long denom = pow(10, decimal_size);
denom *= pow(10, sz) - 1;
ans.iadd(Fraction(x, denom));
}
}
return ans;
}
private:
vector<string> split(const string& s, const string& delimiters) {
vector<string> tokens;
size_t start = 0;
size_t end = s.find_first_of(delimiters);
while (end != string::npos) {
if (end > start)
tokens.push_back(s.substr(start, end - start));
start = end + 1;
end = s.find3 258
Задача: 1002. Find Common Characters
Сложность: easy
Если задан массив строк words, верните массив всех символов, которые встречаются во всех строках внутри слов (включая дубликаты). Вы можете вернуть ответ в любом порядке.
Пример:
Input: words = ["bella","label","roller"] Output: ["e","l","l"]👨💻 Алгоритм: 1⃣Инициализация частотного массива: Создайте массив для хранения минимальной частоты каждого символа, который будет встречаться во всех словах. 2⃣Обработка каждого слова: Для каждого слова создайте временный массив для хранения частоты каждого символа в этом слове. Обновите основной частотный массив, сравнивая его с временным массивом и сохраняя минимальные частоты каждого символа. 3⃣Формирование результата: Создайте результирующий массив, добавляя каждый символ столько раз, сколько его минимальная частота. 😎 Решение:
class Solution {
public:
vector<string> commonChars(vector<string>& words) {
vector<int> min_freq(26, INT_MAX);
for (const string& word : words) {
vector<int> freq(26, 0);
for (char c : word) {
freq[c - 'a']++;
}
for (int i = 0; i < 26; ++i) {
min_freq[i] = min(min_freq[i], freq[i]);
}
}
vector<string> result;
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < min_freq[i]; ++j) {
result.push_back(string(1, 'a' + i));
}
}
return result;
}
};3 258
Задача: 782. Transform to Chessboard
Сложность: hard
Дана бинарная сетка размером n x n. В каждом ходе можно поменять местами любые две строки или любые два столбца.
Верните минимальное количество ходов, чтобы преобразовать сетку в шахматную доску. Если задача невыполнима, верните -1.
Шахматная доска — это доска, на которой ни один 0 и ни одна 1 не соприкасаются друг с другом по вертикали и горизонтали.
Пример:
Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]] Output: 2 Explanation: One potential sequence of moves is shown. The first move swaps the first and second column. The second move swaps the second and third row.👨💻 Алгоритм: 1⃣Для каждого набора строк (и столбцов соответственно) убедитесь, что существует только 2 вида линий в правильных количествах, которые являются противоположностями друг друга. 2⃣Затем для каждой возможной идеальной трансформации этой линии найдите минимальное количество перестановок, чтобы преобразовать эту линию в её идеальную и добавьте это к ответу. Например, [0, 1, 1, 1, 0, 0] имеет два идеала [0, 1, 0, 1, 0, 1] или [1, 0, 1, 0, 1, 0]; но [0, 1, 1, 1, 0] имеет только один идеал [1, 0, 1, 0, 1]. 3⃣В Java мы используем целые числа для представления строк как двоичных чисел. Мы проверяем количество различий с [1, 0, 1, 0, 1, 0, ...] с помощью побитового исключающего ИЛИ с 0b010101010101.....01 = 0x55555555. Чтобы убедиться, что мы не добавляем излишне большие элементы. 😎 Решение:
class Solution {
public:
int movesToChessboard(vector<vector<int>>& board) {
int N = board.size(), ans = 0;
for (auto count : {counter(board), counter(transpose(board))}) {
if (count.size() != 2 || !sortedEquals(count, {N/2, (N+1)/2})) return -1;
auto it = count.begin();
vector<int> line1 = it->first, line2 = (++it)->first;
if (!allOpposite(line1, line2)) return -1;
vector<int> starts = (N % 2 == 0) ? vector<int>{0, 1} : vector<int>{(accumulate(line1.begin(), line1.end(), 0) * 2 > N)};
int minSwaps = INT_MAX;
for (int start : starts) {
int swaps = 0;
for (int i = 0; i < N; i++) {
swaps += (line1[i] != (i % 2 == start ? 1 : 0));
}
minSwaps = min(minSwaps, swaps / 2);
}
ans += minSwaps;
}
return ans;
}
private:
map<vector<int>, int> counter(const vector<vector<int>>& board) {
map<vector<int>, int> count;
for (const auto& row : board) {
count[row]++;
}
return count;
}
vector<vector<int>> transpose(const vector<vector<int>>& board) {
int N = board.size();
vector<vector<int>> transposed(N, vector<int>(N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
transposed[j][i] = board[i][j];
}
}
return transposed;
}
bool allOpposite(const vector<int>& line1, const vector<int>& line2) {
for (int i = 0; i < line1.size(); i++) {
if ((line1[i] ^ line2[i]) == 0) {
return false;
}
}
return true;
}
bool sortedEquals(const map<vector<int>, int>& count, const vector<int>& sortedValues) {
vector<int> values;
for (const auto& [key, value] : count) {
values.push_back(value);
}
sort(values.begin(), values.end());
return values == sortedValues;
}
};3 258
Задача: 1277. Count Square Submatrices with All Ones
Сложность: medium
Если задана матрица m * n из единиц и нулей, верните, сколько квадратных подматриц имеют все единицы.
Пример:
Input: matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] Output: 15👨💻 Алгоритм: 1⃣Создайте вспомогательную матрицу dp таких же размеров, что и исходная матрица, для хранения размеров максимальных квадратов. 2⃣Пройдите по каждому элементу матрицы и обновите dp следующим образом: если элемент равен 1, то dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. 3⃣Суммируйте все значения в dp, чтобы получить количество квадратных подматриц, состоящих из всех единиц. 😎 Решение:
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
int count = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 1) {
if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
}
count += dp[i][j];
}
}
}
return count;
}
};3 258
Задача: 303. Range Sum Query - Immutable
Сложность: easy
Дан целочисленный массив nums. Обработайте несколько запросов следующего типа:
Вычислите сумму элементов массива nums между индексами left и right включительно, где left <= right.
Реализуйте класс NumArray:
- NumArray(int[] nums) Инициализирует объект с целочисленным массивом nums.
- int sumRange(int left, int right) Возвращает сумму элементов массива nums между индексами left и right включительно (т.е. nums[left] + nums[left + 1] + ... + nums[right]).
Пример:
Input ["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]] Output [null, 1, -1, -3]👨💻 Алгоритм: 1⃣Инициализация: Создайте массив sum длиной на один элемент больше, чем массив nums, и заполните его накопленными суммами элементов массива nums. 2⃣Предварительное вычисление сумм: Заполните массив sum, где каждый элемент sum[i + 1] является суммой всех предыдущих элементов массива nums до индекса i включительно. 3⃣Вычисление диапазонной суммы: Для каждого запроса суммы элементов между индексами left и right используйте разницу между sum[right + 1] и sum[left], чтобы быстро получить результат. 😎 Решение:
class NumArray {
private:
vector<int> sum;
public:
NumArray(vector<int>& nums) {
sum.resize(nums.size() + 1);
for (int i = 0; i < nums.size(); i++) {
sum[i + 1] = sum[i] + nums[i];
}
}
int sumRange(int i, int j) {
return sum[j + 1] - sum[i];
}
};3 258
Задача: 1049. Last Stone Weight II
Сложность: medium
Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два любых камня и разбиваем их вместе. Предположим, что камни имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y приобретает новый вес y - x. В конце игры остается не более одного камня. Верните наименьший возможный вес оставшегося камня. Если камней не осталось, верните 0.
Пример:
Input: stones = [2,7,4,1,8,1] Output: 1👨💻 Алгоритм: 1⃣Используй метод динамического программирования, чтобы проверить, можно ли разделить камни на две группы с равной суммой. 2⃣Определи, какие веса можно достичь, используя половину суммы всех камней. 3⃣Найди наибольшую достижимую сумму, которая меньше или равна половине общей суммы, и верни разницу между общей суммой и удвоенной этой суммой.Верни максимальную длину среди всех цепочек. 😎 Решение:
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int totalSum = accumulate(stones.begin(), stones.end(), 0);
int halfSum = totalSum / 2;
vector<int> dp(halfSum + 1, 0);
for (int stone : stones) {
for (int j = halfSum; j >= stone; j--) {
dp[j] = max(dp[j], dp[j - stone] + stone);
}
}
return totalSum - 2 * dp[halfSum];
}
};3 258
Задача: №27. Remove Element
Сложность: easy
Учитывая массив nums и значение val, удалите все вхождения val на месте. Порядок элементов может быть изменён. Верните количество элементов k, которые не равны val, и убедитесь, что первые k элементов массива содержат именно эти значения.
Пример:
Input: nums = [3,2,2,3], val = 3 Output: 2👨💻Алгоритм: 1⃣Заводим указатель k для отслеживания позиции следующего "валидного" элемента. 2⃣Проходим по массиву: если текущий элемент не равен val, записываем его на позицию k и увеличиваем k. 3⃣После цикла k будет содержать количество элементов, не равных val. 😎 Решение:
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int k = 0;
for(int i = 0; i < nums.size(); i++) {
if(nums[i] != val) {
nums[k] = nums[i];
k++;
}
}
return k;
}
};