C/C++ | LeetCode

Получи грант до 1,2 млн руб. на обучение в магистратуре 4 офлайн программы, онлайн-магистратура по ML. Гранты до 1,2 млн руб. Стажировки, диплом гос. образца и фокус на твоей карьере в ЦУ Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 1245. Tree Diameter Сложность: medium Диаметр дерева - это количество ребер в самом длинном пути в этом дереве. Имеется неориентированное дерево из n узлов, помеченных от 0 до n - 1. Вам дан двумерный массив edges, где edges.length == n - 1 и edges[i] = [ai, bi] означает, что между узлами ai и bi в дереве есть неориентированное ребро. Верните диаметр дерева. Пример:

Input: edges = [[0,1],[0,2]]
Output: 2

👨‍💻 Алгоритм: 1⃣Построение графа: Используем представление графа в виде списка смежности. 2⃣Поиск самой удаленной вершины (DFS1): Запускаем DFS от произвольной вершины (например, 0) для нахождения самой удаленной вершины от нее. 3⃣Поиск диаметра (DFS2): Запускаем DFS от найденной на предыдущем шаге самой удаленной вершины и находим самую удаленную вершину от нее. Это расстояние и будет диаметром дерева.reset(playerId): Устанавливаем счет игрока в 0. 😎 Решение:

class Solution {
public:
    int treeDiameter(vector<vector<int>>& edges) {
        if (edges.empty()) return 0;

        unordered_map<int, vector<int>> graph;
        for (const auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        int farthest_node = 0;
        auto dfs = [&](int node, int parent) {
            int max_depth = 0;
            for (int neighbor : graph[node]) {
                if (neighbor != parent) {
                    int depth = dfs(neighbor, node);
                    if (depth + 1 > max_depth) {
                        max_depth = depth + 1;
                        farthest_node = neighbor;
                    }
                }
            }
            return max_depth;
        };

        dfs(0, -1);
        int start_node = farthest_node;

        dfs(start_node, -1);
        return dfs(farthest_node, -1);
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Онлайн-магистратура с IT специальностями от Яндекса Совместно с ИТМО, МИФИ, МФТИ. Онлайн-магистратура с актуальными программами и гибким графиком обучения. Получите высокооплачиваемую IT профессию, официальный диплом и практические знания. Господдержка оплаты. Совмещение с работой! Подать заявку #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 1404. Number of Steps to Reduce a Number in Binary Representation to One Сложность: medium Дано бинарное представление целого числа в виде строки s. Верните количество шагов, необходимых для его сокращения до 1 по следующим правилам: Если текущее число четное, его нужно разделить на 2. Если текущее число нечетное, нужно прибавить к нему 1. Гарантируется, что для всех тестовых случаев всегда можно достичь единицы. Пример:

Input: s = "1101"
Output: 6
Explanation: "1101" corressponds to number 13 in their decimal representation.
Step 1) 13 is odd, add 1 and obtain 14. 
Step 2) 14 is even, divide by 2 and obtain 7.
Step 3) 7 is odd, add 1 and obtain 8.
Step 4) 8 is even, divide by 2 and obtain 4.  
Step 5) 4 is even, divide by 2 and obtain 2. 
Step 6) 2 is even, divide by 2 and obtain 1.  

👨‍💻 Алгоритм: 1⃣Инициализируйте переменную operations значением 0. 2⃣Повторяйте операции, пока длина строки s больше 1: Если последний бит строки s равен 0, это означает, что число четное; примените операцию деления на 2, удалив последний бит. В противном случае это означает, что число, представленное строкой, нечетное; добавьте 1 к числу, изменив строку, чтобы выполнить эту операцию. 3⃣Верните количество операций. 😎 Решение:

class Solution {
public:
    int numSteps(string s) {
        int operations = 0;
        while (s.size() > 1) {
            if (s.back() == '0') {
                s.pop_back();
            } else {
                int i = s.size() - 1;
                while (i >= 0 && s[i] == '1') {
                    s[i] = '0';
                    i--;
                }
                if (i < 0) {
                    s.insert(s.begin(), '1');
                } else {
                    s[i] = '1';
                }
            }
            operations++;
        }
        return operations;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Баранкины и камни силы Смотрите на Кинопоиске с 7 августа. Семья таксистов обретает сверхсилы — и родственницу из XIX века. Фантастическая комедия с Андреем Федорцовым Узнать больше #реклама 16+ kinopoisk.ru О рекламодателе

Задача: 366. Find Leaves of Binary Tree Сложность: medium Дан корень бинарного дерева, соберите узлы дерева следующим образом: Соберите все листовые узлы. Удалите все листовые узлы. Повторяйте, пока дерево не станет пустым. Пример:

Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.

👨‍💻 Алгоритм: 1⃣Реализовать функцию getHeight(node), которая будет вычислять высоту каждого узла в дереве с использованием рекурсивного обхода в глубину (post-order). Если узел является null, вернуть -1. 2⃣Сохранить пары (высота, значение) для всех узлов и отсортировать их по высоте. 3⃣Организовать узлы по высоте и вернуть результат. 😎 Решение:

#include <vector>
#include <algorithm>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
    vector<pair<int, int>> pairs;

    int getHeight(TreeNode* node) {
        if (!node) return -1;
        int leftHeight = getHeight(node->left);
        int rightHeight = getHeight(node->right);
        int currHeight = max(leftHeight, rightHeight) + 1;
        pairs.push_back({currHeight, node->val});
        return currHeight;
    }

public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        getHeight(root);
        sort(pairs.begin(), pairs.end());
        vector<vector<int>> solution;
        int currentHeight = -1;
        for (const auto& p : pairs) {
            if (p.first != currentHeight) {
                solution.push_back(vector<int>());
                currentHeight = p.first;
            }
            solution.back().push_back(p.second);
        }
        return solution;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Регистрируйтесь на Yandex Ecom Open Air 8 августа Море инсайтов для бизнеса, музыкальный open-air, лекции и нетворкинг. Участие бесплатно! Зарегистрироваться #реклама 18+ ecomfest.ru О рекламодателе

⚡ Официальный релиз easyoffer 2.0 состоится уже в течение нескольких дней. Напоминаю, что в честь релиза запускаем акцию. Первые 500 покупателей получат: 🚀 Скидку 50% на PRO тариф на 1 год 🎁 Подарок ценностью 5000₽ для тех, кто подписан на этот канал 🔔 Подпишитесь на этот канал: https://t.me/+b2fZN17A9OQ3ZmJi В нем мы опубликуем сообщение о релизе в первую очередь

Задача: 846. Hand of Straights Сложность: medium У Алисы есть некоторое количество карт, и она хочет переставить карты в группы так, чтобы каждая группа была размером groupSize и состояла из groupSize последовательных карт. Дан целочисленный массив hand, где hand[i] — это значение, написанное на i-й карте, и целое число groupSize. Верните true, если она может переставить карты, или false в противном случае. Пример:

Input: hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
Output: true
Explanation: Alice's hand can be rearranged as [1,2,3],[2,3,4],[6,7,8]

👨‍💻 Алгоритм: 1⃣Проверьте, делится ли длина массива hand на groupSize. Если нет, верните false. 2⃣Создайте карту cardCount для хранения количества каждой карты в массиве hand. 3⃣Итерируйте по массиву hand и обновляйте карту cardCount. Затем итерируйте снова для создания групп: Найдите начальную карту startCard для потенциальной последовательности, уменьшая startCard, пока не найдёте карту, которая отсутствует в карте cardCount. Попробуйте сформировать последовательность из groupSize карт, начиная с startCard. Если какая-либо карта в потенциальной последовательности отсутствует в карте cardCount, верните false. Если последовательность можно сформировать, уменьшите количество каждой карты в последовательности в карте cardCount. 😎 Решение:

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

class Solution {
public:
    bool isNStraightHand(vector<int>& hand, int groupSize) {
        if (hand.size() % groupSize != 0) {
            return false;
        }

        unordered_map<int, int> cardCount;
        for (int card : hand) {
            cardCount[card]++;
        }

        sort(hand.begin(), hand.end());

        for (int card : hand) {
            if (cardCount[card] == 0) {
                continue;
            }

            for (int nextCard = card; nextCard < card + groupSize; nextCard++) {
                if (cardCount[nextCard] == 0) {
                    return false;
                }
                cardCount[nextCard]--;
            }
        }

        return true;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать

Задача: 204. Count Primes Сложность: medium Дано целое число n. Нужно вернуть количество простых чисел, которые строго меньше n. Пример:

Input: n = 10 Output: 4
Объяснение: простые числа: 2, 3, 5, 7

👨‍💻 Алгоритм: 1⃣Инициализируем булев массив numbers длиной n, где numbers[i] == true означает, что число i — потенциально простое. 2⃣Начинаем с p = 2 и до sqrt(n): – Если numbers[p] == true, обнуляем все кратные p, начиная с p * p. 3⃣После завершения прохода, все индексы, где numbers[i] == true (и i >= 2), являются простыми. 😎 Решение:

class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2) {
            return 0;
        }

        vector<bool> numbers(n, true);
        for (int p = 2; p <= sqrt(n); ++p) {
            if (numbers[p]) {
                for (int j = p * p; j < n; j += p) {
                    numbers[j] = false;
                }
            }
        }

        int numberOfPrimes = 0;
        for (int i = 2; i < n; i++) {
            if (numbers[i]) {
                ++numberOfPrimes;
            }
        }

        return numberOfPrimes;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Регистрируйтесь на Yandex Neuro Scale В этом году у конференции новое имя и фокус: главной темой становятся нейротехнологии. Мы покажем, как бизнес уже применяет сервисы и как создавать собственных AI-агентов с помощью инструментов нашей платформы. ✨Ждём вас на главной конференции Yandex Cloud!✨ Зарегистрироваться #реклама 16+ scale.yandex.cloud О рекламодателе Реклама на Яндексе

Задача: 281. Zigzag Iterator Сложность: medium Даны два вектора v1 и v2. Необходимо реализовать итератор, который будет поочередно возвращать элементы из этих двух векторов: сначала из первого, затем из второго и так далее. Пример:

Input: v1 = [1,2], v2 = [3,4,5,6]
Output: [1,3,2,4,5,6]

👨‍💻 Алгоритм 1⃣Инициализация Создаем структуру, которая будет хранить оба вектора и очередь индексов (номер вектора, индекс элемента). В очередь добавляются только непустые вектора. 2⃣Метод next() Извлекаем пару (номер вектора, индекс элемента), возвращаем соответствующее значение. Если в этом векторе есть еще элементы — добавляем следующую пару в очередь. 3⃣Метод hasNext() Просто проверяет, пуста ли очередь. Если нет — значит остались элементы. 😎 Решение

#include <vector>
#include <queue>
#include <utility>

class ZigzagIterator {
private:
    std::vector<std::vector<int>> vectors;
    std::queue<std::pair<int, int>> queue;

public:
    ZigzagIterator(std::vector<int>& v1, std::vector<int>& v2) {
        vectors.push_back(v1);
        vectors.push_back(v2);
        for (int i = 0; i < vectors.size(); ++i) {
            if (!vectors[i].empty()) {
                queue.push({i, 0});
            }
        }
    }

    int next() {
        auto [vecIndex, elemIndex] = queue.front();
        queue.pop();
        int nextElemIndex = elemIndex + 1;
        if (nextElemIndex < vectors[vecIndex].size()) {
            queue.push({vecIndex, nextElemIndex});
        }
        return vectors[vecIndex][elemIndex];
    }

    bool hasNext() {
        return !queue.empty();
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 92. Reverse Linked List II Сложность: medium Дан односвязный список и два числа left и right. Нужно перевернуть часть списка от позиции left до right (включительно) и вернуть изменённый список, сохранив остальные узлы нетронутыми. Пример:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

👨‍💻 Алгоритм: 1⃣Запускаем рекурсивную функцию recurseAndReverse, передавая указатель right (начинается с head), а также значения m и n — относительные позиции для переворота. 2⃣Перед каждым рекурсивным вызовом сдвигаем right = right->next, и если m > 1, то сдвигаем left = left->next. Таким образом, когда n == 1, left указывает на начало, а right — на конец подсписка. 3⃣Во время отката рекурсии — обмениваем значения в left и right, затем двигаем left = left->next. Останавливаем обмены, если указатели пересеклись (left == right) или пересекаются (right->next == left). 😎 Решение:

class Solution {
public:
    ListNode* left = nullptr;
    bool stop = false;

    void recurseAndReverse(ListNode* right, int m, int n) {
        if (n == 1) return;

        right = right->next;

        if (m > 1) this->left = this->left->next;

        recurseAndReverse(right, m - 1, n - 1);

        if (this->left == right || right->next == this->left) stop = true;

        if (!stop) {
            int t = this->left->val;
            this->left->val = right->val;
            right->val = t;
            this->left = this->left->next;
        }
    }

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        this->left = head;
        recurseAndReverse(head, m, n);
        return head;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Битрикс24 ускоряет работу команды. Вот как это работает Бесплатный онлайн-сервис для совместной работы заменяет десятки приложений. 📱Например, обсуждаете проект в чате. Тут же ставьте задачи, кидайте файлы и собирайте встречи — без переключения окон. Задачи сразу попадают в трекер, обсуждения превращаются в дела, а календарь сам напоминает о встречах. После созвонов AI подводит итоги и добавляет в тот же чат. Работайте бесшовно в Битрикс24, чтобы не терять время на переключения. 👌Коллеги, пользуемся Зарегистрироваться #реклама 16+ bitrix24.ru О рекламодателе

Задача: 989. Add to Array-Form of Integer Сложность: easy Массивная форма целого числа num - это массив, представляющий его цифры в порядке слева направо. Например, для num = 1321, массивная форма - это [1, 3, 2, 1]. Дано num в массивной форме целого числа и целое число k, верните массивную форму числа num + k. Пример:

Input: num = [1,2,0,0], k = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

👨‍💻 Алгоритм: 1⃣Инициализация переменных: Преобразуйте число k в массив его цифр и переверните оба массива (массив num и массив цифр k). Завести переменную carry для хранения переноса и инициализировать ее нулем. Создать пустой массив result для хранения результата. 2⃣Сложение массивов: Пройдите по элементам массивов num и цифр k, начиная с их конца, сложите соответствующие цифры вместе с переносом (carry). Если сумма больше 9, сохраните последнюю цифру в текущей позиции результата, а carry установите в 1. Если сумма меньше 10, установите carry в 0. Добавьте результат текущего сложения в массив result 3⃣Обработка оставшихся цифр и переноса: Если один из массивов закончился раньше, продолжайте сложение оставшихся цифр другого массива с переносом. Если после окончания всех сложений остается перенос (carry), добавьте его в начало массива result. Переверните массив result обратно и верните его. 😎 Решение:

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<int> addToArrayForm(std::vector<int>& num, int k) {
        std::vector<int> result;
        int n = num.size();
        
        for (int i = n - 1; i >= 0; i--) {
            k += num[i];
            result.push_back(k % 10);
            k /= 10;
        }
        while (k > 0) {
            result.push_back(k % 10);
            k /= 10;
        }
        std::reverse(result.begin(), result.end());
        return result;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Бесплатный 4-х дневный марафон по веб-дизайну "Just do design" ✅День 1 - Как зарабатывать на дизайне? ✅День 2 - Отрисовка концепта "Nike" ✅День 3 - Отрисовка дополнительных экранов концепта "Nike" ✅День 4 - Анимация концепта "Nike" Практический марафон по дизайну - легкий старт в профессию мечты. Вас ждут 4 урока, 4 домашних задания, персональный куратор-эксперт и обратная связь. Дойдите до конца марафона и пополните портфолио концептом «NIKE». Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

Задача: 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix Сложность: hard Дана бинарная матрица mat размером m x n. За один шаг вы можете выбрать одну ячейку и перевернуть её и всех её четырех соседей, если они существуют (Перевернуть означает изменить 1 на 0 и 0 на 1). Пара ячеек называется соседями, если они имеют общую границу. Верните минимальное количество шагов, необходимых для преобразования матрицы mat в нулевую матрицу или -1, если это невозможно. Бинарная матрица - это матрица, в которой все ячейки равны 0 или 1. Нулевая матрица - это матрица, в которой все ячейки равны 0. Пример:

Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.

👨‍💻 Алгоритм: 1⃣Переберите все возможные варианты решений для первой строки матрицы. Каждое решение представляется массивом, где каждый элемент равен 0 или 1, указывая, перевернут ли соответствующий элемент в первой строке. Инициализируйте два бинарных массива для каждой строки: lastState[], содержащий значения предыдущей строки, и changed[], представляющий, были ли значения в текущей строке перевернуты при работе с предыдущей строкой. 2⃣Для каждой строки в матрице используйте следующий шаг для вычисления состояния, инициализированного как changed: Для каждой позиции j в диапазоне [0, n - 1] текущей строки измените значение state[j] соответственно, если lastState[j] равно 1. Переверните state[j], state[j - 1] и state[j + 1], если они существуют. Увеличьте счетчик переворотов на 1. Значения, которые будут перевернуты в следующей строке, точно равны lastState, а решение для следующей строки точно равно массиву state. Поэтому установите changed = lastState и lastState = state, затем переходите к следующей строке. 3⃣После обработки всех строк проверьте, содержит ли lastState все нули, чтобы определить, является ли это допустимым решением. Верните минимальное количество переворотов для всех допустимых решений. 😎 Решение:

class Solution {
    int better(int x, int y) {
        return x < 0 || (y >= 0 && y < x) ? y : x;
    }

    int dfs(const vector<vector<int>>& mat, vector<int>& operations) {
        if (operations.size() == mat[0].size()) {
            vector<int> changed(mat[0].size());
            vector<int> last_state = operations;
            int maybe = 0;
            for (const vector<int>& row : mat) {
                vector<int> state = changed;
                for (int j = 0; j < row.size(); ++j) {
                    state[j] ^= row[j];
                    if (last_state[j]) {
                        state[j] ^= 1;
                        if (j) {
                            state[j - 1] ^= 1;
                        }
                        if (j + 1 < row.size()) {
                            state[j + 1] ^= 1;
                        }
                        ++maybe;
                    }
                }
                changed = last_state;
                last_state = state;
            }
            for (int x : last_state) {
                if (x) {
                    return -1;
                }
            }
            return maybe;
        }
        operations.push_back(0);
        const int maybe1 = dfs(mat, operations);
        operations.back() = 1;
        const int maybe2 = dfs(mat, operations);
        operations.pop_back();
        return better(maybe1, maybe2);
    }

public:
    int minFlips(vector<vector<int>>& mat) {
        vector<int> operations;
        return dfs(mat, operations);
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Мы ищем людей, которые хотят работать турагентом из дома 💰Оплата от 150.000 рублей в месяц Образование, место жительства, трудовой стаж — не важны! Подходит, как для подработки / декретного отпуска, так и для полной занятости. Если заинтересовались, то для старта нужно: — зарегистрироваться на сайте — пройти трехдневный курс На что можно рассчитывать: ✅ удаленная работа ✅ зп от 150.000 рублей (потолка нет) ✅ стабильная подработка, если не хотите уходить с основной работы Количество бесплатных мест ограничено. Успейте пройти тест и оставить заявку. ⚡ Набор заканчивается в понедельник! Зарегистрироваться #реклама интревел.рф О рекламодателе

Задача: 745. Prefix and Suffix Search Сложность: hard Создайте специальный словарь, в котором поиск слов осуществляется по префиксу и суффиксу. Реализуйте класс WordFilter: WordFilter(string[] words) Инициализирует объект со словами в словаре. f(string pref, string suff) Возвращает индекс слова в словаре, которое имеет префикс pref и суффикс suff. Если существует более одного допустимого индекса, возвращается наибольший из них. Если в словаре нет такого слова, возвращается -1. Пример:

Input: letters = ["c","f","j"], target = "a"
Output: "c"

👨‍💻 Алгоритм: 1⃣Сохраните слова и их индексы в словаре. 2⃣Создайте объединенные ключи, состоящие из префиксов и суффиксов для всех возможных комбинаций. 3⃣Реализуйте функцию поиска, которая ищет наибольший индекс слова по префиксу и суффиксу. 😎 Решение:

class WordFilter {
public:
    WordFilter(vector<string>& words) {
        for (int index = 0; index < words.size(); ++index) {
            string word = words[index];
            int length = word.length();
            for (int prefixLength = 1; prefixLength <= length; ++prefixLength) {
                for (int suffixLength = 1; suffixLength <= length; ++suffixLength) {
                    string prefix = word.substr(0, prefixLength);
                    string suffix = word.substr(length - suffixLength);
                    string key = prefix + "#" + suffix;
                    prefixSuffixMap[key] = index;
                }
            }
        }
    }
    
    int f(string pref, string suff) {
        string key = pref + "#" + suff;
        return prefixSuffixMap.count(key) ? prefixSuffixMap[key] : -1;
    }

private:
    unordered_map<string, int> prefixSuffixMap;
};

Ставь 👍 и забирай 📚 Базу знаний