C/C++ | LeetCode

Задача: 459. Repeated Substring Pattern Сложность: easy Дана строка s, проверьте, может ли она быть построена путем взятия подстроки и добавления нескольких копий этой подстроки друг за другом. Пример:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

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

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.length();
        for (int i = 1; i <= n / 2; i++) {
            if (n % i == 0) {
                string pattern = "";
                for (int j = 0; j < n / i; j++) {
                    pattern += s.substr(0, i);
                }
                if (s == pattern) {
                    return true;
                }
            }
        }
        return false;
    }
};

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

Бесплатный курс по 3D-моделированию с нуля Начни карьеру в дизайне и получи первую зарплату! Вас ждет реальный рабочий процесс: ✅ разные задачи по 3D Blander ✅ опыт общения с клиентами ✅ оплата за проект Освойте Blender и создайте работу для портфолио Обучение полностью бесплатное для первых 70 участников. Осталось 28 мест. В конце курса мы откроем для вас доступ к звездной распродаже Там вы сможете обменять звездочки на ценные бонусы: 1. Гайд по выходу на биржу UpWork 2. Курс «Заработок на дизайне» 3. Анимированный концепт Samsung True для портфолио 4. Бессрочный грант на обучение: 15 000 ₽ 5. Гайд «Горячие клавиши в Blender» Записывайтесь сейчас! Узнать больше #реклама 16+ yudaevschool24.online О рекламодателе

Задача: 1318. Minimum Flips to Make a OR b Equal to c Сложность: medium Даны три положительных числа a, b и c. Верните минимальное количество переворотов, необходимых в некоторых битах a и b, чтобы сделать (a OR b == c) (побитовая операция OR). Операция переворота состоит из изменения любого отдельного бита с 1 на 0 или с 0 на 1 в их двоичном представлении. Пример:

Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)

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

class Solution {
public:
    int minFlips(int a, int b, int c) {
        int answer = 0;
        while (a != 0 || b != 0 || c != 0) {
            if ((c & 1) == 1) {
                if ((a & 1) == 0 && (b & 1) == 0) {
                    answer++;
                }
            } else {
                answer += (a & 1) + (b & 1);
            }
            a >>= 1;
            b >>= 1;
            c >>= 1;
        }
        return answer;
    }
};

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

Как эффективно работать с интеграциями сегодня? Узнайте 5 июня на бесплатном вебинаре СберТеха «Новый взгляд на интеграционный ландшафт: как микросервисы меняют правила игры». Эксперты из Neoflex и СберТеха познакомят вас с инструментами для создания и управления интеграциями. А также поделятся опытом реализации проектов на базе решений от IBM и open source технологий. Регистрируйтесь и получите доступ к информации и рекомендациям от экспертов рынка! Зарегистрироваться #реклама 16+ platformv.sbertech.ru О рекламодателе

Задача: 400. Nth Digit Сложность: medium Дано целое число n, вернуть n-ю цифру бесконечной последовательности чисел [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]. Пример:

Input: n = 3
Output: 3

👨‍💻 Алгоритм: 1⃣Определение диапазона: Начните с определения количества цифр в числах текущего диапазона (1-9, 10-99, 100-999 и т.д.). Уменьшайте значение n, вычитая количество цифр в текущем диапазоне, пока не найдете диапазон, в который попадает n-я цифра. 2⃣Нахождение конкретного числа: Когда определите диапазон, найдите точное число, содержащее n-ю цифру. Определите индекс цифры в этом числе. 3⃣Возвращение n-й цифры: Извлеките и верните n-ю цифру из найденного числа. 😎 Решение:

class Solution {
public:
    int findNthDigit(int n) {
        long length = 1, count = 9, start = 1;
        while (n > length * count) {
            n -= length * count;
            length++;
            count *= 10;
            start *= 10;
        }
        start += (n - 1) / length;
        string s = to_string(start);
        return s[(n - 1) % length] - '0';
    }
};

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

Освойте профессию Системный аналитик с нуля за 7 месяцев Освойте высокооплачиваемую IT-профессию без программирования. Выдаём диплом, помогаем с трудоустройством. Excel, BPMN, UML, Python, SQL, API Преимущества обучения в Академии Eduson: 🎓 22 реальных бизнес-кейса 🎓 официальный государственный диплом 🎓 рассрочка 0% на 24 мес. 🎓 бессрочный доступ к лекциям и материалам, которые регулярно обновляются 🎓 личный куратор с Вами на связи Начните обучаться онлайн и получать доход уже во время обучения! Получить скидку #реклама 16+ mrqz.me О рекламодателе

Задача: 1103. Distribute Candies to People Сложность: easy Мы распределяем некоторое количество конфет ряду из n = num_people человек следующим образом: Сначала даем 1 конфету первому человеку, 2 конфеты второму человеку и так далее, пока не дадим n конфет последнему человеку. Затем мы возвращаемся к началу ряда, давая n + 1 конфету первому человеку, n + 2 конфеты второму человеку и так далее, пока не дадим 2 * n конфет последнему человеку. Этот процесс повторяется (мы каждый раз даем на одну конфету больше и возвращаемся к началу ряда после достижения конца), пока у нас не закончатся конфеты. Последний человек получит все оставшиеся конфеты (не обязательно на одну больше, чем в предыдущий раз). Верните массив (длиной num_people и суммой candies), который представляет собой окончательное распределение конфет. Пример:

Input: candies = 7, num_people = 4
Output: [1,2,3,1]
Explanation:
On the first turn, ans[0] += 1, and the array is [1,0,0,0].
On the second turn, ans[1] += 2, and the array is [1,2,0,0].
On the third turn, ans[2] += 3, and the array is [1,2,3,0].
On the fourth turn, ans[3] += 1 (because there is only one candy left), and the final array is [1,2,3,1].

👨‍💻 Алгоритм: 1⃣Вычислите количество людей, получивших полные подарки, и оставшиеся конфеты: p = floor(sqrt(2C+0.25)-0.5) remainig = C - p(p+1)/2 2⃣Вычислите количество полных циклов и распределите конфеты: rows = p // n d[i]= i*rows + n*rows*(rows-1)/2 3⃣Добавьте конфеты за дополнительный неполный цикл и оставшиеся конфеты: d[i]+=i+n⋅rows для первых p%n людей d[p%n]+=remaining Верните распределение конфет d 😎 Решение:

class Solution {
public:
    vector<int> distributeCandies(int candies, int num_people) {
        int n = num_people;
        int p = int(sqrt(2 * candies + 0.25) - 0.5);
        int remaining = candies - (p + 1) * p / 2;
        int rows = p / n;
        int cols = p % n;
        
        vector<int> d(n, 0);
        for (int i = 0; i < n; i++) {
            d[i] = (i + 1) * rows + (rows * (rows - 1) / 2) * n;
            if (i < cols) {
                d[i] += i + 1 + rows * n;
            }
        }
        d[cols] += remaining;
        return d;
    }
};

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

Распродажа на Stepik. Соберите все скидки весны! Stepik объявляет масштабную весеннюю распродажу.⚡ Она пройдет с 20 мая по 2 июня 2025 года и распространяется на курсы по программированию, аналитике, маркетингу, дизайну, иностранным языкам и пр. Это отличная возможность, если вы хотите: — Освоить новую профессию, например начать погружение в мир IT — Научиться играть на музыкальном инструменте, писать книги или стать увереннее в публичных выступлениях — Освоить новую технологию или инструмент, например работу с ИИ Не пропустите главное событие первой половины 2025 года на Stepik: переходите в наш уютный каталог найдите свой курс😊 Купить #реклама 16+ stepik.org О рекламодателе

Задача: 979. Distribute Coins in Binary Tree Сложность: medium Вам дан корень бинарного дерева с n узлами, где каждый узел в дереве содержит node.val монет. Всего по всему дереву распределено n монет. За один ход мы можем выбрать два смежных узла и переместить одну монету из одного узла в другой. Ход может быть как от родителя к ребенку, так и от ребенка к родителю. Верните минимальное количество ходов, необходимых для того, чтобы каждый узел имел ровно одну монету. Пример:

Input: root = [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.

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

class Solution {
public:
    int distributeCoins(TreeNode* root) {
        moves = 0;
        dfs(root);
        return moves;
    }

private:
    int moves;

    int dfs(TreeNode* current) {
        if (current == nullptr) return 0;
        int leftCoins = dfs(current->left);
        int rightCoins = dfs(current->right);
        moves += abs(leftCoins) + abs(rightCoins);
        return current->val - 1 + leftCoins + rightCoins;
    }
};

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

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

Задача: 734. Sentence Similarity Сложность: easy Мы можем представить предложение в виде массива слов, например, предложение "I am happy with leetcode" можно представить как arr = ["I", "am",happy", "with", "leetcode"]. Даны два предложения sentence1 и sentence2, каждое из которых представлено в виде массива строк, и массив пар строк similarPairs, где similarPairs[i] = [xi, yi] указывает, что два слова xi и yi похожи. Возвращается true, если предложения sentence1 и sentence2 похожи, или false, если они не похожи. Два предложения похожи, если: у них одинаковая длина (т.е, Заметьте, что слово всегда похоже само на себя, также обратите внимание, что отношение сходства не является транзитивным. Например, если слова a и b похожи, а слова b и c похожи, то a и c не обязательно похожи. Пример:

Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true

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

class Solution {
public:
    bool areSentencesSimilar(vector<string>& sentence1, vector<string>& sentence2, vector<vector<string>>& similarPairs) {
        if (sentence1.size() != sentence2.size()) {
            return false;
        }

        unordered_map<string, unordered_set<string>> similar;
        for (const auto& pair : similarPairs) {
            similar[pair[0]].insert(pair[1]);
            similar[pair[1]].insert(pair[0]);
        }

        for (int i = 0; i < sentence1.size(); ++i) {
            const string& w1 = sentence1[i];
            const string& w2 = sentence2[i];
            if (w1 != w2 && (similar[w1].find(w2) == similar[w1].end())) {
                return false;
            }
        }

        return true;
    }
};

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

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

Задача: 1273. Delete Tree Nodes Сложность: medium Дерево, укорененное в узле 0, задано следующим образом: количество узлов - nodes; значение i-го узла - value[i]; родитель i-го узла - parent[i]. Удалите все поддеревья, сумма значений узлов которых равна нулю. Верните количество оставшихся узлов в дереве. Пример:

Input: nodes = 7, parent = [-1,0,0,1,2,2,2], value = [1,-2,4,0,-2,-1,-1]
Output: 2

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

class Solution {
public:
    int deleteTreeNodes(int nodes, vector<int>& parent, vector<int>& value) {
        unordered_map<int, vector<int>> tree;
        for (int i = 0; i < nodes; ++i) {
            tree[parent[i]].push_back(i);
        }

        return dfs(0, tree, value).second;
    }

private:
    pair<int, int> dfs(int node, unordered_map<int, vector<int>>& tree, vector<int>& value) {
        int totalSum = value[node];
        int totalCount = 1;
        for (int child : tree[node]) {
            auto [childSum, childCount] = dfs(child, tree, value);
            totalSum += childSum;
            totalCount += childCount;
        }
        if (totalSum == 0) {
            return {0, 0};
        }
        return {totalSum, totalCount};
    }
};

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

Привет ребят! Мне в последнее время пишет очень много начинающих предпринимателей оценить их бизнес со стороны. Я как человек с 10 годами опыта в создании стартапов, как успеших так и абсолютно убыточных могу дать свою оценку. Я продавал свой бизнес в прибыль, и я также в убыток продовал несколько своих проектов. Готов с вами обсудить ваши идеи, но только сейчас, пока я пьян и на веселе. Напишите @kivaiko и мы созвонимся, чтобы я трезво оценивал ваши шансы и дал экспертные рекомендации.

Онлайн-магистратура "Науки о данных". Ваш рост в IT! ✅ТОП-1 тех.вуз РФ ✅Диплом магистра ✅Карьера в топ-компаниях ✅Запуск стартапа ✅+2 диплома ДПО Data Science, МФТИ — среда для профессионального и карьерного роста в IT! Записаться онлайн #реклама 16+ mipt.online О рекламодателе

Задача: 34. Find First and Last Position of Element in Sorted Array Сложность: medium Учитывая отсортированный по не убыванию массив целых чисел nums, необходимо найти начальную и конечную позиции заданного значения target. Если значение не найдено, вернуть [-1, -1]. Алгоритм должен работать за O(log n). Пример:

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]

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

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans{-1,-1};
        auto l = lower_bound(nums.begin(), nums.end(), target);
        auto r = upper_bound(nums.begin(), nums.end(), target);
        if (l != nums.end() && *l == target) {
            ans[0] = l - nums.begin();
            ans[1] = r - nums.begin() - 1;
        }
        return ans;
    }
};

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

PostgreSQL как сервис: что это и как применяется? Сервис PostgreSQL от РТК-ЦОД позволяет быстро развернуть, эксплуатировать и масштабировать базу данных в облаке. Процесс установки и настройки полностью автоматизирован. Как наши клиенты используют PostgreSQL? — Работают в 1С — Управляют платежными системами — Ведут финансовый учет — Собирают геоданные — Работают с данными со сложной структурой — Анализируют большие массивы данных ✅30 дней бесплатно: тестируйте наш сервис с полным доступом ко всем возможностям. Оставьте заявку на www.cloud.rt.ru Узнать больше #реклама 16+ cloud.rt.ru О рекламодателе

Задача: 85. Maximal Rectangle Сложность: hard Дана бинарная матрица размера rows x cols, заполненная '0' и '1'. Найдите наибольший прямоугольник, содержащий только '1', и верните его площадь. Пример:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6

👨‍💻 Алгоритм: 1⃣Для каждой строки i считаем количество подряд идущих '1' слева от текущей ячейки, т.е. если matrix[i][j] == '1', то dp[i][j] = dp[i][j-1] + 1 (иначе 0). 2⃣Для каждой единицы на позиции (i,j) идём вверх по столбцу, накапливая минимальную ширину width, и вычисляем площадь текущего прямоугольника width * высота, обновляя максимум. 3⃣Повторяем для всех ячеек, возвращаем наибольшую найденную площадь. 😎 Решение:

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.size() == 0) return 0;
        int maxarea = 0;
        vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(), 0));

        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = j == 0 ? 1 : dp[i][j - 1] + 1;
                    int width = dp[i][j];
                    for (int k = i; k >= 0; k--) {
                        width = std::min(width, dp[k][j]);
                        maxarea = std::max(maxarea, width * (i - k + 1));
                    }
                }
            }
        }
        return maxarea;
    }
};

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

ПСК 5,046% - 29,191%. Ипотека от 5% для всех! Это не семейная программа. А комфортная ставка, которой могут воспользоваться даже пары без детей или холостяки. И оформить квартиру от 16 200 руб/мес в ЖК «Мотивы». Если не хочется переплачивать даже за ипотеку под 5%, выберите один из вариантов беспроцентной рассрочки: 1. С первым платежом от 260 000 ₽ на двух- или трехкомнатную квартиру. 2. Длительная рассрочка на год! Оставьте заявку на сайте, чтобы узнать подробности и получить планировки. Перейти на сайт Изучите все условия кредита (займа) на сайте в соответствующем разделе. Оценивайте свои финансовые возможности и рискиПроектная декларация на сайте https://наш.дом.рф/. Застройщик: ООО "СЗ "ИСБ Девелопмент". Финансовые услуги оказывает: ПАО Сбербанк. #реклама zhk-motivy.rqch.ru О рекламодателе

Задача: 330. Patching Array Сложность: hard Дан отсортированный массив целых чисел nums и целое число n. Добавьте/дополните элементы в массив таким образом, чтобы любое число в диапазоне [1, n] включительно могло быть сформировано как сумма некоторых элементов массива. Верните минимальное количество дополнений, необходимых для этого. Пример:

Input: nums = [1,3], n = 6
Output: 1
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

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

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        int patches = 0, i = 0;
        long miss = 1;
        while (miss <= n) {
            if (i < nums.size() && nums[i] <= miss) {
                miss += nums[i++];
            } else {
                miss += miss;
                patches++;
            }
        }
        return patches;
    }
};

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