C/C++ | LeetCode

#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]

👨‍💻 Алгоритм: 1️⃣Метод добавления узла в конец связного списка (add): Получите текущий узел в конце списка, это "реальный" хвост: tail.prev, обозначим его как previousEnd. Вставьте node после previousEnd, установив previousEnd.next = node. Настройте указатели узла: node.prev = previousEnd и node.next = tail. Обновите tail.prev = node, делая node новым "реальным" хвостом списка. 2️⃣Метод удаления узла из связного списка (remove): Узел node должен быть удален из списка. Для этого определите узлы nextNode = node.next и prevNode = node.prev. Чтобы удалить node, переназначьте prevNode.next = nextNode и nextNode.prev = prevNode, эффективно исключая node из списка. Это превратит, например, последовательность A <-> B <-> C в A <-> C, где prevNode = A и nextNode = C. 3️⃣Методы get и put: get(int key): Проверьте, существует ли ключ в хэш-карте. Если нет, верните -1. Иначе, получите узел, связанный с ключом, переместите его в конец списка с помощью remove(node) и add(node). Верните node.val. put(int key, int value): Если ключ уже существует, найдите соответствующий узел и удалите его методом remove. Создайте новый узел с key и value, добавьте его в хэш-карту и в конец списка методом add(node). Если размер кэша превышает установленную емкость после добавления, удалите самый редко используемый узел (который находится в голове списка после фиктивного узла head), затем удалите соответствующий ключ из хэш-карты. 😎 Решение:

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;
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

🤬 Постоянные ошибки, как они надоели! 🤯 Планируя свои дела, мы забываем, что оборудование может подвести. Это может перекрыть все рабочие планы. Придется гуглить, смотреть видосы, звонить знакомым "Не встречалась ли тебе такая ошибка?" 🥵 Все это время и силы. Наша команда нашла этому решение - Битый код. Канал, который даст тебе базу в мире ошибок. 🍸 Стань тем человеком, к которому будут обращаться и про которого будут говорить "Он сможет помочь"

#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;
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#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;
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#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;
        }
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#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;
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#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;
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

👨‍💻 Джун: Слушай, вот стажировку я прошел, где теперь можно чекнуть вакансии на работу? 🍷 Мидл: Ооо, тебе помогут ребята с канала Джун работает 💯 Карьеру нужно начинать с хорошими работодателями. Твое резюме будет ликовать, ведь контент выходит каждый день, работа ждет тебя, мой друг! 😏 Не упускай возможность и подписывайся, чтобы не потерять

#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;
            }
        }
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

📕 Прогер, как ты расширяешь свой кругозор в сфере IT? Не достаточно знать что-то одно, мысля глобально и изучая смежные отрасли, ты не только становишься умнее, но и увеличиваешь свою востребованность и свой заработок. 🗿 Не обязательно читать заумные книги и смотреть подкасты - это долго. У нас есть решение: 🔥 Полезные статьи - концентрат знаний. 🔥 Советы - короткие сообщения, которые будут увеличивать твою эффективность. 🔥 Инструменты - tool-сайты в разы упростят и ускорят твою работу. 🧑‍💻 Время, силы, желание - ресурсы, которые нужно использовать с умом. Подпишись на канал Заметки прогера, IT ниша скажет "спасибо" за такого специалиста.

#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;
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

😭 Джун: Как мне найти работу в IT, если опыта нет? 🧑‍💻 Мидл: Просто зайди на канал Джун стажер и подбери стажировку по душе. 📕 Админы отбирают самые сочные вакансии от ведущих компаний, к тому же контент выходит каждый день. 🔥 Не упускай возможность и подписывайся, чтобы не потерять

#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;
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

👨‍💻 Будущий специалист, ты знаешь, какая самая частая ошибка новичка в сфере IT? Отсутствие практики убивает в тебе потенциал ✈️ Как с этим бороться, мой друг? Найди работу и прокачивай свои скилы на конкретных задачах 🔥 У нас ты будешь находить большое количество вакансий каждый день. Понятие работы перестанет быть для тебя размытым. Подпишись на канал и не откладывай свой прогресс в долгий ящик.

#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];
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

🧑‍💻 Если твой английский позволяет ответить только на вопрос "Do you speak English", то с этим нужно что-то делать, будучи программистом. 🫤 Ты в курсе, что ... - говорят по-английски — 20% из всех людей. - Большое кол-во IT документации написано на английском. Хочешь понимать код лучше? Изучи язык, который используется в его основе. 📕 На нашем канале ты постепенно будешь набираться опыта, в этом тебе помогут: - Тесты для изучения английского: проверьте свои знания на практике. - Английский через мемы: учите язык весело и с интересом. - Шпаргалки для повторения: закрепите знания быстро и эффективно. - Английский сленг программиста: станьте настоящим профи в коммуникации. 🔥 Маленький шаг в изучении иностранного откроет перед тобой большие возможности будущего специалиста и значительно повысит твое зп. 🌸 Подпишись, do it!

#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];
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#hard Задача: 135. Candy В очереди стоят n детей. Каждому ребенку присвоено значение рейтинга, указанное в массиве целых чисел ratings. Вы раздаете конфеты этим детям с соблюдением следующих требований: Каждый ребенок должен получить как минимум одну конфету. Дети с более высоким рейтингом должны получать больше конфет, чем их соседи. Верните минимальное количество конфет, которое вам нужно иметь, чтобы распределить их среди детей. Пример:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

👨‍💻 Алгоритм: 1️⃣Инициализация и первичное заполнение массивов: Создайте два массива: left2right для расчета конфет с учетом только левых соседей и right2left для расчета с учетом только правых соседей. Изначально каждому ученику в обоих массивах присваивается по одной конфете. 2️⃣Обход и обновление значений в массивах: Проходите массив ratings слева направо, увеличивая значение в left2right для каждого ученика, чей рейтинг выше рейтинга его левого соседа. Затем проходите массив справа налево, увеличивая значение в right2left для каждого ученика, чей рейтинг выше рейтинга его правого соседа. 3️⃣Расчет минимального количества конфет: Для каждого ученика определите максимальное значение конфет между left2right[i] и right2left[i], чтобы соответствовать требованиям к распределению конфет. Суммируйте полученные значения для всех учеников, чтобы найти минимальное количество конфет, необходимое для соблюдения всех правил. 😎 Решение:

class Solution {
public:
    int candy(vector<int>& ratings) {
        int sum = 0;
        vector<int> left2right(ratings.size(), 1);
        vector<int> right2left(ratings.size(), 1);
        for (int i = 1; i < ratings.size(); i++) {
            if (ratings[i] > ratings[i - 1]) {
                left2right[i] = left2right[i - 1] + 1;
            }
        }
        for (int i = ratings.size() - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right2left[i] = right2left[i + 1] + 1;
            }
        }
        for (int i = 0; i < ratings.size(); i++) {
            sum += max(left2right[i], right2left[i]);
        }
        return sum;
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 134. Gas Station Вдоль кругового маршрута расположены n заправочных станций, на каждой из которых находится определённое количество топлива gas[i]. У вас есть автомобиль с неограниченным топливным баком, и для проезда от i-й станции к следующей (i + 1)-й станции требуется cost[i] топлива. Путешествие начинается с пустым баком на одной из заправочных станций. Учитывая два массива целых чисел gas и cost, верните индекс начальной заправочной станции, если вы можете проехать вокруг цепи один раз по часовой стрелке, в противном случае верните -1. Если решение существует, оно гарантированно будет уникальным. Пример:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

👨‍💻 Алгоритм: 1️⃣Инициализируйте переменные curr_gain, total_gain и answer значением 0. 2️⃣Пройдите по массивам gas и cost. Для каждого индекса i увеличивайте total_gain и curr_gain на gas[i] - cost[i]. Если curr_gain меньше 0, проверьте, может ли станция i + 1 быть начальной станцией: установите answer как i + 1, сбросьте curr_gain до 0 и повторите шаг 2. 3️⃣По завершении итерации, если total_gain меньше 0, верните -1. В противном случае верните answer. 😎 Решение:

#include <vector>
using namespace std;

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int currGain = 0, totalGain = 0, answer = 0;

        for (int i = 0; i < gas.size(); ++i) {
            totalGain += gas[i] - cost[i];
            currGain += gas[i] - cost[i];
            if (currGain < 0) {
                answer = i + 1;
                currGain = 0;
            }
        }

        return totalGain >= 0 ? answer : -1;
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#medium Задача: 133. Clone Graph Дана ссылка на узел в связанном неориентированном графе. Верните глубокую копию (клон) графа. Каждый узел в графе содержит значение (целое число) и список (List[Node]) своих соседей. Пример:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

👨‍💻 Алгоритм: 1️⃣Используйте хеш-таблицу для хранения ссылок на копии всех уже посещенных и скопированных узлов. Ключом будет узел оригинального графа, а значением — соответствующий клонированный узел клонированного графа. Хеш-таблица посещенных узлов также используется для предотвращения циклов. 2️⃣Добавьте первый узел в очередь, клонируйте его и добавьте в хеш-таблицу посещенных. 3️⃣Выполните обход в ширину (BFS): извлеките узел из начала очереди, посетите всех соседей этого узла. Если какой-либо сосед уже был посещен, получите его клон из хеш-таблицы посещенных; если нет, создайте клон и добавьте его в хеш-таблицу. Добавьте клоны соседей в список соседей клонированного узла. 😎 Решение:

#include <vector>
#include <deque>
#include <unordered_map>
using namespace std;

struct Node {
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (node == nullptr) {
            return node;
        }
        unordered_map<Node*, Node*> visited;
        deque<Node*> queue{node};
        visited[node] = new Node(node->val, {});
        while (!queue.empty()) {
            Node* n = queue.front();
            queue.pop_front();
            for (Node* neighbor : n->neighbors) {
                if (visited.find(neighbor) == visited.end()) {
                    visited[neighbor] = new Node(neighbor->val, {});
                    queue.push_back(neighbor);
                }
                visited[n]->neighbors.push_back(visited[neighbor]);
            }
        }
        return visited[node];
    }
};

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых