C/C++ | LeetCode

Как навести порядок в IT-заявках? ⚡Бесплатный вебинар. Как создать прозрачную систему управления IT-заявками и сократить время обработки обращений с 8 часов до 15 минут. ✅ Бонус при регистрации: интерактивный чек-лист для аудита вашей IT-поддержки Экспресс-диагностика по 20 ключевым параметрам Сравнение ваших показателей со средними по рынку Персональные рекомендации по оптимизации Записаться онлайн #реклама 16+ promo.itilium.ru О рекламодателе

Задача: 378. Kth Smallest Element in a Sorted Matrix Сложность: medium Дана матрица размером 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;
    }
};

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

Курсы JAVA-разработки Гарантия ЗП от 120 000р в договоре Jаvа — это язык, на котором строятся банковские системы, мобильные приложения, крупные веб-сервисы и многое другое, а спрос на Jаvа-разработчиков стабильно высок. Благодаря кроссплатформенности и надежности, ты сможешь работать в любой сфере IТ — от финансов до Коммерческой отрасли.📊💰 Почему это работает?✨ - Минимальные вложения. - Тысячи человек уже в IТ. Наши выпускники работают в крутых компаниях: от стартапов до международных корпораций. - Наши менторы — это опытные разработчики, которые ежедневно работают в IТ и готовы делиться актуальными знаниями. P.S. Если всё ещё сомневаешься и думаешь что будет сложно — просто попробуй.😊 Мы берем на себя все риски: ты оплачиваешь основную стоимость обучения только после успешного трудоустройства — это закреплено в договоре. Подать заявку #реклама 16+ kata.academy О рекламодателе

Задача: 1110. Delete Nodes And Return Forest Сложность: medium Дан корень бинарного дерева, каждый узел в дереве имеет уникальное значение. После удаления всех узлов со значением из to_delete, остаётся лес (несвязное объединение деревьев). Верните корни деревьев в оставшемся лесу. Вы можете вернуть результат в любом порядке. Пример:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

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

class Solution {
    fun delNodes(root: TreeNode?, to_delete: IntArray): List<TreeNode?> {
        val toDeleteSet = to_delete.toSet()
        val forest = mutableListOf<TreeNode?>()

        fun processNode(node: TreeNode?): TreeNode? {
            if (node == null) return null

            node.left = processNode(node.left)
            node.right = processNode(node.right)

            if (toDeleteSet.contains(node.`val`)) {
                node.left?.let { forest.add(it) }
                node.right?.let { forest.add(it) }
                return null
            }
            return node
        }

        val root = processNode(root)
        if (root != null) forest.add(root)

        return forest
    }
}

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

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

Задача: 640. Solve the Equation Сложность: medium Решите заданное уравнение и верните значение 'x' в виде строки "x=#value". Уравнение содержит только операции '+', '-', переменную 'x' и ее коэффициент. Вы должны вернуть "No solution", если для уравнения нет решения, или "Infinite solutions", если для уравнения существует бесконечное количество решений. Если для уравнения существует ровно одно решение, мы убеждаемся, что значение 'x' является целым числом. Пример:

Input: s = "*"
Output: 9

👨‍💻 Алгоритм: 1⃣Разделение уравнения: Разделите уравнение на левую и правую части относительно знака равенства '='. 2⃣Парсинг и упрощение: Пройдитесь по каждой части уравнения, упрощая ее до суммы коэффициентов 'x' и числовых значений. 3⃣Решение уравнения: Используйте уравнение вида ax + b = cx + d, чтобы решить для 'x'. Если коэффициенты 'x' равны и числовые значения равны, уравнение имеет бесконечное количество решений. Если коэффициенты 'x' равны, но числовые значения различны, решения нет. В противном случае вычислите значение 'x'. 😎 Решение:

class Solution {
public:
    string solveEquation(string equation) {
        auto parse = [](const string& s) {
            int coeff = 0, constPart = 0, sign = 1, num = 0;
            int i = 0;
            while (i < s.size()) {
                if (s[i] == '+') {
                    sign = 1;
                    i++;
                } else if (s[i] == '-') {
                    sign = -1;
                    i++;
                } else if (isdigit(s[i])) {
                    num = 0;
                    while (i < s.size() && isdigit(s[i])) {
                        num = num * 10 + (s[i] - '0');
                        i++;
                    }
                    if (i < s.size() && s[i] == 'x') {
                        coeff += sign * num;
                        i++;
                    } else {
                        constPart += sign * num;
                    }
                } else if (s[i] == 'x') {
                    coeff += sign;
                    i++;
                }
            }
            return make_pair(coeff, constPart);
        };

        auto [leftCoeff, leftConst] = parse(equation.substr(0, equation.find('=')));
        auto [rightCoeff, rightConst] = parse(equation.substr(equation.find('=') + 1));

        int coeff = leftCoeff - rightCoeff;
        int constPart = rightConst - leftConst;

        if (coeff == 0) {
            return constPart == 0 ? "Infinite solutions" : "No solution";
        }
        return "x=" + to_string(constPart / coeff);
    }
};

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

Современная магистратура от Центрального университета Хочешь развиваться в сфере ИТ и получить фундаментальные знания с практикой? Поступай в магистратуру Центрального университета! - 4 офлайн программы по востребованным направлениям ИТ - Онлайн-программа по машинному обучению - 300 мест с грантами до 1,2 млн руб. - Вечерние занятия и учеба по выходным — удобно совмещать с работой - Обучение по модели STEM-образования: на стыке науки, технологий и бизнеса - Возможность стажировок и трудоустройства в ведущих компаниях - Государственный диплом за 2 года Магистратура в Центральном университете — это современный подход к образованию, сильный преподавательский состав и актуальные кейсы от индустрии. Оставляй заявку на грант уже сейчас! Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 917. Reverse Only Letters Сложность: easy Задав строку s, переверните ее в соответствии со следующими правилами: все символы, не являющиеся английскими буквами, остаются в той же позиции. Все английские буквы (строчные или прописные) должны быть перевернуты. Верните s после перевертывания. Пример:

Input: s = "ab-cd"
Output: "dc-ba"

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

class Solution {
public:
    string reverseOnlyLetters(string s) {
        vector<char> letters;
        for (char c : s) {
            if (isalpha(c)) {
                letters.push_back(c);
            }
        }
        reverse(letters.begin(), letters.end());
        string result;
        int idx = 0;
        for (char c : s) {
            if (isalpha(c)) {
                result += letters[idx++];
            } else {
                result += c;
            }
        }
        return result;
    }
};

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

Дарим подписку на Яндекс Музыку Ответьте на 1 вопрос и Яндекс Музыка ваша для вас и 3-х ваших близких. Кинопоиск и Яндекс Книги тоже в подписке. Попробуйте бесплатно❤️ Попробовать #реклама 18+ music.yandex.ru О рекламодателе Реклама на Яндексе

📺 Уникальная база IT собеседований 456+ реальных собеседований на программиста, тестировщика, аналитика и прочие IT профы. Есть собесы от ведущих компаний: Сбер, Яндекс, ВТБ, Тинькофф, Озон, Wildberries и т.д. 🎯 Переходи по ссылке и присоединяйся к базе, чтобы прокачать свои шансы на успешное трудоустройство!

Задача: 1198. Find Smallest Common Element in All Rows Сложность: medium Дана матрица mat размером m x n, где каждая строка отсортирована в строго возрастающем порядке. Верните наименьший общий элемент во всех строках. Если общего элемента нет, верните -1. Пример:

Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
Output: 5

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

class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        vector<int> pos(n, 0);
        int cur_max = 0, cnt = 0;
        
        while (true) {
            for (int i = 0; i < n; ++i) {
                while (pos[i] < m && mat[i][pos[i]] < cur_max) {
                    ++pos[i];
                }
                if (pos[i] >= m) {
                    return -1;
                }
                if (mat[i][pos[i]] != cur_max) {
                    cnt = 1;
                    cur_max = mat[i][pos[i]];
                } else if (++cnt == n) {
                    return cur_max;
                }
            }
        }
    }
};

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

Получи грант на обучение в Центральном университете Прояви себя, получи грант до 2,8 млн на обучение ИТ и бизнесу в вузе. Для школьников 10-х и 11-х классов, СПО. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

Задача: 190. Reverse Bits Сложность: easy Переверните биты заданного 32-битного беззнакового целого числа. Пример:

Input: n = 00000010100101000001111010011100 Output: 964176192 (00111001011110000010100101000000)

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

class Solution {
public:
    uint32_t reverseByte(uint32_t byte, map<uint32_t, uint32_t> cache) {
        if (cache.find(byte) != cache.end()) {
            return cache[byte];
        }
        uint32_t value = (byte * 0x0202020202 & 0x010884422010) % 1023;
        cache.emplace(byte, value);
        return value;
    }

    uint32_t reverseBits(uint32_t n) {
        uint32_t ret = 0, power = 24;
        map<uint32_t, uint32_t> cache;
        while (n != 0) {
            ret += reverseByte(n & 0xff, cache) << power;
            n = n >> 8;
            power -= 8;
        }
        return ret;
    }
};

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

Битрикс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;
    }
};

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