现已上线！2025 年 Telegram 研究 — 年度关键洞察 
C/C++ | LeetCode
前往频道在 Telegram
Cайт easyoffer.ru Реклама @easyoffer_adv ВП @easyoffer_vp Тесты t.me/+zYofcX2VLTM3MGMy Вопросы собесов t.me/+BTbqlW1VbIFmYmVi Вакансии t.me/+za2mJYs4riAzMzFi
显示更多3 260
订阅者
无数据24 小时
-17 天
-430 天
帖子存档
3 261
Задача: 101. Symmetric Tree
Сложность: easy
Дан корень бинарного дерева. Проверьте, является ли это дерево зеркальным отражением самого себя (то есть симметричным относительно своего центра).
Пример:
Input: root = [1,2,2,3,4,4,3] Output: true👨💻 Алгоритм: 1⃣Дерево симметрично, если его левое и правое поддеревья являются зеркальным отражением друг друга. 2⃣Два дерева — зеркальные, если их корни равны и правое поддерево одного совпадает с левым другого. 3⃣Используйте рекурсию: сравните правое поддерево первого с левым поддеревом второго, и наоборот. 😎 Решение:
class Solution {
public:
bool isSymmetric(TreeNode* root) { return isMirror(root, root); }
bool isMirror(TreeNode* t1, TreeNode* t2) {
if (t1 == nullptr && t2 == nullptr) return true;
if (t1 == nullptr || t2 == nullptr) return false;
return (t1->val == t2->val) && isMirror(t1->right, t2->left) &&
isMirror(t1->left, t2->right);
}
};3 261
🔥Стажировки и вакансии для IT специалистов
- Вакансии которых нет на джоб-агрегаторах
- Только прямые контакты HR в Telegram
🤖 ML & DS 👩💻 DevOps
👨✈️ ИБ & OSINT 👣 Go
👩💻 Mobile 👩💻 C#
👩💻 Node.js 👩💻 Python
🔎 QA 👩💻 Java
👩💻 UX/UI 👩💻 Frontend
🖼️ PHP 📋 Analyst
💼 1C 🖥 SQL
👩💻 IT HR
Пока другие листают джоб-сайты — ты уже пишешь HR в Telegram.
3 261
Задача: 127. Word Ladder
Сложность: hard
Дано: beginWord, endWord и wordList. Найдите длину кратчайшей цепочки преобразования из beginWord в endWord, где каждое слово отличается ровно одной буквой, и каждое промежуточное слово должно быть в wordList.
Пример:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5 Explanation: "hit" → "hot" → "dot" → "dog" → "cog" — цепочка из 5 слов👨💻 Алгоритм: 1⃣Преобразование слов: Для каждого слова из wordList формируем промежуточные состояния, заменяя по одной букве на *. Например, "hot" → "*ot", "h*t", "ho*". Сохраняем в unordered_map<string, vector<string>> allComboDict. 2⃣BFS: Стартуем с beginWord, кладем в очередь (beginWord, 1) — слово и уровень. Храним visited, чтобы не зациклиться. На каждом шаге: генерируем все промежуточные состояния *ot, h*t, ... смотрим в allComboDict, какие слова подходят добавляем их в очередь с level + 1 если встречаем endWord — возвращаем level + 1 3⃣Если очередь опустела, а endWord не найден — возвращаем 0. 😎 Решение:
#include <unordered_map>
#include <vector>
#include <queue>
#include <string>
using namespace std;
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
int L = beginWord.size();
unordered_map<string, vector<string>> allComboDict;
for (string word : wordList) {
for (int i = 0; i < L; i++) {
string newWord = word.substr(0, i) + '*' + word.substr(i + 1);
allComboDict[newWord].push_back(word);
}
}
queue<pair<string, int>> Q;
Q.push({beginWord, 1});
unordered_map<string, bool> visited;
visited[beginWord] = true;
while (!Q.empty()) {
auto [word, level] = Q.front();
Q.pop();
for (int i = 0; i < L; i++) {
string newWord = word.substr(0, i) + '*' + word.substr(i + 1);
for (string& adjacentWord : allComboDict[newWord]) {
if (adjacentWord == endWord) return level + 1;
if (!visited[adjacentWord]) {
visited[adjacentWord] = true;
Q.push({adjacentWord, level + 1});
}
}
}
}
return 0;
}
};3 261
Задача: 897. Increasing Order Search Tree
Сложность: easy
Задав корень дерева двоичного поиска, перестройте дерево по порядку так, чтобы самый левый узел дерева теперь был корнем дерева, а каждый узел не имел левого и только одного правого дочернего узла.
Пример:
Input: root = [5,3,6,2,4,null,8,1,null,null,null,7,9] Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]👨💻 Алгоритм: 1⃣Выполнить обход дерева в порядке in-order, чтобы получить список узлов. 2⃣Перестроить дерево, устанавливая каждый узел из списка как правый дочерний элемент предыдущего узла и устанавливая левые дочерние элементы в null. 3⃣Вернуть новый корень дерева (первый элемент списка). 😎 Решение:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode* increasingBST(TreeNode* root) {
vector<TreeNode*> nodes;
inorder(root, nodes);
for (int i = 0; i < nodes.size() - 1; ++i) {
nodes[i]->left = nullptr;
nodes[i]->right = nodes[i + 1];
}
nodes.back()->left = nullptr;
nodes.back()->right = nullptr;
return nodes.front();
}
void inorder(TreeNode* node, vector<TreeNode*>& nodes) {
if (node == nullptr) return;
inorder(node->left, nodes);
nodes.push_back(node);
inorder(node->right, nodes);
}
};3 261
Задача: 641. Design Circular Deque
Сложность: medium
Разработайте свою реализацию круговой двусторонней очереди (deque). Реализуйте класс MyCircularDeque: MyCircularDeque(int k) Инициализирует deque с максимальным размером k. boolean insertFront() Добавляет элемент в переднюю часть Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean insertLast() Добавляет элемент в заднюю часть Deque. Возвращает true, если операция выполнена успешно, или false в противном случае. boolean deleteFront() Удаляет элемент из передней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. boolean deleteLast() Удаляет элемент из задней части Deque. Возвращает true, если операция прошла успешно, или false в противном случае. int getFront() Возвращает передний элемент из Deque. Возвращает -1, если Deque пуст. int getRear() Возвращает последний элемент из Deque. Возвращает -1, если Deque пуст. boolean isEmpty() Возвращает true, если Deque пуст, или false в противном случае. boolean isFull() Возвращает true, если Deque полон, или false в противном случае.
Пример:
Input ["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"] [[3], [1], [2], [3], [4], [], [], [], [4], []] Output [null, true, true, true, false, 2, true, true, true, 4]👨💻 Алгоритм: 1⃣Инициализация и проверка состояний: Реализуйте конструктор для инициализации кольцевой двусторонней очереди заданного размера и методы для проверки пустоты и полноты очереди. 2⃣Операции вставки: Реализуйте методы вставки элементов в переднюю и заднюю части очереди с учетом кольцевой структуры. 3⃣Операции удаления: Реализуйте методы удаления элементов из передней и задней частей очереди с учетом кольцевой структуры и методы для получения переднего и заднего элементов очереди. 😎 Решение:
class MyCircularDeque {
public:
MyCircularDeque(int k) : deque(k), front(0), rear(0), size(0), capacity(k) {}
bool insertFront(int value) {
if (isFull()) return false;
front = (front - 1 + capacity) % capacity;
deque[front] = value;
size++;
return true;
}
bool insertLast(int value) {
if (isFull()) return false;
deque[rear] = value;
rear = (rear + 1) % capacity;
size++;
return true;
}
bool deleteFront() {
if (isEmpty()) return false;
front = (front + 1) % capacity;
size--;
return true;
}
bool deleteLast() {
if (isEmpty()) return false;
rear = (rear - 1 + capacity) % capacity;
size--;
return true;
}
int getFront() {
if (isEmpty()) return -1;
return deque[front];
}
int getRear() {
if (isEmpty()) return -1;
return deque[(rear - 1 + capacity) % capacity];
}
bool isEmpty() {
return size == 0;
}
bool isFull() {
return size == capacity;
}
private:
vector<int> deque;
int front;
int rear;
int size;
int capacity;
};3 261
Задача: 954. Array of Doubled Pairs
Сложность: medium
Если задан целочисленный массив четной длины arr, верните true, если можно переупорядочить arr так, чтобы arr[2 * i + 1] = 2 * arr[2 * i] для каждого 0 <= i < len(arr) / 2, или false в противном случае.
Пример:
Input: arr = [3,1,3,6] Output: false👨💻 Алгоритм: 1⃣Подсчитать частоту каждого элемента в массиве. Отсортировать массив по абсолютным значениям элементов. 2⃣Для каждого элемента в отсортированном массиве: Проверить, можно ли сопоставить его с элементом, равным его удвоенному значению. Уменьшить счетчик обоих элементов в словаре частот. 3⃣Если для каждого элемента можно найти пару, вернуть true, иначе вернуть false. 😎 Решение:
class Solution {
public:
bool canReorderDoubled(vector<int>& arr) {
unordered_map<int, int> count;
for (int num : arr) {
count[num]++;
}
sort(arr.begin(), arr.end(), [](int a, int b) { return abs(a) < abs(b); });
for (int num : arr) {
if (count[num] == 0) continue;
if (count[2 * num] == 0) return false;
count[num]--;
count[2 * num]--;
}
return true;
}
};3 261
Задача: 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 261
Задача: 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 261
Задача: 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 261
Задача: 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 261
Задача: 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 261
Задача: 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 261
Задача: 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 261
Задача: 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 261
Задача: 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 261
Задача: 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 261
Задача: 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 261
Задача: 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 261
Задача: 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 261
Задача: 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.find