C/C++ | LeetCode

Задача: 1046. Last Stone Weight Сложность: easy Вам дан массив целых чисел stones, где stones[i] - вес i-го камня. Мы играем в игру с камнями. На каждом ходу мы выбираем два самых тяжелых камня и разбиваем их вместе. Предположим, что два самых тяжелых камня имеют веса x и y, причем x <= y. Результат разбивания таков: если x == y, оба камня уничтожаются, а если x != y, камень веса x уничтожается, а камень веса y имеет новый вес y - x. В конце игры остается не более одного камня. Верните вес последнего оставшегося камня. Если камней не осталось, верните 0. Пример:

Input: stones = [2,7,4,1,8,1]
Output: 1

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

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> maxHeap(stones.begin(), stones.end());
        
        while (maxHeap.size() > 1) {
            int first = maxHeap.top(); maxHeap.pop();
            int second = maxHeap.top(); maxHeap.pop();
            if (first != second) {
                maxHeap.push(first - second);
            }
        }
        
        return maxHeap.empty() ? 0 : maxHeap.top();
    }
};

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

Задача: 867. Transpose Matrix Сложность: easy Дан двумерный целочисленный массив matrix, верните его транспонированную матрицу. Транспонированная матрица — это матрица, перевернутая относительно своей главной диагонали, при этом строки и столбцы меняются местами. Пример:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[1,4,7],[2,5,8],[3,6,9]]

👨‍💻 Алгоритм: 1⃣Инициализируйте новую матрицу ans с размерами C x R, где C — количество столбцов в исходной матрице, а R — количество строк. 2⃣Скопируйте каждую запись исходной матрицы в новую матрицу так, чтобы ans[c][r] = matrix[r][c]. 3⃣Верните матрицу ans. 😎 Решение:

class Solution {
public:
    vector<vector<int>> transpose(vector<vector<int>>& A) {
        int R = A.size(), C = A[0].size();
        vector<vector<int>> ans(C, vector<int>(R));
        for (int r = 0; r < R; ++r)
            for (int c = 0; c < C; ++c)
                ans[c][r] = A[r][c];
        return ans;
    }
};

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

Задача: 76. Minimum Window Substring Сложность: hard Даны две строки s и t длиной m и n соответственно. Верните наименьшую подстроку строки s, содержащую все символы строки t (включая дубликаты). Если такой подстроки не существует, верните пустую строку "". Пример:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

👨‍💻 Алгоритм: 1⃣Используем два указателя left и right, инициализированные на начало строки s. 2⃣Расширяем окно, двигая right, пока окно не будет содержать все символы из t. 3⃣Как только окно удовлетворяет условию, начинаем двигать left, сокращая размер окна и обновляя минимальное, пока условие сохраняется. После — снова расширяем окно. 😎 Решение:

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.length() == 0 || t.length() == 0) {
            return "";
        }
        unordered_map<char, int> dictT;
        for (int i = 0; i < t.length(); i++) {
            dictT[t[i]]++;
        }
        int required = dictT.size();
        int l = 0, r = 0;
        int formed = 0;
        unordered_map<char, int> windowCounts;
        int ans[3] = {-1, 0, 0};
        while (r < s.length()) {
            char c = s[r];
            windowCounts[c]++;
            if (dictT.find(c) != dictT.end() && windowCounts[c] == dictT[c]) {
                formed++;
            }
            while (l <= r && formed == required) {
                c = s[l];
                if (ans[0] == -1 || r - l + 1 < ans[0]) {
                    ans[0] = r - l + 1;
                    ans[1] = l;
                    ans[2] = r;
                }
                windowCounts[c]--;
                if (dictT.find(c) != dictT.end() && windowCounts[c] < dictT[c]) {
                    formed--;
                }
                l++;
            }
            r++;
        }
        return ans[0] == -1 ? "" : s.substr(ans[1], ans[2] - ans[1] + 1);
    }
};

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

Задача: 753. Cracking the Safe Сложность: medium Имеется сейф, защищенный паролем. Пароль представляет собой последовательность из n цифр, каждая из которых может находиться в диапазоне [0, k - 1]. Сейф имеет особый способ проверки пароля. Например, правильный пароль - "345", а вы вводите "012345": после ввода 0 последние 3 цифры - "0", что неверно. После ввода 1 последние 3 цифры - "01", что неверно. После ввода 2 последние 3 цифры - "012", что неверно. После ввода 3 последние 3 цифры - "123", что неверно. После ввода 4 последние 3 цифры - "234", что неверно. После ввода 5 последние 3 цифры - "345", что верно, и сейф разблокируется. Верните любую строку минимальной длины, которая разблокирует сейф на определенном этапе ввода. Пример:

Input: n = 1, k = 2
Output: "10"

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

class Solution {
public:
    string crackSafe(int n, int k) {
        unordered_set<string> seen;
        string result;

        string startNode(n - 1, '0');
        dfs(startNode, k, seen, result);

        result += startNode;
        return result;
    }

private:
    void dfs(const string& node, int k, unordered_set<string>& seen, string& result) {
        for (int x = 0; x < k; ++x) {
            string neighbor = node + to_string(x);
            if (!seen.count(neighbor)) {
                seen.insert(neighbor);
                dfs(neighbor.substr(1), k, seen, result);
                result += to_string(x);
            }
        }
    }
};

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

Задача: 1466. Reorder Routes to Make All Paths Lead to the City Zero Сложность: medium Дано n городов, пронумерованных от 0 до n - 1, и n - 1 дорог, таких, что существует только один путь между двумя различными городами (эта сеть образует дерево). В прошлом году Министерство транспорта решило направить дороги в одном направлении, потому что они слишком узкие. Дороги представлены массивом connections, где connections[i] = [ai, bi] представляет дорогу от города ai до города bi. В этом году в столице (город 0) будет большое событие, и многие люди хотят приехать в этот город. Ваша задача состоит в том, чтобы переориентировать некоторые дороги так, чтобы каждый город мог посетить город 0. Верните минимальное количество изменённых дорог. Гарантируется, что каждый город может добраться до города 0 после перенаправления. Пример:

Input: n = 6, connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]
Output: 3
Explanation: Change the direction of edges show in red such that each node can reach the node 0 (capital).

👨‍💻 Алгоритм: 1⃣Создайте переменную count для подсчета количества рёбер, которые необходимо изменить. Инициализируйте её нулём. Создайте список смежности adj, который содержит список пар целых чисел так, чтобы adj[node] содержал всех соседей node в форме (neighbor, sign), где neighbor - соседний узел, а sign обозначает направление ребра (оригинальное или искусственное). 2⃣Начните обход в глубину (DFS). Используйте функцию dfs для выполнения обхода. В каждом вызове передавайте параметры node, parent и adj. Начните с узла 0 и parent равным -1. 3⃣Перебирайте всех соседей узла с помощью adj[node]. Для каждого neighbor, sign в adj[node], проверьте, равен ли neighbor родителю. Если равен, не посещайте его снова. Если neighbor не равен parent, выполните count += sign и рекурсивно вызовите dfs с node = neighbor и parent = node. По завершении обхода DFS, в count будет содержаться количество рёбер, которые необходимо изменить. Верните count. 😎 Решение:

class Solution {
public:
    int count = 0;

    void dfs(int node, int parent, unordered_map<int, vector<pair<int, int>>>& adj) {
        if (adj.find(node) == adj.end()) {
            return;
        }
        for (auto& nei : adj[node]) {
            int neighbor = nei.first;
            int sign = nei.second;
            if (neighbor != parent) {
                count += sign;
                dfs(neighbor, node, adj);
            }
        }
    }

    int minReorder(int n, vector<vector<int>>& connections) {
        unordered_map<int, vector<pair<int, int>>> adj;
        for (auto& connection : connections) {
            adj[connection[0]].emplace_back(connection[1], 1);
            adj[connection[1]].emplace_back(connection[0], 0);
        }
        dfs(0, -1, adj);
        return count;
    }
};

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

Задача: 373. Find K Pairs with Smallest Sums Сложность: medium Вам даны два целочисленных массива nums1 и nums2, отсортированных в неубывающем порядке, и целое число k. Определим пару (u, v), которая состоит из одного элемента из первого массива и одного элемента из второго массива. Верните k пар (u1, v1), (u2, v2), ..., (uk, vk) с наименьшими суммами. Пример:

Input: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
Output: [[1,2],[1,4],[1,6]]
Explanation: The first 3 pairs are returned from the sequence: [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

👨‍💻 Алгоритм: 1⃣Создайте две целочисленные переменные m и n, инициализируйте их размерами массивов nums1 и nums2 соответственно. Создайте список ans для хранения пар с наименьшими суммами, которые будут возвращены в качестве ответа. Создайте множество visited для отслеживания просмотренных пар. 2⃣Инициализируйте минимальную кучу minHeap, которая содержит тройки целых чисел: сумму пары, индекс первого элемента пары в nums1 и индекс второго элемента пары в nums2. Вставьте в minHeap первую пару из обоих массивов, т.е. nums1[0] + nums2[0], 0, 0, и добавьте пару (0, 0) в visited. 3⃣Повторяйте до получения k пар и пока minHeap не пуст: Извлеките верхний элемент из minHeap и установите i = top[1] и j = top[2]. Добавьте пару (nums1[i], nums2[j]) в ans. Если i + 1 < m и пары (i + 1, j) нет в visited, добавьте новую пару nums1[i + 1] + nums2[j], i + 1, j в minHeap. Если j + 1 < n и пары (i, j + 1) нет в visited, добавьте новую пару nums1[i] + nums2[j + 1], i, j + 1 в minHeap. Верните ans. 😎 Решение:

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        int m = nums1.size();
        int n = nums2.size();

        vector<vector<int>> ans;
        set<pair<int, int>> visited;

        priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>,
                       greater<pair<int, pair<int, int>>>> minHeap;
        minHeap.push({nums1[0] + nums2[0], {0, 0}});
        visited.insert({0, 0});

        while (k-- && !minHeap.empty()) {
            auto top = minHeap.top();
            minHeap.pop();
            int i = top.second.first;
            int j = top.second.second;

            ans.push_back({nums1[i], nums2[j]});

            if (i + 1 < m && visited.find({i + 1, j}) == visited.end()) {
                minHeap.push({nums1[i + 1] + nums2[j], {i + 1, j}});
                visited.insert({i + 1, j});
            }

            if (j + 1 < n && visited.find({i, j + 1}) == visited.end()) {
                minHeap.push({nums1[i] + nums2[j + 1], {i, j + 1}});
                visited.insert({i, j + 1});
            }
        }

        return ans;
    }
};

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

Задача: 716. Max Stack Сложность: hard Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова. Пример:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

👨‍💻 Алгоритм: 1⃣Инициализируйте MaxStack с двумя стеками: один для хранения всех элементов, другой для отслеживания максимальных элементов. 2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека. 3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно. 😎 Решение:

class MaxStack {
public:
    MaxStack() {}

    void push(int x) {
        stack.push(x);
        if (maxStack.empty() || x >= maxStack.top()) {
            maxStack.push(x);
        }
    }

    int pop() {
        int x = stack.top();
        stack.pop();
        if (x == maxStack.top()) {
            maxStack.pop();
        }
        return x;
    }

    int top() {
        return stack.top();
    }

    int peekMax() {
        return maxStack.top();
    }

    int popMax() {
        int maxVal = maxStack.top();
        maxStack.pop();
        stack<int> buffer;
        while (stack.top() != maxVal) {
            buffer.push(stack.top());
            stack.pop();
        }
        stack.pop();
        while (!buffer.empty()) {
            push(buffer.top());
            buffer.pop();
        }
        return maxVal;
    }

private:
    stack<int> stack;
    stack<int> maxStack;
};

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

Задача: 251. Flatten 2D Vector Сложность: medium Пример:

Input: vec = [[1, 2], [3], [4]]
Output: 1, 2, 3, true, true, 4, false

👨‍💻 Алгоритм: 1⃣Преобразуем двумерный вектор в одномерный Итерируемся по каждому вложенному вектору и добавляем его элементы в одномерный массив. 2⃣Метод hasNext проверяет наличие следующего элемента Возвращает true, если текущий индекс position + 1 находится в пределах размера массива. 3⃣Метод next возвращает элемент Увеличивает индекс position и возвращает текущий элемент массива. 😎 Решение:

#include <vector>
using namespace std;

class Vector2D {
    vector<int> nums;
    int position;

public:
    Vector2D(vector<vector<int>>& v) : position(-1) {
        for (auto& innerList : v) {
            nums.insert(nums.end(), innerList.begin(), innerList.end());
        }
    }

    int next() {
        position++;
        return nums[position];
    }

    bool hasNext() {
        return position + 1 < nums.size();
    }
};

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

Распродажа металлообрабатывающих станков, скидки до 30% Срок действия акции ограничен, не упустите шанс! Токарные и фрезерные станки по металлу, обрабатывающие центры. Большой выбор моделей в наличии на складе. Узнать больше #реклама 16k20.ru О рекламодателе

Задача: 681. Next Closest Time Сложность: medium Дано время, представленное в формате "ЧЧ:ММ". Сформируйте ближайшее следующее время, используя текущие цифры. Количество раз, которое можно использовать цифру, не ограничено. Можно предположить, что заданная строка всегда корректна. Например, "01:34", "12:09" являются корректными. "1:34", "12:9" являются некорректными. Пример:

Input: time = "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.
It is not 19:33, because this occurs 23 hours and 59 minutes later.

👨‍💻 Алгоритм: 1⃣Симулируйте ход часов, увеличивая время на одну минуту. Каждый раз, когда время увеличивается, если все цифры допустимы, верните текущее время. 2⃣Представьте время как целое число t в диапазоне 0 <= t < 24 * 60. Тогда часы равны t / 60, минуты равны t % 60. 3⃣Найдите каждую цифру часов и минут: часы / 10, часы % 10 и т.д. 😎 Решение:

class Solution {
public:
    string nextClosestTime(string time) {
        int cur = 60 * stoi(time.substr(0, 2)) + stoi(time.substr(3));
        unordered_set<int> allowed;
        for (char c : time) if (c != ':') {
            allowed.insert(c - '0');
        }

        while (true) {
            cur = (cur + 1) % (24 * 60);
            vector<int> digits = {cur / 60 / 10, cur / 60 % 10, cur % 60 / 10, cur % 60 % 10};
            bool valid = true;
            for (int d : digits) {
                if (!allowed.count(d)) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                return (cur / 60 < 10 ? "0" : "") + to_string(cur / 60) + ":" + (cur % 60 < 10 ? "0" : "") + to_string(cur % 60);
            }
        }
    }
};

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

🚀 Станьте C++ разработчиком и откройте для себя новые возможности в IT. Актуальное обучение от OTUS — это ваш старт в масштабную разработку на современном подмножестве C++! 👨‍💻 На курсе вы освоите все ключевые аспекты разработки на C++ — от основ синтаксиса до идиом и паттернов языка, продвинутой многопоточности и работы с базами данных Мы подготовим вас для работы с высоконагруженными приложениями, IoT-устройствами и сложными проектами. ⚡️ Изучите C++ с нуля и пройдите два этапа обучения: от Junior до Middle Developer. Реальные кейсы, лучшие практики и советы экспертов помогут вам освоить язык и уверенно претендовать на востребованные позиции. ❗️ Запись на курс закрывается! Оставьте заявку и получите скидку на обучение по промокоду CPPspec_6: https://otus.pw/YuAOj/ Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576, www.otus.ru

В турагентство на удаленку требуются стажеры Клиентов предоставим. Можно без опыта и совмещая с основной работой или декретом. С нас обучение с гарантированной стажировкой. Доход после обучения: от 50 000₽ до 220 000₽. Оплата в процессе обучения зависит от вашей вовлеченности. Задачи: Помогать людям организовывать путешествия: подбор самых выгодных предложений на отдых со скидкой до 50% в новых сервисах бронирования. Условия: ✅ Без опыта — обучение с нуля за 2 месяца, первые выплаты в среднем в течение 2 недель; ✅Удаленная работа или совмещение с офисом (по желанию, зависит от вашего города). Хотите проверить, подойдет ли это вам? Регистрируйтесь на бесплатный вводный урок, на котором узнаете: — как подбирать туры для себя и близких с выгодой до 40% — как получать комиссию 7-10% с каждого тура. Узнать больше #реклама 16+ via-tourism-school.space О рекламодателе

Задача: 1071. Greatest Common Divisor of Strings Сложность: easy Для двух строк s и t мы говорим, что "t делит s", если и только если s = t + t + t + ... + t (т.е. t соединена сама с собой один или более раз). Даны две строки str1 и str2, верните наибольшую строку x, такую что x делит и str1, и str2. Пример:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

👨‍💻 Алгоритм: 1⃣Найдите более короткую строку среди str1 и str2, для простоты пусть это будет str1. 2⃣Начните с base = str1 и проверьте, состоят ли обе строки str1 и str2 из множителей строки base. Если это так, верните base. В противном случае, попробуйте более короткую строку, удалив последний символ из base. 3⃣Если вы проверили все префиксные строки и не нашли строку GCD, верните "". 😎 Решение:

class Solution {
public:
    bool valid(string str1, string str2, int k) {
        int len1 = str1.size(), len2 = str2.size();
        if (len1 % k > 0 || len2 % k > 0) {
            return false;
        } else {
            string base = str1.substr(0, k);
            int n1 = len1 / k, n2 = len2 / k;
            return str1 == joinWords(base, n1) && str2 == joinWords(base, n2);
        }
    }
    string joinWords(string str, int k) {
        string ans = "";
        for (int i = 0; i < k; ++i) {
            ans += str;
        }
        return ans;
    }
    string gcdOfStrings(string str1, string str2) {
        int len1 = str1.length(), len2 = str2.length();
        for (int i = min(len1, len2); i >= 1; --i) {
            if (valid(str1, str2, i)) {
                return str1.substr(0, i);
            }
        }
        return "";
    }
};

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

Задача: 1258. Synonymous Sentences Сложность: medium Вам дан список эквивалентных пар строк synonyms, где synonyms[i] = [si, ti] означает, что si и ti являются эквивалентными строками. Вам также дан текст предложения. Верните все возможные синонимичные предложения, отсортированные лексикографически. Пример:

Input: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"
Output: ["I am cheerful today but was sad yesterday","I am cheerful today but was sorrow yesterday","I am happy today but was sad yesterday","I am happy today but was sorrow yesterday","I am joy today but was sad yesterday","I am joy today but was sorrow yesterday"]

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

class Solution {
public:
    vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
        unordered_map<string, set<string>> graph;
        for (const auto& pair : synonyms) {
            graph[pair[0]].insert(pair[1]);
            graph[pair[1]].insert(pair[0]);
        }

        vector<string> words = split(text, ' ');
        vector<vector<string>> synonymGroups;
        for (const string& word : words) {
            synonymGroups.push_back(findSynonyms(graph, word));
        }

        vector<string> sentences;
        string sentence;
        generate(sentences, synonymGroups, sentence, 0);
        sort(sentences.begin(), sentences.end());
        return sentences;
    }

private:
    vector<string> split(const string& str, char delimiter) {
        vector<string> tokens;
        string token;
        istringstream tokenStream(str);
        while (getline(tokenStream, token, delimiter)) {
            tokens.push_back(token);
        }
        return tokens;
    }

    vector<string> findSynonyms(unordered_map<string, set<string>>& graph, const string& word) {
        set<string> synonyms;
        stack<string> stack;
        stack.push(word);
        while (!stack.empty()) {
            string w = stack.top();
            stack.pop();
            if (synonyms.insert(w).second) {
                for (const string& neighbor : graph[w]) {
                    stack.push(neighbor);
                }
            }
        }
        return vector<string>(synonyms.begin(), synonyms.end());
    }

    void generate(vector<string>& sentences, const vector<vector<string>>& groups, string& sentence, int index) {
        if (index == groups.size()) {
            sentences.push_back(sentence.substr(1));
            return;
        }
        for (const string& word : groups[index]) {
            string original = sentence;
            sentence += " " + word;
            generate(sentences, groups, sentence, index + 1);
            sentence = original;
        }
    }
};

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

Задача: 683. K Empty Slots Сложность: hard У вас есть n лампочек, расположенных в ряд и пронумерованных от 1 до n. Изначально все лампочки выключены. Каждый день мы включаем ровно одну лампочку, и через n дней все лампочки будут включены. Вам дан массив bulbs длины n, где bulbs[i] = x означает, что в (i+1)-й день мы включим лампочку в позиции x, где i индексируется с 0, а x индексируется с 1. Дано целое число k, верните минимальный номер дня, такой что существует две включенные лампочки, между которыми ровно k выключенных лампочек. Если такого дня не существует, верните -1. Пример:

Input: bulbs = [1,3,2], k = 1
Output: 2
Explanation:
On the first day: bulbs[0] = 1, first bulb is turned on: [1,0,0]
On the second day: bulbs[1] = 3, third bulb is turned on: [1,0,1]
On the third day: bulbs[2] = 2, second bulb is turned on: [1,1,1]
We return 2 because on the second day, there were two on bulbs with one off bulb between them.

👨‍💻 Алгоритм: 1⃣Поддерживайте active, отсортированную структуру данных, содержащую каждую лампочку, которая в данный момент включена. Это позволит быстро находить соседей для вновь добавленных лампочек и проверять условия задачи. 2⃣Когда вы добавляете лампочку в active, проверьте ее нижних и верхних соседей. Для этого найдите ближайшие включенные лампочки с обеих сторон и проверьте количество выключенных лампочек между ними. 3⃣Если какой-то сосед удовлетворяет условию (ровно k выключенных лампочек между двумя включенными), значит, условие впервые произошло в этот день, и вы можете вернуть номер этого дня. Если такого дня не существует после включения всех лампочек, верните -1. 😎 Решение:

#include <set>
#include <vector>

class Solution {
public:
    int kEmptySlots(std::vector<int>& flowers, int k) {
        std::set<int> active;
        int day = 0;
        
        for (int flower : flowers) {
            day++;
            active.insert(flower);
            auto lower = active.lower_bound(flower);
            auto higher = active.upper_bound(flower);
            
            if (lower != active.begin() && flower - *std::prev(lower) - 1 == k) {
                return day;
            }
            if (higher != active.end() && *higher - flower - 1 == k) {
                return day;
            }
        }
        return -1;
    }
};

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

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

Задача: 333. Largest BST Subtree Сложность: medium Дан корень бинарного дерева, найдите самое большое поддерево, которое также является деревом бинарного поиска (BST), где "самое большое" означает поддерево с наибольшим количеством узлов. Дерево бинарного поиска (BST) — это дерево, в котором все узлы соблюдают следующие свойства: Значения в левом поддереве меньше значения их родительского (корневого) узла. Значения в правом поддереве больше значения их родительского (корневого) узла. Примечание: Поддерево должно включать всех своих потомков. Пример:

Input: root = [10,5,15,1,8,null,7]
Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one. The return value is the subtree's size, which is 3.

👨‍💻 Алгоритм: 1⃣Пост-упорядоченный обход дерева: Обходите каждую ноду дерева в пост-упорядоченном порядке (left-right-root). Это позволит гарантировать, что обе поддеревья ноды уже проверены на соответствие критериям BST перед проверкой самой ноды. 2⃣Проверка условий BST для каждой ноды: Для каждой ноды определите минимальное и максимальное значения в её левом и правом поддеревьях. Проверьте, удовлетворяет ли текущее поддерево условиям BST: - значение текущей ноды должно быть больше максимального значения в левом поддереве. - значение текущей ноды должно быть меньше минимального значения в правом поддереве. Если условия выполняются, вычислите размер текущего поддерева как сумму размеров левого и правого поддеревьев плюс 1 (для текущей ноды). 3⃣Возврат максимального размера BST: Если текущее поддерево не является BST, верните максимальный размер BST из его левого или правого поддерева. В конце рекурсивного обхода верните максимальный размер BST в дереве. 😎 Решение:

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

class NodeValue {
public:
    int minNode, maxNode, maxSize;
    
    NodeValue(int minNode, int maxNode, int maxSize) : 
        minNode(minNode), maxNode(maxNode), maxSize(maxSize) {}
};

class Solution {
public:
    NodeValue largestBSTSubtreeHelper(TreeNode* root) {
        if (root == nullptr) {
            return NodeValue(INT_MAX, INT_MIN, 0);
        }
        
        NodeValue left = largestBSTSubtreeHelper(root->left);
        NodeValue right = largestBSTSubtreeHelper(root->right);
        
        if (left.maxNode < root->val && root->val < right.minNode) {
            return NodeValue(min(root->val, left.minNode), max(root->val, right.maxNode), 
                             left.maxSize + right.maxSize + 1);
        }
        
        return NodeValue(INT_MIN, INT_MAX, max(left.maxSize, right.maxSize));
    }
    
    int largestBSTSubtree(TreeNode* root) {
        return largestBSTSubtreeHelper(root).maxSize;
    }
};

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

Задача: 1095. Find in Mountain Array Сложность: hard Массив arr является горным массивом тогда и только тогда, когда: Длина массива arr >= 3. Существует некоторое i с 0 < i < arr.length - 1 такое, что: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > ... > arr[arr.length - 1] Дан горный массив mountainArr, верните минимальный индекс, такой что mountainArr.get(index) == target. Если такого индекса не существует, верните -1. Вы не можете напрямую обращаться к массиву. Вы можете использовать интерфейс MountainArray: MountainArray.get(k) возвращает элемент массива на индексе k (индексация начинается с 0). MountainArray.length() возвращает длину массива. Решения, использующие более 100 вызовов MountainArray.get, будут оценены как неправильные. Также любые решения, которые пытаются обойти ограничение, будут дисквалифицированы. Пример:

Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

👨‍💻 Алгоритм: 1⃣Найти индекс пика: Инициализируем два указателя low и high, где low начинается с 1, а high — с длины массива минус 2. Используем бинарный поиск для нахождения пикового элемента: если элемент в середине меньше следующего элемента, то пиковый элемент находится справа, иначе он находится слева. Продолжаем сужать диапазон поиска до тех пор, пока low не станет равным high. Это и будет индекс пика. 2⃣Бинарный поиск в возрастающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от 0 до пикового индекса. Проводим обычный бинарный поиск: если значение в середине меньше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс, иначе продолжаем. 3⃣Бинарный поиск в убывающей части массива: Устанавливаем указатели low и high для поиска в диапазоне от пикового индекса плюс 1 до конца массива. Проводим бинарный поиск, но с учетом убывающей последовательности: если значение в середине больше целевого значения, перемещаем low вправо, иначе перемещаем high влево. По завершении поиска проверяем, равно ли значение по индексу low целевому значению. Если да, возвращаем индекс. Если значение не найдено, возвращаем -1. 😎 Решение:

class Solution {
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int length = mountainArr.length();

        int low = 1, high = length - 2;
        while (low != high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        int peak = low;

        low = 0, high = peak;
        while (low < high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (mountainArr.get(low) == target) {
            return low;
        }

        low = peak + 1, high = length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (mountainArr.get(mid) > target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (mountainArr.get(low) == target) {
            return low;
        }

        return -1;
    }
};

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

Методичка: как сделать онлайн-встречи эффективнее Надоело ждать коллег, которые постоянно забывают о встречах, а отсутствие повестки и потерянные договоренности мешают нормально работать? Команда МТС Линк собрала на 37 страницах полезные материалы, чек-листы и кейсы, которые помогают компаниям проводить эффективные совещания в онлайне с помощью сервиса Встречи. Из методички узнаете: - Как создать постоянную ссылку и подключаться на встречи в 2 клика, - Как делать заметки и работать с файлами, не переживая за качество связи и безопасность данных. - Как облегчает жизнь ИИ, который расшифровывает созвоны в текст и автоматически отправляет расшифровку на почту. Еще в методичке описаны 7 способов оценки текущей эффективности ваших онлайн-встреч. Получить гайд можно бесплатно на сайте. Скачать #реклама 16+ mts-link.ru О рекламодателе

Задача: 1228. Missing Number In Arithmetic Progression Сложность: easy В массиве arr значения находились в арифметической прогрессии: значения arr[i + 1] - arr[i] равны для всех 0 <= i < arr.length - 1. Из массива arr было удалено значение, которое не было первым или последним значением в массиве. Дан массив arr, вернуть удаленное значение. Пример:

Input: arr = [5,7,11,13]
Output: 9
Explanation: The previous array was [5,7,9,11,13].

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

class Solution {
public:
    int missingNumber(vector<int>& arr) {
        int n = arr.size();
        int difference = (arr[n - 1] - arr[0]) / n;
        int expected = arr[0];

        for (int val : arr) {
            if (val != expected) {
                return expected;
            }
            expected += difference;
        }
        return expected;
    }
};

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