C/C++ | LeetCode
前往频道在 Telegram
Сайт: https://easyoffer.ru/ Все каналы: t.me/+xGeAw6ckJ4liYzQy Контакт для рекламы: @sendme_ads
显示更多
3 202
订阅者
-224 小时
-57 天
-2830 天
帖子存档
3 202
👩💻 Есть опыт в проге, но не растет зп? Может нужно найти крутой оффер?
🗿 Большинство IT специалистов работает за копейки и даже не осознает этого. Лучший способ понять рынок вакансий - стать его частью и начать анализировать.
👍 Предела совершенству нет, что нельзя сказать про зп в рамках одной компании. Подпишись на Мидл работает и повышай свой капитал.
3 202
#Medium
Задача: 148. Sort List
Дан указатель на начало связанного списка. Верните список после его сортировки в порядке возрастания.
Пример:
Input: head = [4,2,1,3] Output: [1,2,3,4]👨💻 Алгоритм: 1️⃣Разделение списка (Фаза разделения): Рекурсивно разделяйте исходный список на две половины. Процесс разделения продолжается до тех пор, пока в связанном списке не останется только один узел. Для разделения списка на две части используется подход с быстрым и медленным указателями, как упоминается в методе поиска середины связанного списка. 2️⃣Сортировка подсписков и их объединение (Фаза слияния): Рекурсивно сортируйте каждый подсписок и объединяйте их в один отсортированный список. Это аналогично задаче слияния двух отсортированных связанных списков. 3️⃣Иллюстрация процесса сортировки: Процесс продолжается до тех пор, пока не будет получен исходный список в отсортированном порядке. Например, для связанного списка [10,1,60,30,5] описан процесс сортировки слиянием с использованием подхода сверху вниз. Если у нас есть отсортированные списки list1 = [1,10] и list2 = [5,30,60], следующая анимация иллюстрирует процесс слияния обоих списков в один отсортированный список. 😎 Решение:
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* mid = getMid(head);
ListNode* left = sortList(head);
ListNode* right = sortList(mid);
return merge(left, right);
}
ListNode* merge(ListNode* list1, ListNode* list2) {
ListNode dummyHead(0);
ListNode* ptr = &dummyHead;
while (list1 && list2) {
if (list1->val < list2->val) {
ptr->next = list1;
list1 = list1->next;
} else {
ptr->next = list2;
list2 = list2->next;
}
ptr = ptr->next;
}
if (list1)
ptr->next = list1;
else
ptr->next = list2;
return dummyHead.next;
}
ListNode* getMid(ListNode* head) {
ListNode* midPrev = nullptr;
while (head && head->next) {
midPrev = (midPrev == nullptr) ? head : midPrev->next;
head = head->next->next;
}
ListNode* mid = midPrev->next;
midPrev->next = nullptr;
return mid;
}
};3 202
#medium
Задача: 147. Insertion Sort List
Дана голова односвязного списка. Отсортируйте список, используя сортировку вставками, и верните голову отсортированного списка.
Шаги алгоритма сортировки вставками:
1. Сортировка вставками итеративно работает, потребляя один входной элемент за каждую итерацию и формируя отсортированный выходной список.
2. На каждой итерации сортировка вставками удаляет один элемент из входных данных, находит место, куда он принадлежит в отсортированном списке, и вставляет его туда.
3. Процесс повторяется до тех пор, пока не закончатся входные элементы.
Пример:
Input: head = [4,2,1,3] Output: [1,2,3,4]👨💻 Алгоритм: 1️⃣Создание вспомогательного узла (pseudo_head): В качестве первого шага создайте вспомогательный узел, который называется pseudo_head. Этот узел будет использоваться как указатель на начало результирующего списка. Этот узел облегчает доступ к результирующему списку, особенно когда необходимо вставить новый элемент в начало списка. Этот прием значительно упрощает логику работы с односвязным списком. 2️⃣Механизм вставки узла: В односвязном списке каждый узел содержит только один указатель, который указывает на следующий узел. Чтобы вставить новый узел (например, B) перед определенным узлом (например, A), необходимо знать узел (например, C), который находится перед узлом A (т.е. C -> A). Имея ссылку на узел C, можно вставить новый узел так, чтобы получилось C -> B -> A. 3️⃣Использование пары указателей для вставки: Используя пару указателей (prev и next), которые служат местом для вставки нового элемента между ними, вставьте новый элемент в список. Это делается путем установки prev -> new_node -> next. Этот метод позволяет точно и безопасно вставлять новые элементы в список, сохраняя при этом правильный порядок элементов без необходимости перемещения других узлов списка. 😎 Решение:
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode* dummy = new ListNode();
ListNode* curr = head;
while (curr != NULL) {
ListNode* prev = dummy;
while (prev->next != NULL && prev->next->val <= curr->val) {
prev = prev->next;
}
ListNode* next = curr->next;
curr->next = prev->next;
prev->next = curr;
curr = next;
}
return dummy->next;
}
};3 202
#medium
Задача: 146. LRU Cache
Реализуйте класс LRUCache:
LRUCache(int capacity) - инициализирует LRU-кэш с положительным размером capacity.
int get(int key) - возвращает значение по ключу, если ключ существует, в противном случае возвращает -1.
void put(int key, int value) - обновляет значение по ключу, если ключ существует. В противном случае добавляет пару ключ-значение в кэш. Если количество ключей превышает установленную емкость после этой операции, удаляет наименее недавно использованный ключ.
Функции get и put должны выполняться за среднее время O(1).
Пример:
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]struct Node {
int key;
int val;
Node *next;
Node *prev;
Node(int key, int val) : key(key), val(val), next(nullptr), prev(nullptr) {}
};
class LRUCache {
public:
int capacity;
unordered_map<int, Node *> dic;
Node *head = new Node(-1, -1);
Node *tail = new Node(-1, -1);
LRUCache(int capacity) {
this->capacity = capacity;
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (dic.find(key) == dic.end()) {
return -1;
}
Node *node = dic[key];
remove(node);
add(node);
return node->val;
}
void put(int key, int value) {
if (dic.find(key) != dic.end()) {
Node *oldNode = dic[key];
remove(oldNode);
}
Node *node = new Node(key, value);
dic[key] = node;
add(node);
if (dic.size() > capacity) {
Node *nodeToDelete = head->next;
remove(nodeToDelete);
dic.erase(nodeToDelete->key);
}
}
void add(Node *node) {
Node *previousEnd = tail->prev;
previousEnd->next = node;
node->prev = previousEnd;
node->next = tail;
tail->prev = node;
}
void remove(Node *node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
};3 202
🤬 Постоянные ошибки, как они надоели!
🤯 Планируя свои дела, мы забываем, что оборудование может подвести. Это может перекрыть все рабочие планы. Придется гуглить, смотреть видосы, звонить знакомым "Не встречалась ли тебе такая ошибка?"
🥵 Все это время и силы. Наша команда нашла этому решение - Битый код. Канал, который даст тебе базу в мире ошибок.
🍸 Стань тем человеком, к которому будут обращаться и про которого будут говорить "Он сможет помочь"
3 202
#easy
Задача: 145. Binary Tree Postorder Traversal
Дан корень бинарного дерева, верните обход значений узлов в постпорядке.
Пример:
Input: root = [1,null,2,3] Output: [3,2,1]👨💻 Алгоритм: 1️⃣Заполнение стека по стратегии право->узел->лево: Инициируйте стек и добавьте в него корень дерева. Перед тем как положить узел в стек, сначала добавьте его правого потомка, затем сам узел, а после — левого потомка. Это обеспечит последовательное извлечение узлов из стека в нужном порядке для постпорядкового обхода. 2️⃣Извлечение узла из стека и проверка: Извлекайте последний узел из стека, проверяя, является ли он левым листом (узел без потомков). Если это так, добавьте значение узла в выходной список (массив значений). Если узел имеет потомков, продолжайте выполнение стека с добавлением дочерних узлов по той же стратегии. 3️⃣Повторение процесса до опустошения стека: Если извлеченный узел не является левым листом, необходимо обработать его потомков. Для этого, верните узел и его потомков в стек в правильном порядке, чтобы следующие итерации могли корректно обработать все узлы. Повторяйте процесс до тех пор, пока стек не опустеет, что означает завершение обхода всех узлов. 😎 Решение:
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> output;
stack<TreeNode*> stack;
if (root == NULL) return output;
stack.push(root);
while (!stack.empty()) {
root = stack.top();
stack.pop();
output.push_back(root->val);
if (root->left != NULL) stack.push(root->left);
if (root->right != NULL) stack.push(root->right);
}
reverse(output.begin(), output.end());
return output;
}
};3 202
#easy
Задача: 144. Binary Tree Preorder Traversal
Дан корень бинарного дерева, верните предварительный обход значений его узлов.
Пример:
Input: root = [1,null,2,3] Output: [1,2,3]👨💻 Алгоритм: 1️⃣Определение структуры узла дерева: Определите класс TreeNode, который будет использоваться в реализации. Каждый узел TreeNode содержит значение и ссылки на левого и правого потомков. 2️⃣Инициализация процесса обхода: Начните обход с корневого узла дерева. Используйте стек для хранения узлов дерева, которые нужно обойти, начиная с корня. 3️⃣Итеративный обход дерева: На каждой итерации извлекайте текущий узел из стека и добавляйте его значение в выходной список. Сначала добавьте в стек правого потомка (если он существует), затем левого потомка (если он существует). Это гарантирует, что узлы будут обрабатываться в порядке слева направо, так как стек работает по принципу LIFO (последний пришел - первый ушел). Повторяйте процесс, пока стек не опустеет, что означает завершение обхода всех узлов. 😎 Решение:
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
if (root == nullptr) {
return vector<int>();
}
vector<TreeNode*> stack = {root};
vector<int> output;
while (!stack.empty()) {
root = stack.back();
stack.pop_back();
if (root != nullptr) {
output.push_back(root->val);
if (root->right != nullptr) {
stack.push_back(root->right);
}
if (root->left != nullptr) {
stack.push_back(root->left);
}
}
}
return output;
}
};3 202
#medium
Задача: 143. Reorder List
Вам дана голова односвязного списка. Список можно представить в следующем виде:
L0 → L1 → … → Ln - 1 → Ln
Переупорядочите список так, чтобы он принял следующую форму:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
Вы не можете изменять значения в узлах списка. Можно изменять только сами узлы.
Пример:
Input: head = [1,2,3,4] Output: [1,4,2,3]👨💻 Алгоритм: 1️⃣Нахождение середины списка и разделение его на две части: Используйте два указателя, slow и fast, для нахождения середины списка. Указатель slow движется на один узел за шаг, а fast — на два узла. Когда fast достигает конца списка, slow окажется в середине. Разделите список на две части. Первая часть начинается от головы списка до slow, вторая — с узла после slow до конца списка. 2️⃣Реверс второй половины списка: Инициализируйте указатели prev как NULL и curr как slow. Перемещайтесь по второй половине списка и меняйте направление ссылок между узлами для реверсирования списка. Продолжайте, пока не перестроите весь второй сегмент, теперь последний элемент первой части списка будет указывать на NULL, а prev станет новой головой второй половины списка. 3️⃣Слияние двух частей списка в заданном порядке: Начните с головы первой части списка (first) и головы реверсированной второй части (second). Перекрестно связывайте узлы из первой и второй части, вставляя узлы из второй части между узлами первой части. Передвигайте указатели first и second соответственно после каждой вставки. Продолжайте этот процесс до тех пор, пока узлы второй части не закончатся. 😎 Решение:
class Solution {
public:
void reorderList(ListNode* head) {
if (head == NULL) return;
ListNode* slow = head;
ListNode* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* prev = NULL;
ListNode* curr = slow;
ListNode* tmp;
while (curr != NULL) {
tmp = curr->next;
curr->next = prev;
prev = curr;
curr = tmp;
}
ListNode* first = head;
ListNode* second = prev;
while (second->next != NULL) {
tmp = first->next;
first->next = second;
first = tmp;
tmp = second->next;
second->next = first;
second = tmp;
}
}
};3 202
#medium
Задача: 142. Linked List Cycle II
Дана голова связного списка. Верните узел, с которого начинается цикл. Если цикла нет, верните null.
Цикл в связном списке существует, если есть такой узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла (индексация с нуля). Она равна -1, если цикла нет. Обратите внимание, что pos не передается в качестве параметра.
Не модифицируйте связный список.
Пример:
Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node.👨💻 Алгоритм: 1️⃣Инициализация и начало обхода: Инициализируйте узел указателем на голову связного списка и создайте пустое множество nodes_seen для отслеживания посещенных узлов. Начните обход со связного списка, перемещая узел на один шаг за раз. 2️⃣Проверка на наличие узла в множестве: Для каждого посещенного узла проверьте, содержится ли он уже в множестве nodes_seen. Если узел найден в множестве, это означает, что был найден цикл. Верните текущий узел как точку входа в цикл. 3️⃣Добавление узла в множество или завершение обхода: Если узел не найден в nodes_seen, добавьте его в множество и перейдите к следующему узлу. Если узел становится равным null (конец списка), верните null. В списке нет цикла, так как в случае наличия цикла вы бы застряли в петле и не достигли бы конца списка. 😎 Решение:
class Solution {
public:
ListNode* detectCycle(ListNode* head) {
unordered_set<ListNode*> nodesSeen;
ListNode* node = head;
while (node != nullptr) {
if (nodesSeen.find(node) != nodesSeen.end()) {
return node;
} else {
nodesSeen.insert(node);
node = node->next;
}
}
return nullptr;
}
};3 202
#easy
Задача: 141. Linked List Cycle
Дана переменная head, которая является началом связного списка. Определите, содержит ли связный список цикл.
Цикл в связном списке существует, если существует узел в списке, до которого можно добраться снова, последовательно следуя по указателю next. Внутренне переменная pos используется для обозначения индекса узла, к которому подключен указатель next последнего узла. Обратите внимание, что pos не передается в качестве параметра.
Верните true, если в связном списке есть цикл. В противном случае верните false.
Пример:
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).👨💻 Алгоритм: 1️⃣Инициализация структуры данных: Создайте хеш-таблицу (или множество) для хранения ссылок на узлы, чтобы отслеживать уже посещённые узлы. 2️⃣Обход списка: Перемещайтесь по связному списку, начиная с головы (head), и проверяйте каждый узел по очереди. 3️⃣Проверка на цикл: Если текущий узел равен null, это означает, что вы достигли конца списка, и список не имеет циклов. В этом случае верните false. Если текущий узел уже содержится в хеш-таблице, это означает, что вы вернулись к ранее посещённому узлу, и, следовательно, в списке присутствует цикл. Верните true. Если ни одно из этих условий не выполнено, добавьте текущий узел в хеш-таблицу и продолжите обход списка. 😎 Решение:
class Solution {
public:
bool hasCycle(ListNode *head) {
std::unordered_set<ListNode *> nodesSeen;
ListNode *current = head;
while (current != nullptr) {
if (nodesSeen.find(current) != nodesSeen.end()) {
return true;
}
nodesSeen.insert(current);
current = current->next;
}
return false;
}
};3 202
👨💻 Джун: Слушай, вот стажировку я прошел, где теперь можно чекнуть вакансии на работу?
🍷 Мидл: Ооо, тебе помогут ребята с канала Джун работает
💯 Карьеру нужно начинать с хорошими работодателями. Твое резюме будет ликовать, ведь контент выходит каждый день, работа ждет тебя, мой друг!
😏 Не упускай возможность и подписывайся, чтобы не потерять
3 202
#hard
Задача: 140. Word Break II
Дана строка s и словарь строк wordDict. Добавьте пробелы в строку s, чтобы построить предложение, в котором каждое слово является допустимым словом из словаря. Верните все такие возможные предложения в любом порядке.
Обратите внимание, что одно и то же слово из словаря может использоваться несколько раз при разделении.
Пример:
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"] Output: ["cats and dog","cat sand dog"]👨💻 Алгоритм: 1️⃣Инициализация и начальный вызов: Преобразуйте массив wordDict в множество wordSet для эффективного поиска. Инициализируйте пустой массив results для хранения допустимых предложений. Инициализируйте пустую строку currentSentence для отслеживания конструируемого предложения. Вызовите функцию backtrack с исходной строкой s, множеством wordSet, текущим предложением currentSentence, массивом результатов results и начальным индексом, установленным в 0 — начало входной строки. Верните results после завершения работы backtrack. 2️⃣Функция backtrack: Базовый случай: Если startIndex равен длине строки, добавьте currentSentence в results и вернитесь, так как это означает, что currentSentence представляет собой допустимое предложение. Итерация по возможным значениям endIndex от startIndex + 1 до конца строки. 3️⃣Обработка и рекурсия: Извлеките подстроку word от startIndex до endIndex - 1. Если word найдено в wordSet: Сохраните текущее значение currentSentence в originalSentence. Добавьте word к currentSentence (с пробелом, если это необходимо). Рекурсивно вызовите backtrack с обновленным currentSentence и endIndex. Сбросьте currentSentence к его исходному значению (originalSentence) для отката и попробуйте следующий endIndex. Вернитесь из функции backtrack. 😎 Решение:
class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
vector<string> results;
string currentSentence;
backtrack(s, wordSet, currentSentence, results, 0);
return results;
}
private:
void backtrack(const string& s, const unordered_set<string>& wordSet,
string& currentSentence, vector<string>& results,
int startIndex) {
if (startIndex == s.length()) {
results.push_back(currentSentence);
return;
}
for (int endIndex = startIndex + 1; endIndex <= s.length(); ++endIndex) {
string word = s.substr(startIndex, endIndex - startIndex);
if (wordSet.find(word) != wordSet.end()) {
string originalSentence = currentSentence;
if (!currentSentence.empty()) currentSentence += " ";
currentSentence += word;
backtrack(s, wordSet, currentSentence, results, endIndex);
currentSentence = originalSentence;
}
}
}
};3 202
📕 Прогер, как ты расширяешь свой кругозор в сфере IT?
Не достаточно знать что-то одно, мысля глобально и изучая смежные отрасли, ты не только становишься умнее, но и увеличиваешь свою востребованность и свой заработок.
🗿 Не обязательно читать заумные книги и смотреть подкасты - это долго.
У нас есть решение:
🔥 Полезные статьи - концентрат знаний.
🔥 Советы - короткие сообщения, которые будут увеличивать твою эффективность.
🔥 Инструменты - tool-сайты в разы упростят и ускорят твою работу.
🧑💻 Время, силы, желание - ресурсы, которые нужно использовать с умом. Подпишись на канал Заметки прогера, IT ниша скажет "спасибо" за такого специалиста.
3 202
#medium
Задача: 139. Word Break
Дана строка s и словарь строк wordDict. Верните true, если строку s можно разделить на последовательность одного или нескольких слов из словаря, разделённых пробелами.
Обратите внимание, что одно и то же слово из словаря может использоваться несколько раз при разделении.
Пример:
Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".👨💻 Алгоритм: 1️⃣Инициализация структур данных: Преобразуйте wordDict в множество words для быстрой проверки вхождения. Инициализируйте очередь queue начальным значением 0 (индекс начала строки) и множество seen для отслеживания посещённых индексов. 2️⃣Обход в ширину (BFS): Пока очередь не пуста, извлекайте первый элемент из очереди, обозначающий начальную позицию start. Если start равен длине строки s, возвращайте true, так как достигнут конец строки, и строку можно разделить на слова из словаря. Итерируйте end от start + 1 до s.length включительно. Для каждого end, проверьте, посещён ли он уже. 3️⃣Проверка подстроки и обновление структур: Проверьте подстроку начиная с start и заканчивая перед end. Если подстрока находится в множестве words, добавьте end в очередь и отметьте его в seen как посещённый. Если BFS завершается и конечный узел не достигнут, возвращайте false. 😎 Решение:
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> words(wordDict.begin(), wordDict.end());
queue<int> queue;
vector<bool> seen(s.length(), false);
queue.push(0);
while (!queue.empty()) {
int start = queue.front();
queue.pop();
if (start == s.length()) {
return true;
}
for (int end = start + 1; end <= s.length(); end++) {
if (seen[end]) {
continue;
}
if (words.find(s.substr(start, end - start)) != words.end()) {
queue.push(end);
seen[end] = true;
}
}
}
return false;
}
};3 202
😭 Джун: Как мне найти работу в IT, если опыта нет?
🧑💻 Мидл: Просто зайди на канал Джун стажер и подбери стажировку по душе.
📕 Админы отбирают самые сочные вакансии от ведущих компаний, к тому же контент выходит каждый день.
🔥 Не упускай возможность и подписывайся, чтобы не потерять
3 202
#medium
Задача: 138. Copy List with Random Pointer
Дан связный список длиной n, в котором каждый узел содержит дополнительный случайный указатель (random pointer), который может указывать на любой узел в списке или быть равным null.
Создайте глубокую копию списка. Глубокая копия должна состоять из ровно n совершенно новых узлов, где каждый новый узел имеет значение, равное значению соответствующего оригинального узла. Указатели next и random новых узлов должны указывать на новые узлы в скопированном списке таким образом, чтобы указатели в оригинальном и скопированном списке представляли одно и то же состояние списка. Ни один из указателей в новом списке не должен указывать на узлы в оригинальном списке.
Например, если в оригинальном списке есть два узла X и Y, где X.random --> Y, то для соответствующих узлов x и y в скопированном списке, x.random должен указывать на y.
Верните голову скопированного связного списка.
Связный список представлен во входных/выходных данных как список из n узлов. Каждый узел представлен парой [val, random_index], где:
val: целое число, представляющее Node.val
random_index: индекс узла (в диапазоне от 0 до n-1), на который указывает случайный указатель, или null, если он не указывает ни на какой узел.
Вашему коду будет дана только голова оригинального связного списка.
Пример:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]👨💻 Алгоритм: 1️⃣Инициализация и начало обхода: Начните обход графа со стартового узла (head). Создайте словарь visited_dictionary для отслеживания посещенных и клонированных узлов. 2️⃣Проверка и клонирование узлов: Для каждого текущего узла (current_node) проверьте, есть ли уже клонированная копия в visited_dictionary. Если клонированная копия существует, используйте ссылку на этот клонированный узел. Если клонированной копии нет, создайте новый узел (cloned_node_for_current_node), инициализируйте его и добавьте в visited_dictionary, где ключом будет current_node, а значением — созданный клон. 3️⃣Рекурсивные вызовы для обработки связей: Сделайте два рекурсивных вызова для каждого узла: один используя указатель random, другой — указатель next. Эти вызовы отражают обработку "детей" текущего узла в терминах графа, где детьми являются узлы, на которые указывают указатели random и next. 😎 Решение:
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val, Node* _next, Node* _random) {
val = _val;
next = _next;
random = _random;
}
};
class Solution {
private:
unordered_map<Node*, Node*> visitedHash;
public:
Node* copyRandomList(Node* head) {
if (head == NULL) {
return NULL;
}
if (this->visitedHash.find(head) != this->visitedHash.end()) {
return this->visitedHash[head];
}
Node* node = new Node(head->val, NULL, NULL);
this->visitedHash[head] = node;
node->next = this->copyRandomList(head->next);
node->random = this->copyRandomList(head->random);
return node;
}
};3 202
👨💻 Будущий специалист, ты знаешь, какая самая частая ошибка новичка в сфере IT?
Отсутствие практики убивает в тебе потенциал
✈️ Как с этим бороться, мой друг?
Найди работу и прокачивай свои скилы на конкретных задачах
🔥 У нас ты будешь находить большое количество вакансий каждый день. Понятие работы перестанет быть для тебя размытым.
Подпишись на канал и не откладывай свой прогресс в долгий ящик.
3 202
#medium
Задача: 137. Single Number II
Дан массив целых чисел nums, в котором каждый элемент встречается три раза, кроме одного, который встречается ровно один раз. Найдите этот единственный элемент и верните его.
Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.
Пример:
Input: nums = [2,2,3,2] Output: 3👨💻 Алгоритм: 1️⃣Сортировка массива: Отсортируйте массив nums. Это упорядочит все элементы так, чтобы одинаковые числа находились рядом. 2️⃣Итерация с проверкой: Используйте цикл for для перебора элементов массива от начала до nums.size() - 2 с шагом 3. Таким образом, каждый проверяемый индекс будет иметь следующий за ним индекс в пределах массива. Если элемент на текущем индексе совпадает с элементом на следующем индексе (проверка nums[i] == nums[i + 1]), продолжайте следующую итерацию цикла. 3️⃣Возврат уникального элемента: Если элемент на текущем индексе не совпадает с следующим, значит, это искомый уникальный элемент, который встречается только один раз. В этом случае возвращайте элемент на текущем индексе. Если до последнего элемента цикл не нашёл уникального элемента, возвращайте последний элемент массива nums[nums.size() - 1], поскольку он, очевидно, будет уникальным, если предыдущие проверки не выявили уникального элемента раньше. 😎 Решение:
class Solution {
public:
int singleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 1; i += 3) {
if (nums[i] == nums[i + 1]) {
continue;
} else {
return nums[i];
}
}
return nums[nums.size() - 1];
}
};3 202
🧑💻 Если твой английский позволяет ответить только на вопрос "Do you speak English", то с этим нужно что-то делать, будучи программистом.
🫤 Ты в курсе, что ...
- говорят по-английски — 20% из всех людей.
- Большое кол-во IT документации написано на английском.
Хочешь понимать код лучше? Изучи язык, который используется в его основе.
📕 На нашем канале ты постепенно будешь набираться опыта, в этом тебе помогут:
- Тесты для изучения английского: проверьте свои знания на практике.
- Английский через мемы: учите язык весело и с интересом.
- Шпаргалки для повторения: закрепите знания быстро и эффективно.
- Английский сленг программиста: станьте настоящим профи в коммуникации.
🔥 Маленький шаг в изучении иностранного откроет перед тобой большие возможности будущего специалиста и значительно повысит твое зп.
🌸 Подпишись, do it!
3 202
#easy
Задача: 136. Single Number
Дан непустой массив целых чисел nums, в котором каждый элемент встречается дважды, кроме одного. Найдите этот единственный элемент.
Вы должны реализовать решение с линейной сложностью выполнения и использовать только постоянное дополнительное пространство.
Пример:
Input: nums = [2,2,1] Output: 1👨💻 Алгоритм: 1️⃣Переберите все элементы в массиве nums. 2️⃣Если какое-то число в nums новое для массива, добавьте его. 3️⃣Если какое-то число уже есть в массиве, удалите его. 😎 Решение:
class Solution {
public:
int singleNumber(vector<int>& nums) {
vector<int> no_duplicate_list;
for (int i : nums) {
if (find(no_duplicate_list.begin(), no_duplicate_list.end(), i) ==
no_duplicate_list.end()) {
no_duplicate_list.push_back(i);
} else {
no_duplicate_list.erase(remove(no_duplicate_list.begin(),
no_duplicate_list.end(), i));
}
}
return no_duplicate_list[0];
}
};