C/C++ | LeetCode

#hard Задача: 239. Sliding Window Maximum Вам дан массив целых чисел nums. Существует скользящее окно размера k, которое перемещается с самого левого конца массива до самого правого. Вы можете видеть только k чисел в окне. Каждый раз скользящее окно перемещается вправо на одну позицию. Верните максимальные значения скользящего окна. Пример:

Input: nums = [1], k = 1
Output: [1]

👨‍💻 Алгоритм: 1⃣Инициализация и заполнение первой части окна: Создайте двустороннюю очередь dq для хранения индексов элементов и список res для хранения результатов. Пройдите по первым k элементам массива nums (от i = 0 до k - 1). Для каждого элемента: Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i]. Добавьте текущий индекс i в конец dq. Добавьте в res максимальный элемент первого окна, который находится в nums[dq[0]]. 2⃣Сканирование оставшейся части массива: Пройдите по оставшимся элементам массива nums (от i = k до n - 1). Для каждого элемента: Если индекс элемента на передней части dq равен i - k, удалите этот элемент из dq, так как он выходит за пределы текущего окна. Удалите из dq все элементы, которые меньше или равны текущему элементу nums[i]. Добавьте текущий индекс i в конец dq. Добавьте в res максимальный элемент текущего окна, который находится в nums[dq[0]]. 3⃣Возвращение результата: Верните список res, содержащий максимальные элементы для каждого скользящего окна. 😎 Решение:

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k){
        deque<int> dq;
        vector<int> res;
        for (int i = 0; i < k; i++) {
            while (!dq.empty() && nums[i] >= nums[dq.back()]) {
                dq.pop_back();
            }
            dq.push_back(i);
        }
        res.push_back(nums[dq.front()]);

        for (int i = k; i < nums.size(); i++) {
            if(dq.front() == i - k) {
                dq.pop_front();
            }
            while (!dq.empty() && nums[i] >= nums[dq.back()]) {
                dq.pop_back();
            }
            dq.push_back(i);
            res.push_back(nums[dq.front()]);
        }
        
        return res;
    }
};

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

#hard Задача: 527. Word Abbreviation Дано массив уникальных строк words, верните минимально возможные сокращения для каждого слова. Правила сокращения строки следующие: Первоначальное сокращение для каждого слова: первый символ, затем количество символов между первым и последним символом, затем последний символ. Если более одного слова имеют одинаковое сокращение, выполните следующее: Увеличьте префикс (символы в первой части) каждого из их сокращений на 1. Например, начнем с слов ["abcdef", "abndef"], оба изначально сокращены как "a4f". Последовательность операций будет следующей: ["a4f", "a4f"] -> ["ab3f", "ab3f"] -> ["abc2f", "abn2f"]. Эта операция повторяется до тех пор, пока каждое сокращение не станет уникальным. В конце, если сокращение не сделало слово короче, оставьте его в исходном виде. Пример:

Input: words = ["like","god","internal","me","internet","interval","intension","face","intrusion"]
Output: ["l2e","god","internal","me","i6t","interval","inte4n","f2e","intr4n"]

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

class Solution {
public:
    vector<string> wordsAbbreviation(vector<string>& words) {
        int n = words.size();
        vector<string> ans(n);
        vector<int> prefix(n, 0);

        for (int i = 0; i < n; ++i)
            ans[i] = abbrev(words[i], 0);

        for (int i = 0; i < n; ++i) {
            while (true) {
                unordered_set<int> dupes;
                for (int j = i + 1; j < n; ++j) {
                    if (ans[i] == ans[j])
                        dupes.insert(j);
                }

                if (dupes.empty()) break;
                dupes.insert(i);
                for (int k : dupes) {
                    ans[k] = abbrev(words[k], ++prefix[k]);
                }
            }
        }

        return ans;
    }

private:
    string abbrev(const string& word, int i) {
        int n = word.size();
        if (n - i <= 3) return word;
        return word.substr(0, i + 1) + to_string(n - i - 2) + word.back();
    }
};

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

#medium Задача: 238. Product of Array Except Self Дан массив целых чисел nums, верните массив answer такой, что answer[i] равен произведению всех элементов массива nums, кроме nums[i]. Произведение любого префикса или суффикса массива nums гарантированно помещается в 32-битное целое число. Вы должны написать алгоритм, который работает за время O(n) и не использует операцию деления. Пример:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

👨‍💻 Алгоритм: 1⃣Инициализация массивов L и R: Инициализируйте два пустых массива L и R. Массив L будет содержать произведение всех чисел слева от i, а массив R будет содержать произведение всех чисел справа от i. Заполните массив L, установив L[0] равным 1, а для остальных элементов используйте формулу L[i] = L[i-1] * nums[i-1]. Заполните массив R, установив R[length-1] равным 1, а для остальных элементов используйте формулу R[i] = R[i+1] * nums[i+1]. 2⃣Заполнение массивов L и R: Пройдите два цикла для заполнения массивов L и R. В первом цикле заполните массив L, начиная с L[0] и двигаясь вправо. Во втором цикле заполните массив R, начиная с R[length-1] и двигаясь влево. 3⃣Формирование результата: Пройдите по исходному массиву и для каждого элемента i вычислите произведение всех элементов, кроме nums[i], используя L[i] * R[i]. Сохраните результат в массиве answer и верните его. 😎 Решение:

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int length = nums.size();
        vector<int> L(length), R(length), answer(length);

        L[0] = 1;
        for (int i = 1; i < length; i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }

        R[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--) {
            R[i] = nums[i + 1] * R[i + 1];
        }

        for (int i = 0; i < length; i++) {
            answer[i] = L[i] * R[i];
        }

        return answer;
    }
};

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

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

#medium Задача: 526. Beautiful Arrangement Предположим, у вас есть n целых чисел, пронумерованных от 1 до n. Перестановка этих n целых чисел perm (нумерация с 1) считается красивой, если для каждого i (1 <= i <= n) выполняется одно из следующих условий: perm[i] делится на i. i делится на perm[i]. Дано целое число n, верните количество красивых перестановок, которые вы можете создать. Пример:

Input: n = 2
Output: 2
Explanation: 
The first beautiful arrangement is [1,2]:
    - perm[1] = 1 is divisible by i = 1
    - perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
    - perm[1] = 2 is divisible by i = 1
    - i = 2 is divisible by perm[2] = 1

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

class Solution {
public:
    int count = 0;
    
    int countArrangement(int N) {
        vector<int> nums(N);
        iota(nums.begin(), nums.end(), 1);
        permute(nums, 0);
        return count;
    }
    
    void permute(vector<int>& nums, int l) {
        if (l == nums.size()) {
            count++;
        }
        for (int i = l; i < nums.size(); ++i) {
            swap(nums[i], nums[l]);
            if (nums[l] % (l + 1) == 0 || (l + 1) % nums[l] == 0) {
                permute(nums, l + 1);
            }
            swap(nums[i], nums[l]);
        }
    }
};

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

YADRO приглашает Software Engineer на SPRINT OFFER 🔍 Компания-лидер инженерной индустрии в России YADRO проводит SPRINT OFFER для Software Engineer в двух направлениях — Linux-based и Android. 🔵 Оффер в команду KVADRA, которая разрабатывает собственную операционную систему kvadraOS, можно получить всего за 3 дня! → На направлении Linux-based вам предстоит адаптировать исходный код Chromium для компьютеров и ноутбуков с нашими аппаратными платформами и вносить изменения в поведение устройств, учитывая продуктовые требования. → На направлении Android вы будете заниматься подготовкой unit-тестов своего кода. Разрабатывать собственные и адаптировать чужие приложения, если они входят в базовую поставку ОС. Чтобы принять участие, до 24 ноября подайте заявку на сайте. Станьте частью YADRO!

#hard Задача: 381. Insert Delete GetRandom O(1) - Duplicates allowed RandomizedCollection — это структура данных, содержащая набор чисел, возможно с дубликатами (т.е. мультимножество). Она должна поддерживать вставку и удаление определенных элементов, а также предоставление случайного элемента. Реализуйте класс RandomizedCollection: RandomizedCollection(): Инициализирует пустой объект RandomizedCollection. bool insert(int val): Вставляет элемент val в мультимножество, даже если элемент уже присутствует. Возвращает true, если элемента не было, и false в противном случае. bool remove(int val): Удаляет элемент val из мультимножества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае. Если у val несколько вхождений в мультимножестве, удаляется только одно из них. int getRandom(): Возвращает случайный элемент из текущего мультимножества. Вероятность возврата каждого элемента пропорциональна числу вхождений этого элемента в мультимножество. Реализуйте функции класса так, чтобы каждая функция работала в среднем за O(1) времени. Пример:

Input
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []]
Output
[null, true, false, true, 2, true, 1]

👨‍💻 Алгоритм: 1⃣Создать словарь для хранения значений и их индексов в списке, а также список для хранения всех элементов мультимножества. 2⃣Метод insert(val): Добавить значение в конец списка и обновить словарь, добавив индекс этого значения. Возвращать true, если значение отсутствовало ранее, и false в противном случае. Метод remove(val): Удалить одно вхождение значения из словаря и списка. Для удаления значения заменить его последним элементом списка и обновить словарь. Возвращать true, если значение присутствовало, и false в противном случае. 3⃣Метод getRandom(): Возвращать случайный элемент из списка, обеспечивая равновероятное распределение на основе количества вхождений каждого элемента. 😎 Решение:

using namespace std;

class RandomizedCollection {
public:
    RandomizedCollection() {}

    bool insert(int val) {
        bool exists = dict.find(val) != dict.end();
        if (!exists) {
            dict[val] = unordered_set<int>();
        }
        dict[val].insert(list.size());
        list.push_back(val);
        return !exists;
    }

    bool remove(int val) {
        if (dict.find(val) == dict.end() || dict[val].empty()) {
            return false;
        }
        int index = *dict[val].begin();
        dict[val].erase(index);
        int lastElement = list.back();
        list[index] = lastElement;
        dict[lastElement].insert(index);
        dict[lastElement].erase(list.size() - 1);
        list.pop_back();
        if (dict[val].empty()) {
            dict.erase(val);
        }
        return true;
    }

    int getRandom() {
        int randomIndex = rand() % list.size();
        return list[randomIndex];
    }

private:
    unordered_map<int, unordered_set<int>> dict;
    vector<int> list;
};

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

Откройте подписку на Кинопоиск и Музыку за 1₽ Ответьте на 1 вопрос и получите в подарок доступ к Кинопоиску, Музыке и Книгам на 60 дней за 1 рубль ✨ Сервисы будут доступны не только для Вас, но и для трёх ваших близких Попробовать #реклама 18+ kinopoisk.ru О рекламодателе

#medium Задача: 237. Delete Node in a Linked List Дан односвязный список с головой head, и требуется удалить узел node в этом списке. Вам дан узел node, который нужно удалить. У вас нет доступа к первому узлу head. Все значения в односвязном списке уникальны, и гарантируется, что данный узел node не является последним узлом в списке. Удалите данный узел. Обратите внимание, что под удалением узла мы не подразумеваем его удаление из памяти. Мы имеем в виду: - Значение данного узла не должно существовать в односвязном списке. - Количество узлов в односвязном списке должно уменьшиться на один. - Все значения перед узлом должны оставаться в том же порядке. - Все значения после узла должны оставаться в том же порядке. Пример:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

👨‍💻 Алгоритм: 1⃣Копирование данных: Скопируйте значение из следующего узла (node.next) в текущий узел (node). Таким образом, текущий узел будет иметь значение, которое было в следующем узле. 2⃣Обновление указателя: Обновите указатель next текущего узла, чтобы он ссылался на узел, следующий за узлом node.next. Это effectively удалит следующий узел из списка. 3⃣Удаление ссылки на следующий узел: Убедитесь, что следующий узел больше не ссылается на другие узлы, тем самым полностью исключая его из списка. 😎 Решение:

class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

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

#medium Задача: 339. Nested List Weight Sum Вам дан вложенный список целых чисел nestedList. Каждый элемент либо целое число, либо список, элементы которого также могут быть целыми числами или другими списками. Глубина целого числа — это количество списков, в которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значения каждого целого числа, установленные в его глубину. Верните сумму каждого целого числа в nestedList, умноженного на его глубину. Пример:

Input: nestedList = [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.

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

class Solution {
public:
    int depthSum(vector<NestedInteger>& nestedList) {
        return dfs(nestedList, 1);
    }
    
private:
    int dfs(const vector<NestedInteger>& list, int depth) {
        int total = 0;
        for (const auto& nested : list) {
            if (nested.isInteger()) {
                total += nested.getInteger() * depth;
            } else {
                total += dfs(nested.getList(), depth + 1);
            }
        }
        return total;
    }
};

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

Обучение на Frontend-разработчика. С нуля за 9 месяцев. На курсе вы получите все навыки, необходимые для старта в профессии Frontend-разработчика. Персональный наставник middle/senior уровня. 14 проектов, лайвкодинг, хакатоны, репетиции техсобеседования. Освоите JavaScript, React, TypeScript Официальный диплом и сертификат школы. Поддержка наставника по JS в течение 3-х месяцев после диплома. Гарантия трудоустройства. Если вы не устроитесь, вернём деньги. Это закреплено в договоре п. 6.14 С 9 по 30 ноября 2024 г. скидка 40% на все программы Result School Узнать больше #реклама 16+ result.school О рекламодателе

#medium Задача: 380. Insert Delete GetRandom O(1) Реализуйте класс RandomizedSet: RandomizedSet(): Инициализирует объект RandomizedSet. bool insert(int val): Вставляет элемент val в множество, если его там нет. Возвращает true, если элемент отсутствовал, и false в противном случае. bool remove(int val): Удаляет элемент val из множества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае. int getRandom(): Возвращает случайный элемент из текущего множества элементов (гарантируется, что по крайней мере один элемент существует при вызове этого метода). Каждый элемент должен иметь равную вероятность быть возвращенным. Вы должны реализовать функции класса таким образом, чтобы каждая функция работала в среднем за O(1) по времени. Пример:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

👨‍💻 Алгоритм: 1⃣Создать словарь для хранения значений и их индексов, а также список для хранения значений. 2⃣Метод insert(val): Проверить наличие значения в словаре. Если отсутствует, добавить значение в список и обновить словарь с новым индексом. Метод remove(val): Проверить наличие значения в словаре. Если присутствует, заменить удаляемое значение последним элементом списка, обновить его индекс в словаре, удалить последний элемент из списка и удалить значение из словаря. 3⃣Метод getRandom(): Возвращать случайный элемент из списка, используя встроенную функцию генерации случайных чисел. 😎 Решение:

using namespace std;

class RandomizedSet {
public:
    RandomizedSet() {}

    bool insert(int val) {
        if (dict.find(val) != dict.end()) {
            return false;
        }
        dict[val] = list.size();
        list.push_back(val);
        return true;
    }

    bool remove(int val) {
        if (dict.find(val) == dict.end()) {
            return false;
        }
        int index = dict[val];
        int lastElement = list.back();
        list[index] = lastElement;
        dict[lastElement] = index;
        list.pop_back();
        dict.erase(val);
        return true;
    }

    int getRandom() {
        int randomIndex = rand() % list.size();
        return list[randomIndex];
    }

private:
    unordered_map<int, int> dict;
    vector<int> list;
};

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

Приглашаем на митап для бэкенд-разработчиков от Еком-сервисов Яндекса В Минск приехал Яндекс Foodtech Tour — серия митапов в столицах, на которых эксперты Еды, Лавки и Маркета рассказывают о внутренней кухне разработки сервисов. В Минске спикеры расскажут о core-технологиях, которые лежат в основе работы продуктов. Митап пройдет 7 декабря.  Программа насыщенная:  👉Доклады о BDUI и ускорении разработки. Никита Шумский из Еды расскажет об особенной инфраструктуры Еды, различиях классического и мобильного бэкенда и преимуществах BDUI. Ваня Ходор из Лавки поделится кейсом ускорения разработки, причем не скорости работы кода, а его написания. 👉CaseLab о мультизаказе в Еде. Это интерактивный формат, в котором участники разбирают реальный кейс из работы сервиса, предлагают решение и получают фидбек от экспертов Яндекса. 👉Нетворкинг и afterparty Будет интересно — зовите друзей и регистрируйтесь!  Количество мест ограничено. Дождитесь подтверждения заявки.

#medium Задача: 236. Lowest Common Ancestor of a Binary Tree Дано бинарное дерево. Найдите наименьший общий предок (LCA) двух заданных узлов в дереве. Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)." Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

👨‍💻 Алгоритм: 1⃣Начало обхода дерева с корня: Начните обход дерева с корневого узла. Если текущий узел является одним из узлов p или q, установите переменную mid в значение True и продолжите поиск другого узла в левой и правой ветвях. 2⃣Проверка поддеревьев: Выполните рекурсивный обход левой и правой ветвей дерева. Если какая-либо из ветвей (левая или правая) возвращает True, это означает, что один из двух узлов найден ниже по дереву. 3⃣Определение LCA: Если в любой момент обхода дерева две из трех переменных (left, right или mid) становятся True, это означает, что найден наименьший общий предок (LCA) для узлов p и q. 😎 Решение:

class Solution {
private:
    TreeNode* ans;

public:
    Solution() {
        this->ans = nullptr;
    }

    bool recurseTree(TreeNode* currentNode, TreeNode* p, TreeNode* q) {
        if (currentNode == nullptr) {
            return false;
        }

        int left = this->recurseTree(currentNode->left, p, q) ? 1 : 0;
        int right = this->recurseTree(currentNode->right, p, q) ? 1 : 0;
        int mid = (currentNode == p || currentNode == q) ? 1 : 0;

        if (mid + left + right >= 2) {
            this->ans = currentNode;
        }

        return (mid + left + right > 0);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        this->recurseTree(root, p, q);
        return this->ans;
    }
};

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

Яндекс Музыка до конца года бесплатно! Подписка Яндекс Плюс для вас и 3-х близких до конца года бесплатно! Слушайте музыку, смотрите фильмы и читайте книги в одной подписке. Попробуйте!👍 Попробовать #реклама 18+ plus.yandex.ru О рекламодателе

#medium Задача: 379. Design Phone Directory Создайте телефонный справочник, который изначально имеет maxNumbers пустых слотов для хранения номеров. Справочник должен хранить номера, проверять, пуст ли определенный слот, и освобождать данный слот. Реализуйте класс PhoneDirectory: PhoneDirectory(int maxNumbers) Инициализирует телефонный справочник с количеством доступных слотов maxNumbers. int get() Предоставляет номер, который никому не назначен. Возвращает -1, если номера недоступны. bool check(int number) Возвращает true, если слот доступен, и false в противном случае. void release(int number) Перераспределяет или освобождает номер слота. Пример:

Input
["PhoneDirectory", "get", "get", "check", "get", "check", "release", "check"]
[[3], [], [], [2], [], [2], [2], [2]]
Output
[null, 0, 1, true, 2, false, null, true]

👨‍💻 Алгоритм: 1⃣Инициализировать массив isSlotAvailable размером maxNumbers, установив значение true во всех индексах. 2⃣Метод get(): Проходить по массиву isSlotAvailable. Если найдется true на каком-либо индексе, установить isSlotAvailable[i] = false и вернуть i. Если доступных слотов нет, вернуть -1. Метод check(number): Вернуть значение isSlotAvailable[number]. 3⃣Метод release(number): Установить isSlotAvailable[number] = true. 😎 Решение:

class PhoneDirectory {
public:
    PhoneDirectory(int maxNumbers) : isSlotAvailable(maxNumbers, true) {}

    int get() {
        auto it = std::find(isSlotAvailable.begin(), isSlotAvailable.end(), true);
        if (it != isSlotAvailable.end()) {
            *it = false;
            return std::distance(isSlotAvailable.begin(), it);
        }
        return -1;
    }

    bool check(int number) {
        return isSlotAvailable[number];
    }

    void release(int number) {
        isSlotAvailable[number] = true;
    }

private:
    std::vector<bool> isSlotAvailable;
};

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

Твое резюме на HeadHunter — ОК, если ты видишь это. HeadHunter сравнивает ключевые навыки в твоем резюме и в вакансии и в момент отклика отображает, насколько % ты соответствуешь требованиям. Специальный бейджик «Подходит по навыкам на 100%» отображается, если соответствие составляет более 60%. Если при просмотре вакансий ты видишь такой бейджик, это значит, что список навыков в твоем резюме качественно составлен. Это важный параметр, так как рекрутерам чаще показываются резюме с лучшим соответствием. О том, как правильно указывать ключевые навыки и оптимизировать свое резюме я уже рассказывал в этом видео

#medium Задача: 235. Lowest Common Ancestor of a Binary Search Tree Дано бинарное дерево поиска (BST). Найдите наименьший общий предок (LCA) двух заданных узлов в BST. Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)." Пример:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

👨‍💻 Алгоритм: 1⃣Начало обхода дерева с корня: Начните обход дерева с корневого узла. Проверьте, находятся ли узлы p и q в правом или левом поддереве текущего узла. 2⃣Продолжение поиска в поддереве: Если оба узла p и q находятся в правом поддереве текущего узла, продолжайте поиск в правом поддереве, начиная с шага 1. Если оба узла p и q находятся в левом поддереве текущего узла, продолжайте поиск в левом поддереве, начиная с шага 1. 3⃣Нахождение LCA: Если узлы p и q находятся в разных поддеревьях относительно текущего узла или один из узлов равен текущему узлу, то текущий узел является наименьшим общим предком (LCA). Верните этот узел как результат. 😎 Решение:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int parentVal = root->val;
        int pVal = p->val;
        int qVal = q->val;

        if (pVal > parentVal && qVal > parentVal) {
            return lowestCommonAncestor(root->right, p, q);
        } else if (pVal < parentVal && qVal < parentVal) {
            return lowestCommonAncestor(root->left, p, q);
        } else {
            return root;
        }
    }
};

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

Ответ на 1 вопрос и подписка на Яндекс Музыку ваша ✨Ответьте на 1 вопрос и получите в подарок доступ к Яндекс Музыке до конца года бесплатно!✨ Слушайте любимые треки и подкасты в HQ качестве без рекламы. Для 4 аккаунтов и 10 устройств. Кино и книги тоже в подписке! Попробуйте!👍 Попробовать #реклама 18+ mrqz.me О рекламодателе

#medium Задача: 378. Kth Smallest Element in a Sorted Matrix Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице. Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент. Вы должны найти решение с использованием памяти лучше, чем O(n²). Пример:

Input: matrix = [[-5]], k = 1
Output: -5

👨‍💻 Алгоритм: 1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список. 2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку. 3⃣Мин-куча будет содержать тройки информации (значение, строка, столбец). Куча будет упорядочена по значениям, и мы будем использовать номера строк и столбцов для добавления следующего элемента, если текущий элемент будет удален из кучи. 😎 Решение:

using namespace std;

class MyHeapNode {
public:
    int row;
    int column;
    int value;

    MyHeapNode(int v, int r, int c) : value(v), row(r), column(c) {}
};

class MyHeapComparator {
public:
    bool operator()(const MyHeapNode& x, const MyHeapNode& y) const {
        return x.value > y.value;
    }
};

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int N = matrix.size();

        priority_queue<MyHeapNode, vector<MyHeapNode>, MyHeapComparator> minHeap;

        for (int r = 0; r < min(N, k); r++) {
            minHeap.push(MyHeapNode(matrix[r][0], r, 0));
        }

        MyHeapNode element = minHeap.top();
        while (k-- > 0) {
            element = minHeap.top();
            minHeap.pop();
            int r = element.row, c = element.column;

            if (c < N - 1) {
                minHeap.push(MyHeapNode(matrix[r][c + 1], r, c + 1));
            }
        }

        return element.value;
    }
};

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