C/C++ | LeetCode
رفتن به کانال در Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
نمایش بیشتر
3 205
مشترکین
-224 ساعت
-67 روز
-2730 روز
آرشیو پست ها
3 205
Задача: 65. Valid Number
Сложность: hard
Нужно определить, является ли строка s валидным числом, включая целые, десятичные и числа с экспонентой (e или E).
Пример:
Input: s = "0" Output: true👨💻 Алгоритм: 1⃣Объявить флаги: seenDigit — были ли цифры seenDot — была ли точка seenExponent — была ли экспонента 2⃣Пройти по строке посимвольно: Цифра: seenDigit = true Знак (+/-) допустим только в начале строки или сразу после e/E e/E: не должно быть второй экспоненты, и до неё должна быть хотя бы одна цифра .: допустима только один раз и только до e Любой другой символ — false 3⃣В конце вернуть seenDigit, т.к. после e должна быть хотя бы одна цифра 😎 Решение:
class Solution {
public:
bool isNumber(string s) {
bool seenDigit = false;
bool seenExponent = false;
bool seenDot = false;
for (int i = 0; i < s.length(); i++) {
char curr = s[i];
if (curr >= '0' && curr <= '9') {
seenDigit = true;
} else if (curr == '+' || curr == '-') {
if (i > 0 && s[i - 1] != 'e' && s[i - 1] != 'E') {
return false;
}
} else if (curr == 'e' || curr == 'E') {
if (seenExponent || !seenDigit) {
return false;
}
seenExponent = true;
seenDigit = false;
} else if (curr == '.') {
if (seenDot || seenExponent) {
return false;
}
seenDot = true;
} else {
return false;
}
}
return seenDigit;
}
};3 205
Крупнейший университет искусственного интеллекта
Учим использовать ChatGPT в профессиональных целях, создавать нейро-сотрудников и зарабатывать на искусственном интеллекте.
✨ 8 000+ студентов со всего мира
✨ 600+ AI-проектов, созданных студентами
✨ Сборная Университета — победители крупнейших AI-хакатонов России
✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие)
✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие)
Будем рады видеть тебя в наших рядах!
Узнать больше
#реклама 16+
neural-university.ru
О рекламодателе
3 205
Задача: 1265. Print Immutable Linked List in Reverse
Сложность: medium
Вам дан неизменяемый связный список, распечатайте все значения каждого узла в обратном порядке с помощью следующего интерфейса: ImmutableListNode:Интерфейс неизменяемого связанного списка, вам дана голова списка. Для доступа к связанному списку необходимо использовать следующие функции (напрямую к ImmutableListNode обращаться нельзя): ImmutableListNode.printValue(): Выводит значение текущего узла. ImmutableListNode.getNext(): Возвращает следующий узел. Входные данные даются только для внутренней инициализации связанного списка.Вы должны решить эту задачу, не изменяя связанный список. Другими словами, вы должны работать со связанным списком, используя только упомянутые API.
Пример:
Input: head = [1,2,3,4] Output: [4,3,2,1]👨💻 Алгоритм: 1⃣Используйте рекурсию для достижения конца связного списка. 2⃣На обратном пути рекурсии распечатайте значение каждого узла. 3⃣Обратный порядок достигается благодаря природе рекурсии (стек вызовов). 😎 Решение:
class ImmutableListNode {
public:
void printValue();
ImmutableListNode* getNext();
};
class Solution {
public:
void printLinkedListInReverse(ImmutableListNode* head) {
if (head->getNext() != nullptr) {
printLinkedListInReverse(head->getNext());
}
head->printValue();
}
};3 205
Современная магистратура от Центрального университета
Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой?
Поступай в магистратуру Центрального университета!
- 4 офлайн программы по востребованным направлениям ИТ
- Онлайн-программа по машинному обучению
- 300 мест с грантами до 1,2 млн руб.
- Вечерние занятия и учеба по выходным — удобно совмещать с работой
- Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса
- Возможность стажировок и трудоустройства в ведущих компаниях
- Государственный диплом за 2 года
Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии.
Оставляй заявку на грант уже сейчас!
Подать заявку
#реклама 16+
apply.centraluniversity.ru
О рекламодателе
3 205
Задача: 965. Univalued Binary Tree
Сложность: medium
Дан список слов, и нам нужно реализовать проверку орфографии, которая преобразует слово запроса в правильное слово.
Для данного слова запроса, проверка орфографии обрабатывает две категории ошибок правописания:
Заглавные буквы: если запрос совпадает со словом в списке слов (без учета регистра), то слово запроса возвращается с таким же регистром, как и в списке слов.
Пример: wordlist = ["yellow"], query = "YellOw": correct = "yellow"
Пример: wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
Пример: wordlist = ["yellow"], query = "yellow": correct = "yellow"
Ошибки гласных: если после замены гласных ('a', 'e', 'i', 'o', 'u') в слове запроса на любую гласную по отдельности оно совпадает со словом в списке слов (без учета регистра), то слово запроса возвращается с таким же регистром, как и совпадающее слово в списке слов.
Пример: wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
Пример: wordlist = ["YellOw"], query = "yeellow": correct = "" (нет совпадения)
Пример: wordlist = ["YellOw"], query = "yllw": correct = "" (нет совпадения)
Кроме того, проверка орфографии работает по следующим правилам приоритета:
Когда запрос точно совпадает со словом в списке слов (с учетом регистра), вы должны вернуть это же слово.
Когда запрос совпадает со словом за исключением регистра, вы должны вернуть первое такое совпадение в списке слов.
Когда запрос совпадает со словом за исключением ошибок гласных, вы должны вернуть первое такое совпадение в списке слов.
Если запрос не имеет совпадений в списке слов, вы должны вернуть пустую строку.
Дан массив запросов, верните список слов answer, где answer[i] — правильное слово для query = queries[i].
Пример:
Input: wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"] Output: ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]👨💻 Алгоритм: 1⃣Используйте множество для хранения слов из списка, чтобы проверять точные совпадения. 2⃣Используйте хэш-таблицу для хранения слов в нижнем регистре и соответствующих слов из списка для проверки совпадений без учета регистра. 3⃣Используйте хэш-таблицу для хранения слов в нижнем регистре с замененными гласными символами и соответствующих слов из списка для проверки совпадений с ошибками гласных. 😎 Решение:
class Solution {
public:
unordered_set<string> words_perfect;
unordered_map<string, string> words_cap;
unordered_map<string, string> words_vow;
vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
for (const string& word : wordlist) {
words_perfect.insert(word);
string wordlow = toLower(word);
words_cap.insert({wordlow, word});
string wordlowDV = devowel(wordlow);
words_vow.insert({wordlowDV, word});
}
vector<string> ans;
for (const string& query : queries) {
ans.push_back(solve(query));
}
return ans;
}
string solve(const string& query) {
if (words_perfect.count(query)) {
return query;
}
string queryL = toLower(query);
if (words_cap.count(queryL)) {
return words_cap[queryL];
}
string queryLV = devowel(queryL);
if (words_vow.count(queryLV)) {
return words_vow[queryLV];
}
return "";
}
string toLower(const string& str) {
string result = str;
transform(result.begin(), result.end(), result.begin(), ::tolower);
return result;
}
string devowel(const string& word) {
string result = word;
for (char& c : result) {
if (isVowel(c)) {
c = '*';
}
}
return result;
}
bool isVowel(char c) {
return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
}
};3 205
Дарим подписку на Яндекс Музыку
Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких.
Кинопоиск и Яндекс Книги тоже в подписке.
Попробуйте бесплатно❤️
Попробовать
#реклама 18+
music.yandex.ru
О рекламодателе
Реклама на Яндексе
3 205
Задача: 936. Stamping The Sequence
Сложность: hard
Вам даны две строки stamp и target. Изначально имеется строка s длины target.length со всеми s[i] == '?'. За один ход вы можете поместить штамп над s и заменить каждую букву в s на соответствующую букву из штампа. Например, если штамп = "abc" и target = "abcba", то s изначально будет "?????". За один ход вы можете: поместить штамп в индекс 0 s, чтобы получить "abc??", поместить штамп в индекс 1 s, чтобы получить "?abc?", или поместить штамп в индекс 2 s, чтобы получить "??abc". Обратите внимание, что штамп должен полностью находиться в границах s, чтобы штамповать (то есть вы не можете поместить штамп в индекс 3 s). Мы хотим преобразовать s в цель, используя не более 10 * target.length ходов. Верните массив индекса самой левой буквы, которая штампуется на каждом ходу. Если мы не можем получить цель из s за 10 * target.length оборотов, верните пустой массив
Пример:
Input: stamp = "abc", target = "ababc" Output: [0,2]👨💻 Алгоритм: 1⃣Инициализировать переменные: s как массив символов '?', длиной target.length. res как список для хранения результатов. done как массив булевых значений для отслеживания того, какие позиции уже штампованы. target как массив символов для удобства. 2⃣Использовать функцию canStamp для проверки, можно ли штамповать stamp в target начиная с индекса i. Использовать функцию doStamp для штампования stamp в target начиная с индекса i. Повторять шаги, пока штампы возможны или достигнут максимум ходов (10 * target.length): Перебрать все возможные начальные позиции для штампа. Проверить, можно ли штамповать в текущей позиции. Если можно, штамповать и добавить индекс в res. 3⃣Если все символы в s соответствуют символам в target, вернуть массив res в обратном порядке. Иначе, вернуть пустой массив. 😎 Решение:
class Solution {
public:
vector<int> movesToStamp(string stamp, string target) {
vector<int> res;
vector<bool> done(target.size(), false);
string t = target;
string s = stamp;
int m = s.size(), n = t.size();
auto canStamp = [&](int i) {
for (int j = 0; j < m; j++) {
if (t[i + j] != '?' && t[i + j] != s[j]) {
return false;
}
}
return true;
};
auto doStamp = [&](int i) {
for (int j = 0; j < m; j++) {
t[i + j] = '?';
}
res.push_back(i);
done[i] = true;
};
bool changed = true;
while (changed) {
changed = false;
for (int i = 0; i <= n - m; i++) {
if (!done[i] && canStamp(i)) {
doStamp(i);
changed = true;
}
}
}
for (char c : t) {
if (c != '?') {
return {};
}
}
reverse(res.begin(), res.end());
return res;
}
};3 205
Стартуй в бизнесе на ИЗЗЗИ вместе со Сбером
Открой счёт за 0 рублей и получи:
✅ До 100 000 бонусов СберБизнес Спасибо на полезные сервисы
✅ Избавление от рутины: бесплатная бухгалтерия для бизнеса на 6 месяцев
Это твой знак начать своё дело!
Узнать больше
Финансовые услуги оказывает: ПАО Сбербанк.
#реклама
sberbank.com
О рекламодателе
3 205
Задача: 426. Convert Binary Search Tree to Sorted Doubly Linked List
Сложность: medium
Преобразуйте двоичное дерево поиска в отсортированный кольцевой двусвязный список на месте.
Вы можете считать, что указатели "влево" и "вправо" аналогичны указателям на предшественника и последователя в двусвязном списке. Для кольцевого двусвязного списка предшественник первого элемента является последним элементом, а последователь последнего элемента является первым элементом.
Мы хотим выполнить преобразование на месте. После преобразования левый указатель узла дерева должен указывать на его предшественника, а правый указатель должен указывать на его последователя. Вы должны вернуть указатель на самый маленький элемент списка.
Пример:
Input: root = [4,2,5,1,3] Output: [1,2,3,4,5] Explanation: The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.👨💻 Алгоритм: 1⃣Инициализируйте первые и последние узлы как null. 2⃣Вызовите стандартную вспомогательную рекурсивную функцию helper(root): Если узел не равен null: Вызовите рекурсию для левого поддерева helper(node.left). Если последний узел не равен null, свяжите последний узел и текущий узел. Иначе инициализируйте первый узел. Пометьте текущий узел как последний: last = node. Вызовите рекурсию для правого поддерева helper(node.right). 3⃣Свяжите первые и последние узлы, чтобы замкнуть кольцевой двусвязный список, затем верните первый узел. 😎 Решение:
class Node {
public:
int val;
Node* left;
Node* right;
Node() {}
Node(int _val) {
val = _val;
left = NULL;
right = NULL;
}
Node(int _val, Node* _left, Node* _right) {
val = _val;
left = _left;
right = _right;
}
};
class Solution {
public:
Node* first = NULL;
Node* last = NULL;
void helper(Node* node) {
if (node != NULL) {
helper(node->left);
if (last != NULL) {
last->right = node;
node->left = last;
} else {
first = node;
}
last = node;
helper(node->right);
}
}
Node* treeToDoublyList(Node* root) {
if (root == NULL) return NULL;
helper(root);
last->right = first;
first->left = last;
return first;
}
};3 205
Освойте профессию Системный аналитик с нуля за 7 месяцев
Освойте высокооплачиваемую IT-профессию без программирования. Выдаём диплом, помогаем с трудоустройством.
Excel, BPMN, UML, Python, SQL, API
Преимущества обучения в Академии Eduson:
🎓 22 реальных бизнес-кейса
🎓 официальный государственный диплом
🎓 рассрочка 0% на 24 мес.
🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются
🎓 личный куратор с Вами на связи
Начните обучаться онлайн и получать доход уже во время обучения!
Получить скидку
#реклама 16+
mrqz.me
О рекламодателе
3 205
Задача: 318. Maximum Product of Word Lengths
Сложность: medium
Дан массив строк
words, верните максимальное значение произведения длины word[i] на длину word[j], где два слова не имеют общих букв. Если таких двух слов не существует, верните 0.
Пример:
Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"] Output: 16 Explanation: The two words can be "abcw", "xtfn".👨💻 Алгоритм: 1⃣Предварительная обработка масок и длин Вычислите битовые маски для всех слов и сохраните их в массиве masks. Сохраните длины всех слов в массиве lens. 2⃣Сравнение слов и проверка общих букв Сравните каждое слово с каждым последующим словом. Если два слова не имеют общих букв (проверка с использованием масок: (masks[i] & masks[j]) == 0), обновите максимальное произведение maxProd. 3⃣Возврат результата Верните максимальное значение произведения maxProd. 😎 Решение:
class Solution {
public:
int maxProduct(vector<string>& words) {
int n = words.size();
vector<int> masks(n);
vector<int> lens(n);
for (int i = 0; i < n; i++) {
int bitmask = 0;
for (char ch : words[i]) {
bitmask |= 1 << (ch - 'a');
}
masks[i] = bitmask;
lens[i] = words[i].size();
}
int maxVal = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if ((masks[i] & masks[j]) == 0) {
maxVal = max(maxVal, lens[i] * lens[j]);
}
}
}
return maxVal;
}
};3 205
Задача: 665. Non-decreasing Array
Сложность: medium
Дан массив nums из n целых чисел. Ваша задача - проверить, можно ли сделать его неубывающим, изменив не более одного элемента.
Мы определяем массив как неубывающий, если для каждого i (индексация с 0), такого что 0 <= i <= n - 2, выполняется условие nums[i] <= nums[i + 1].
Пример:
Input: nums = [4,2,3] Output: true Explanation: You could modify the first 4 to 1 to get a non-decreasing array.👨💻 Алгоритм: 1⃣Инициализация переменных: Завести переменную count для подсчета числа изменений. Проверить последовательность чисел в массиве nums. 2⃣Проверка условий: Если nums[i] > nums[i + 1], то увеличиваем count. Если count превышает 1, возвращаем false, так как больше одного изменения недопустимо. Если nums[i - 1] > nums[i + 1] и nums[i] > nums[i + 2], то возвращаем false. 3⃣вВозврат результата: Если количество изменений не превышает 1, вернуть true. 😎 Решение:
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int count = 0;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] < nums[i - 1]) {
if (count > 0) {
return false;
}
count++;
if (i == 1 || nums[i] >= nums[i - 2]) {
nums[i - 1] = nums[i];
} else {
nums[i] = nums[i - 1];
}
}
}
return true;
}
};3 205
Получи грант на обучение в Центральном университете
Центральный университет выдает гранты на 4 года обучения в бакалавриате.
Грант покрывает до 100% стоимости обучения. Участвуй в отборе, чтобы получить грант.
Получи доступ к уникальным активностям для абитуриентов. Для выпускников 10-х, 11-х классов и колледжей.
Подать заявку
#реклама
apply.centraluniversity.ru
О рекламодателе
3 205
Задача: 289. Game of Life
Сложность: medium
Согласно статье Википедии: "Игра Жизнь, также известная просто как Жизнь, — это клеточный автомат, созданный британским математиком Джоном Хортоном Конуэем в 1970 году."
Доска состоит из сетки клеток размером m x n, где каждая клетка имеет начальное состояние: живая (представляется числом 1) или мёртвая (представляется числом 0). Каждая клетка взаимодействует с восемью соседями (по горизонтали, вертикали и диагоналям) согласно следующим четырём правилам (взято из вышеупомянутой статьи Википедии):
Любая живая клетка с менее чем двумя живыми соседями умирает, как будто из-за недостатка населения.
Любая живая клетка с двумя или тремя живыми соседями остаётся живой до следующего поколения.
Любая живая клетка с более чем тремя живыми соседями умирает, как будто из-за перенаселения.
Любая мёртвая клетка с ровно тремя живыми соседями становится живой, как будто вследствие размножения.
Следующее состояние создаётся путем одновременного применения вышеупомянутых правил ко всем клеткам в текущем состоянии, где рождения и смерти происходят одновременно. Дано текущее состояние сетки m x n, верните следующее состояние.
Пример:
Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]] Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]👨💻 Алгоритм: 1⃣Итерация по клеткам доски: Пройдите через каждую клетку на доске. Для каждой клетки подсчитайте количество живых соседей, проверяя все восемь соседних клеток. 2⃣Применение правил: На основе количества живых соседей и текущего состояния клетки примените правила игры: Любая живая клетка с менее чем двумя живыми соседями умирает (становится -1). Любая живая клетка с двумя или тремя живыми соседями остаётся живой (без изменений). Любая живая клетка с более чем тремя живыми соседями умирает (становится -1). Любая мёртвая клетка с ровно тремя живыми соседями становится живой (становится 2). 3⃣Обновление доски: Пройдите через доску ещё раз и обновите состояния клеток: Если значение клетки больше 0, установите её в 1 (живая). Если значение клетки меньше или равно 0, установите её в 0 (мёртвая). 😎 Решение:
class Solution {
public:
void gameOfLife(vector<vector<int>>& board) {
vector<int> neighbors = {0, 1, -1};
int rows = board.size();
int cols = board[0].size();
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
int liveNeighbors = 0;
for (int i : neighbors) {
for (int j : neighbors) {
if (!(i == 0 && j == 0)) {
int r = row + i;
int c = col + j;
if (r >= 0 && r < rows && c >= 0 && c < cols && abs(board[r][c]) == 1) {
liveNeighbors++;
}
}
}
}
if (board[row][col] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {
board[row][col] = -1;
}
if (board[row][col] == 0 && liveNeighbors == 3) {
board[row][col] = 2;
}
}
}
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
board[row][col] = (board[row][col] > 0) ? 1 : 0;
}
}
}
};3 205
Data и ML для бизнеса. Большая конференция Яндекса
Узнайте, как ускорить создание продуктов, упростить процессы и снизить расходы.
Зарегистрироваться
#реклама 16+
yandex.cloud
О рекламодателе
Реклама на Яндексе
3 205
Задача: 682. Baseball Game
Сложность: medium
Вы ведете учет очков в бейсбольной игре с необычными правилами. В начале игры у вас пустая запись.
Вам дается список строк operations, где operations[i] — это i-я операция, которую вы должны применить к записи, и она может быть одной из следующих:
Целое число x.
Записать новый счет, равный x.
'+'.
Записать новый счет, который является суммой двух предыдущих очков.
'D'.
Записать новый счет, который в два раза больше предыдущего очка.
'C'.
Аннулировать предыдущее очко, удалив его из записи.
Верните сумму всех очков в записи после применения всех операций.
Тестовые случаи сформированы таким образом, что ответ и все промежуточные вычисления умещаются в 32-битное целое число, и что все операции корректны.
Пример:
Input: ops = ["5","2","C","D","+"]
Output: 30
Explanation:
"5" - Add 5 to the record, record is now [5].
"2" - Add 2 to the record, record is now [5, 2].
"C" - Invalidate and remove the previous score, record is now [5].
"D" - Add 2 * 5 = 10 to the record, record is now [5, 10].
"+" - Add 5 + 10 = 15 to the record, record is now [5, 10, 15].
The total sum is 5 + 10 + 15 = 30.class Solution {
public:
int calPoints(vector<string>& ops) {
stack<int> stack;
for (string op : ops) {
if (op == "+") {
int top = stack.top();
stack.pop();
int newTop = top + stack.top();
stack.push(top);
stack.push(newTop);
} else if (op == "C") {
stack.pop();
} else if (op == "D") {
stack.push(2 * stack.top());
} else {
stack.push(stoi(op));
}
}
int ans = 0;
while (!stack.empty()) {
ans += stack.top();
stack.pop();
}
return ans;
}
};3 205
Битрикс24 дропнул новую фичу — онлайн-доски
Теперь к вашему рабочему мессенджеру, видеозвонкам и таскам добавился еще один маст-хэв инструмент. Все это бесплатно и в одном комплекте. Офисные стикеры, берегитесь.😊
Узнать больше
#реклама 16+
bitrix24.ru
О рекламодателе
3 205
Задача: 186. Reverse Words in a String II
Сложность: medium
Дан массив символов s, переверните порядок слов.
Слово определяется как последовательность символов, не являющихся пробелами.
Слова в s разделены одним пробелом.
Решение должно быть in-place, без использования дополнительной памяти.
Пример:
Input: s = ["a"] Output: ["a"]👨💻 Алгоритм: 1⃣Перевернуть всю строку: Разворачиваем весь массив символов от начала до конца. 2⃣Перевернуть каждое слово: Проходим по массиву, находим границы слов и переворачиваем символы внутри каждого слова. 3⃣Окончательная корректировка: Поскольку пробелы гарантированы как одиночные, дополнительных манипуляций с ними не требуется. 😎 Решение:
class Solution {
public:
void reverseWords(vector<char>& s) {
reverse(s.begin(), s.end());
int start = 0, end = 0;
int n = s.size();
while (start < n) {
while (end < n && s[end] != ' ')
end++;
reverse(s.begin() + start, s.begin() + end);
end++;
start = end;
}
}
};3 205
+3
Подключите спутниковый интернет за городом. Доступно
Интернет там, где нужно - для офиса или загородного дома.
Мы предлагаем:
👍Высокую скорость до 100 Мбит/с.
👍Доступные цены на оборудование и установку.
👍Выгодные тарифы, как для частных домовладельцев, так и для коллективных подключений.
👍Надежное подключение во всех регионах России.
Подобрать подходящий вам тариф и оставить заявку на подключение - по ссылке ниже!
Узнать больше
#реклама
radiointernet1.ru
О рекламодателе
3 205
Задача: 1429. First Unique Number
Сложность: medium
У вас есть очередь целых чисел, необходимо извлечь первый уникальный элемент из очереди.
Реализуйте класс FirstUnique:
- FirstUnique(int[] nums) Инициализирует объект числами в очереди.
- int showFirstUnique() возвращает значение первого уникального элемента в очереди и возвращает -1, если такого элемента нет.
- void add(int value) вставляет значение в очередь.
Пример:
Input:
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output:
[null,2,null,2,null,3,null,-1]
Explanation:
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5); // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2); // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3); // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1#include <unordered_map>
#include <unordered_set>
#include <list>
class FirstUnique {
public:
FirstUnique(vector<int>& nums) {
for (int num : nums) {
add(num);
}
}
int showFirstUnique() {
if (!queue.empty()) {
return queue.front();
}
return -1;
}
void add(int value) {
if (isUnique.find(value) == isUnique.end()) {
isUnique[value] = true;
queue.push_back(value);
} else if (isUnique[value]) {
isUnique[value] = false;
queue.remove(value);
}
}
private:
list<int> queue;
unordered_map<int, bool> isUnique;
};