C/C++ | LeetCode

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

Задача: 939. Minimum Area Rectangle Сложность: medium Дан массив точек в плоскости X-Y points, где points[i] = [xi, yi]. Верните минимальную площадь прямоугольника, образованного из этих точек, со сторонами, параллельными осям X и Y. Если такого прямоугольника не существует, верните 0. Пример:

Input: points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

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

class Solution {
public:
    int minAreaRect(vector<vector<int>>& points) {
        unordered_set<string> pointSet;
        for (auto& point : points) {
            pointSet.insert(to_string(point[0]) + "," + to_string(point[1]));
        }
        
        int minArea = INT_MAX;
        for (int i = 0; i < points.size(); i++) {
            for (int j = i + 1; j < points.size(); j++) {
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                if (x1 != x2 && y1 != y2 && pointSet.count(to_string(x1) + "," + to_string(y2)) && pointSet.count(to_string(x2) + "," + to_string(y1))) {
                    minArea = min(minArea, abs(x2 - x1) * abs(y2 - y1));
                }
            }
        }
        
        return minArea == INT_MAX ? 0 : minArea;
    }
};

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

Высшее образование дистанционно от 4 700 ₽/мес. Поступи в Университет «Синергия»! — Высшее образование в московском вузе, не выходя из дома. — Полностью дистанционный онлайн-формат. — Обучайся дома, на работе, в путешествии. — Поступление круглый год. — Диплом государственного образца. — Программа «колледж + вуз» без ЕГЭ. Рассрочка 0% на весь срок обучения. Перейти на сайт #реклама 16+ synergy.ru О рекламодателе

Задача: 227. Basic Calculator II Сложность: medium Дана строка s, представляющая выражение. Вычислите это выражение и верните его значение. Целочисленное деление должно округляться к нулю. Вы можете предположить, что данное выражение всегда является допустимым. Все промежуточные результаты будут находиться в диапазоне [-2^31, 2^31 - 1]. Примечание: Запрещено использовать какие-либо встроенные функции, которые вычисляют строки как математические выражения, такие как eval(). Пример:

Input: s = "3+2*2"
Output: 7

👨‍💻 Алгоритм: 1⃣Вместо использования стека, используем переменную lastNumber для отслеживания значения последнего вычисленного выражения. 2⃣Если операция сложения (+) или вычитания (-), добавляем lastNumber к результату вместо того, чтобы помещать его в стек. Текущее значение currentNumber будет обновлено на lastNumber для следующей итерации. 3⃣Если операция умножения (*) или деления (/), вычисляем выражение lastNumber * currentNumber и обновляем lastNumber с результатом выражения. Это значение будет добавлено к результату после сканирования всей строки. 😎 Решение:

class Solution {
public:
    int calculate(string s) {
        int length = s.length();
        if (length == 0) return 0;
        int currentNumber = 0, lastNumber = 0, result = 0;
        char sign = '+';
        
        for (int i = 0; i < length; i++) {
            char currentChar = s[i];
            if (isdigit(currentChar)) {
                currentNumber = (currentNumber * 10) + (currentChar - '0');
            }
            if (!isdigit(currentChar) && !iswspace(currentChar) || i == length - 1) {
                if (sign == '+' || sign == '-') {
                    result += lastNumber;
                    lastNumber = (sign == '+') ? currentNumber : -currentNumber;
                } else if (sign == '*') {
                    lastNumber = lastNumber * currentNumber;
                } else if (sign == '/') {
                    lastNumber = lastNumber / currentNumber;
                }
                sign = currentChar;
                currentNumber = 0;
            }
        }
        result += lastNumber;
        return result;  
    }
};

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

Задача: 868. Binary Gap Сложность: easy Дано положительное целое число n, найдите и верните наибольшее расстояние между любыми двумя соседними единицами в двоичном представлении числа n. Если нет двух соседних единиц, верните 0. Две единицы считаются соседними, если их разделяют только нули (возможно, никаких нулей нет). Расстояние между двумя единицами — это абсолютная разница между их позициями в битовом представлении. Например, две единицы в "1001" имеют расстояние 3. Пример:

Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.

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

class Solution {
public:
    int binaryGap(int N) {
        int A[32], t = 0;
        for (int i = 0; i < 32; ++i)
            if ((N >> i) & 1)
                A[t++] = i;

        int ans = 0;
        for (int i = 0; i < t - 1; ++i)
            ans = max(ans, A[i + 1] - A[i]);
        return ans;
    }
};

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

Профессия «Бизнес-аналитик» - начни учиться бесплатно! Освойте высокооплачиваемую IT-профессию с нуля за 6 месяцев. Выдаём диплом, помогаем с трудоустройством. Excel, SQL, PowerBI, Python, BPMN, UML, EPC, IDEF. Преимущества обучения в Академии Eduson: 🎓 можно начать учиться бесплатно, если не понравится — не платите 🎓 официальный государственный диплом 🎓 рассрочка 0% на 24 мес. 🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать стабильный доход уже во время обучения! Узнать больше #реклама 16+ eduson.academy О рекламодателе

Задача: 81. Search in Rotated Sorted Array II Сложность: medium Дан отсортированный (возможно, с дубликатами) массив nums, подвергшийся ротации. Нужно определить, содержится ли число target в этом массиве. Необходимо минимизировать количество операций поиска. Пример:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

👨‍💻 Алгоритм: 1⃣Используем модифицированный бинарный поиск с указателями start и end. 2⃣В каждой итерации: Если nums[mid] == target, возвращаем true Если nums[mid] == nums[start], бинарный поиск невозможен — сдвигаем start++ Определяем, находится ли nums[mid] и target в одной отсортированной половине: Если да — продолжаем обычный бинарный поиск Если нет — двигаем в нужную сторону, зная, что целевой элемент в другой части 3⃣Повторяем до start > end. 😎 Решение:

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) return false;
        int end = n - 1;
        int start = 0;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] == target) {
                return true;
            }

            if (!isBinarySearchHelpful(nums, start, nums[mid])) {
                start++;
                continue;
            }

            bool pivotArray = existsInFirst(nums, start, nums[mid]);
            bool targetArray = existsInFirst(nums, start, target);

            if (pivotArray ^ targetArray) {
                if (pivotArray) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            } else {
                if (nums[mid] < target) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return false;
    }

    bool isBinarySearchHelpful(vector<int>& nums, int start, int element) {
        return nums[start] != element;
    }

    bool existsInFirst(vector<int>& nums, int start, int element) {
        return nums[start] <= element;
    }
};

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

Профессия «Аналитик данных» - начни учиться бесплатно! Освойте высокооплачиваемую IT-профессию с нуля за 6 месяцев. Выдаём диплом, помогаем с трудоустройством. Excel, SQL, PowerBI, Python. Преимущества обучения в Академии Eduson: 🎓 можно начать учиться бесплатно, если не понравится — не платите 🎓 официальный государственный диплом 🎓 рассрочка 0% на 24 мес. 🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать стабильный доход уже во время обучения! Подать заявку #реклама 16+ eduson.academy О рекламодателе

Задача: 857. Minimum Cost to Hire K Workers Сложность: hard Есть n работников. Вам даны два целочисленных массива: quality и wage, где quality[i] — качество работы i-го работника, а wage[i] — минимальная ожидаемая заработная плата i-го работника. Мы хотим нанять ровно k работников для формирования оплачиваемой группы. Чтобы нанять группу из k работников, мы должны оплатить их в соответствии со следующими правилами: Каждому работнику в оплачиваемой группе должно быть выплачено как минимум его ожидаемое минимальное вознаграждение. В группе заработная плата каждого работника должна быть прямо пропорциональна его качеству. Это означает, что если качество работы одного работника вдвое выше, чем у другого работника в группе, то ему должно быть выплачено вдвое больше. Учитывая целое число k, верните наименьшую сумму денег, необходимую для формирования оплачиваемой группы, удовлетворяющей указанным условиям. Ответы с точностью до 10^-5 от фактического ответа будут приняты. Пример:

Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd worker.

👨‍💻 Алгоритм: 1⃣Инициализируйте переменные: n для размера массивов quality и wage, totalCost для минимальной стоимости (начальное значение - максимум) и currentTotalQuality для суммы качеств текущих работников. Создайте массив wageToQualityRatio для хранения отношения заработной платы к качеству и качества каждого работника. Рассчитайте и сохраните отношение заработной платы к качеству для каждого работника в wageToQualityRatio. Отсортируйте wageToQualityRatio по возрастанию. 2⃣Создайте приоритетную очередь workers (максимальная куча) для хранения выбранных работников. Итерируйте через отсортированный wageToQualityRatio: добавляйте качество текущего работника в workers и обновляйте currentTotalQuality. 3⃣Если размер workers превышает k, удалите работника с наибольшим качеством из workers и обновите currentTotalQuality. Если размер workers равен k, рассчитайте общую стоимость, умножив currentTotalQuality на отношение заработной платы к качеству текущего работника. Обновите totalCost, если рассчитанная стоимость меньше текущей. Верните totalCost. 😎 Решение:

class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        int n = quality.size();
        double totalCost = numeric_limits<double>::max();
        double currentTotalQuality = 0;
        vector<pair<double, int>> wageToQualityRatio;

        for (int i = 0; i < n; i++) {
            wageToQualityRatio.push_back({static_cast<double>(wage[i]) / quality[i], quality[i]});
        }

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

        priority_queue<int> workers;

        for (auto& [ratio, q] : wageToQualityRatio) {
            workers.push(q);
            currentTotalQuality += q;

            if (workers.size() > k) {
                currentTotalQuality -= workers.top();
                workers.pop();
            }

            if (workers.size() == k) {
                totalCost = min(totalCost, currentTotalQuality * ratio);
            }
        }
        return totalCost;
    }
};

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный однодневный интенсив по AI! Освой искусственный интеллект для профессионального роста: создавай нейросети, автоматизируй бизнес-задачи и зарабатывай на AI-решениях. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе

Задача: 1437. Check If All 1's Are at Least Length K Places Away Сложность: easy Дан бинарный массив nums и целое число k. Вернуть true, если все единицы находятся на расстоянии не менее k позиций друг от друга, в противном случае вернуть false. Пример:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.

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

class Solution {
public:
    bool kLengthApart(vector<int>& nums, int k) {
        int count = k;
        for (int num : nums) {
            if (num == 1) {
                if (count < k) {
                    return false;
                }
                count = 0;
            } else {
                count++;
            }
        }
        return true;
    }
};

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

Ищу желающих перейти в сферу IT без долгого обучения ⚡ Обучим бесплатно — от вас потребуется всего несколько часов в день. Мы помогаем IT-компаниям находить квалифицированных тестировщиков. Профессия тестировщика — отличный способ сменить сферу и начать зарабатывать стабильно. 👌 Подходит тем, кто не боится работать и хочет достойный доход. Сначала проведу вводное бесплатное занятие, где расскажу: — что такое тестирование и зачем оно нужно; — где искать клиентов; — как пройти практику и попасть в крутую IT-команду. ✅ Что нужно будет делать: — проверять приложения и программы; — находить баги; — получать за это деньги. 💰 Доход — от 70 000 ₽ в месяц и выше Подходит даже без технической подготовки. 👍 Для регистрации на бесплатный урок переходите на сайт. Перейти на сайт #реклама 16+ site.purrweb-academy.ru О рекламодателе

Задача: 940. Distinct Subsequences II Сложность: hard Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Подпоследовательность строки - это новая строка, которая образуется из исходной строки путем удаления некоторых (можно ни одного) символов без нарушения взаимного расположения оставшихся символов. (Например, "ace" является подпоследовательностью "abcde", а "aec" - нет. Пример:

Input: s = "abc"
Output: 7

👨‍💻 Алгоритм: 1⃣Определить матрицу DP, где dp[i][j] будет хранить количество подпоследовательностей строки s с длиной i, оканчивающихся символом j. 2⃣Инициализировать матрицу DP нулями. Пройти по каждому символу строки: Если символ еще не был встречен, все подпоследовательности до текущего символа + текущий символ. Если символ уже был встречен, учет всех подпоследовательностей, включающих текущий символ, с учетом предыдущих вхождений. 3⃣Вернуть сумму всех значений в DP по модулю 10^9 + 7. 😎 Решение:

using namespace std;

class Solution {
public:
    int countSubsequences(string s) {
        const int MOD = 1000000007;
        vector<int> dp(26, 0);
        for (char c : s) {
            int index = c - 'a';
            dp[index] = (accumulate(dp.begin(), dp.end(), 0LL) + 1) % MOD;
        }
        return accumulate(dp.begin(), dp.end(), 0LL) % MOD;
    }
};

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

Высшее образование онлайн — поменяйте жизнь в 2025 году! ✅Набор в мае: от 6700 ₽/мес.* Московский технологический институт предлагает: — Высшее образование в московском вузе без выезда на сессии — Полностью дистанционный онлайн-формат — Возможность обучаться дома, на работе, в путешествии — Диплом государственного образца — Более 60 направлений на выбор (IT, инженерные, экономические, педагогические, управленческие и другие) — 5 способов оплаты обучения — Поддержка персонального куратора: от поступления до получения диплома Узнать больше #реклама 16+ mti-education.ru О рекламодателе

Задача: 1054. Distant Barcodes Сложность: medium На складе имеется ряд штрих-кодов, где i-й штрих-код - barcodes[i]. Переставьте штрих-коды так, чтобы два соседних штрих-кода не были одинаковыми. Вы можете вернуть любой ответ, и гарантируется, что ответ существует. Пример:

Input: barcodes = [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]

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

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        unordered_map<int, int> count;
        for (int barcode : barcodes) {
            count[barcode]++;
        }

        priority_queue<pair<int, int>> maxHeap;
        for (auto& [barcode, freq] : count) {
            maxHeap.push({freq, barcode});
        }

        vector<int> result;
        pair<int, int> prev = {0, 0};

        while (!maxHeap.empty()) {
            auto [freq, barcode] = maxHeap.top();
            maxHeap.pop();
            result.push_back(barcode);
            if (prev.first > 0) {
                maxHeap.push(prev);
            }
            prev = {freq - 1, barcode};
        }

        return result;
    }
};

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

Теперь AI сам создает сайты ИИшка в Битрикс24 берёт на себя весь процесс: структура, дизайн, контент — всё создаётся автоматически. Сделайте один запрос AI-помощнику, и через 30 секунд он создаст свой вариант полностью работающего сайта. Узнать больше #реклама sites-24.bitrix24.ru О рекламодателе

Задача: 1012. Numbers With Repeated Digits Сложность: hard Задав целое число n, верните количество положительных целых чисел в диапазоне [1, n], у которых хотя бы одна цифра повторяется. Пример:

Input: n = 20
Output: 1

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

class Solution {
public:
    int numDupDigitsAtMostN(int n) {
        return n - countUniqueDigitNumbers(n);
    }

private:
    int countUniqueDigitNumbers(int x) {
        string s = to_string(x);
        int n = s.size();
        int res = 0;
        for (int i = 1; i < n; ++i) {
            res += 9 * permutation(9, i - 1);
        }
        unordered_set<int> used;
        for (int i = 0; i < n; ++i) {
            for (int j = (i == 0 ? 1 : 0); j < s[i] - '0'; ++j) {
                if (used.find(j) == used.end()) {
                    res += permutation(9 - i, n - i - 1);
                }
            }
            if (used.find(s[i] - '0') != used.end()) {
                break;
            }
            used.insert(s[i] - '0');
        }
        if (used.size() == n) {
            res += 1;
        }
        return res;
    }

    int permutation(int m, int n) {
        return n == 0 ? 1 : permutation(m, n - 1) * (m - n + 1);
    }
};

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

5 свободных мест на курс Коммутаторы MES продвинутый Осталось 5 мест на курс Коммутаторы MES (продвинутый) в нашем авторизованном учебном центре от Академии Eltex в Москве Даты: 12-16 мая (5 дней) Другие курсы: Курс Wi-Fi (контроллер SoftWLC) 19 мая - 5 дней - Выдаем официальный сертификат Eltex. - Преподаватель корректирует программу обучения под Ваш уровень знаний. - Преподаватели прошли аттестацию на заводе Eltex. - Уже выпустили 210 сетевых инженеров! Записаться #реклама 16+ eltexcm.ru О рекламодателе

Задача: 1267. Count Servers that Communicate Сложность: medium На двумерной плоскости имеется n точек с целочисленными координатами points[i] = [xi, yi]. Верните минимальное время в секундах для посещения всех точек в порядке, заданном точками. Вы можете перемещаться по следующим правилам: за 1 секунду вы можете либо: переместиться по вертикали на одну единицу, по горизонтали на одну единицу, либо по диагонали sqrt(2) единиц (другими словами, переместиться на одну единицу по вертикали и на одну единицу по горизонтали за 1 секунду). Вы должны посетить точки в том же порядке, в котором они появляются в массиве. Вы можете проходить через точки, которые появляются позже в порядке, но они не считаются за посещение. Пример:

Input: grid = [[1,0],[0,1]]
Output: 0

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

class Solution {
public:
    int countServers(vector<vector<int>>& grid) {
        vector<int> rows(grid.size(), 0);
        vector<int> cols(grid[0].size(), 0);

        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 1) {
                    rows[i]++;
                    cols[j]++;
                }
            }
        }

        int count = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 1 && (rows[i] > 1 || cols[j] > 1)) {
                    count++;
                }
            }
        }

        return count;
    }
};

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

Крупнейший университет искусственного интеллекта Приглашаем на бесплатный курс по искусственному интеллекту! 5 занятий по теме «Промпт-инжиниринг». Регистрируйся для получения полного бесплатного доступа к курсу. ✨ 8 000+ студентов со всего мира ✨ 600+ AI-проектов, созданных студентами ✨ Сборная Университета — победители крупнейших AI-хакатонов России ✨ Стажировки в крупнейших компаниях России (РЖД, Ростелеком, РУДН, Совкомбанк, Самолет и другие) ✨ Трудоустраиваем выпускников в крупнейшие компании (Яндекс, ВТБ, Сбербанк, Роскосмос и другие) Будем рады видеть тебя в наших рядах! Узнать больше #реклама 16+ neural-university.ru О рекламодателе