C/C++ | LeetCode

Задача: 1248. Count Number of Nice Subarrays Сложность: medium Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать. Пример:

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

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

class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }

private:
    int atMost(vector<int>& nums, int k) {
        int res = 0, left = 0, count = 0;
        for (int right = 0; right < nums.size(); right++) {
            if (nums[right] % 2 == 1) count++;
            while (count > k) {
                if (nums[left++] % 2 == 1) count--;
            }
            res += right - left + 1;
        }
        return res;
    }
};

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

Хочешь новую профессию? Тогда по-взрослому: Психология — это не магия, не эзотерика и не «послушаю подругу за чашкой чая». Это профессия. С методами, практикой, реальными людьми и ответственностью. И ты можешь её освоить за 12 месяцев — без воды. Что конкретно ты получаешь: – 1200 часов системного обучения – 450 часов реальной практики: тренажёры, клиенты, супервизии – Занятия в мини-группах с наставниками – Диплом о проф. переподготовке + международный диплом MBA – Запуск частной практики уже в процессе обучения Всё обучение — онлайн. Гибко, но не халтурно. Через 12 месяцев — ты не в «поиске себя», а в новой профессии. С дипломом. С навыками. С первыми клиентами. С направлением. Посмотри программу. Реши — идёшь или нет. ✅ Начни учиться бесплатно прямо сегодня! Зарегистрироваться #реклама 16+ psy.talentsy.ru О рекламодателе

Задача: 345. Reverse Vowels of a String Сложность: easy Дана строка s, переверните только все гласные в строке и верните её. Гласные: 'a', 'e', 'i', 'o', 'u', а также их верхние регистры. Пример:

Input: s = "hello"
Output: "holle"

👨‍💻 Алгоритм: 1⃣Инициализация указателей и гласных: Создайте набор гласных для быстрой проверки. Установите два указателя: один на начало строки (left), другой на конец строки (right). 2⃣Перестановка гласных: Пока левый указатель меньше правого, перемещайте указатели к центру, пока не найдёте гласные. Обменивайте найденные гласные и продолжайте сдвигать указатели. 3⃣Завершение работы: Когда указатели пересекутся, остановите процесс и верните строку. 😎 Решение:

class Solution {
public:
    string reverseVowels(string s) {
        unordered_set<char> vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};
        int left = 0, right = s.size() - 1;
        
        while (left < right) {
            if (vowels.find(s[left]) == vowels.end()) {
                left++;
            } else if (vowels.find(s[right]) == vowels.end()) {
                right--;
            } else {
                swap(s[left], s[right]);
                left++;
                right--;
            }
        }
        
        return s;
    }
};

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

Обучение трейдингу для новичков и профессиналов Изучайте слайды с основными темами, смотрите видео и практикуйтесь. Торгуйте на рынке как профи! Зарегистрироваться #реклама 16+ fxproru.pro О рекламодателе

Задача: 1302. Deepest Leaves Sum Сложность: medium Дано корень бинарного дерева, вернуть сумму значений его самых глубоких листьев. Пример:

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

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

class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
        int deepestSum = 0, depth = 0, currDepth;
        stack<pair<TreeNode*, int>> stack;
        stack.push({root, 0});

        while (!stack.empty()) {
            auto [node, currDepth] = stack.top();
            stack.pop();

            if (!node->left && !node->right) {
                if (depth < currDepth) {
                    deepestSum = node->val;
                    depth = currDepth;
                } else if (depth == currDepth) {
                    deepestSum += node->val;
                }
            } else {
                if (node->right) {
                    stack.push({node->right, currDepth + 1});
                }
                if (node->left) {
                    stack.push({node->left, currDepth + 1});
                }
            }
        }
        return deepestSum;
    }
};

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

Ищешь высокооплачиваемые проекты? Попробуй SkillStaff SkillStaff — это платформа для ИТ-специалистов, менеджеров и креаторов, которым мало одного оклада. Здесь можно найти клиентов, выполнять их проекты и увеличивать свой доход. - Проекты с гибким графиком: part time, full time, удаленка и гибрид - Ставка за час работы — та, что ты сам выбрал - Клиенты — ведущие бренды, проверенные с юридической точки зрения при регистрации на платформе - Оплата поступает ежемесячно на расчетный счет исполнителя - Удобный личный кабинет и функционал, автоматизирующий документооборот Все, что нужно для работы — иметь статус самозанятого или ИП, а платформа поможет со всеми нюансами. Регистрируйся прямо сейчас Зарегистрироваться #реклама 16+ skillstaff.ru О рекламодателе

Задача: 918. Maximum Sum Circular Subarray Сложность: medium Если задан круговой целочисленный массив nums длины n, верните максимально возможную сумму непустого подмассива nums. Круговой массив означает, что конец массива соединяется с его началом. Формально, следующий элемент nums[i] равен nums[(i + 1) % n], а предыдущий элемент nums[i] равен nums[(i - 1 + n) % n]. Подмассив может включать каждый элемент фиксированного буфера nums не более одного раза. Формально, для подмассива nums[i], nums[i + 1], ..., nums[j] не существует i <= k1, k2 <= j, при этом k1 % n == k2 % n. Пример:

Input: nums = [1,-2,3,-2]
Output: 3

👨‍💻 Алгоритм: 1⃣Найти стандартную максимальную сумму подмассива с помощью алгоритма Кадане. 2⃣Найти минимальную сумму подмассива с помощью алгоритма Кадане и вычесть ее из общей суммы массива. 3⃣Вернуть максимум между стандартной максимальной суммой подмассива и общей суммой массива минус минимальную сумму подмассива, если результат не равен 0 (чтобы учесть случай, когда все числа отрицательные). 😎 Решение:

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        int kadane(vector<int>& arr) {
            int currentSum = arr[0], maxSum = arr[0];
            for (int i = 1; i < arr.size(); ++i) {
                currentSum = max(arr[i], currentSum + arr[i]);
                maxSum = max(maxSum, currentSum);
            }
            return maxSum;
        }

        int maxKadane = kadane(nums);
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        for (int& num : nums) num = -num;
        int minKadane = kadane(nums);

        return max(maxKadane, totalSum + minKadane == 0 ? maxKadane : totalSum + minKadane);
    }
};

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

Задача: 974. Subarray Sums Divisible by K Сложность: medium Дан целочисленный массив nums и целое число k. Верните количество непустых подмассивов, сумма которых делится на k. Подмассив — это непрерывная часть массива. Пример:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

👨‍💻 Алгоритм: 1⃣Инициализация и подготовка. Инициализируйте prefixMod = 0 для хранения остатка от суммы элементов до текущего индекса при делении на k. Инициализируйте result = 0 для хранения количества подмассивов, сумма которых делится на k. Инициализируйте массив modGroups длиной k, где modGroups[R] хранит количество подмассивов с остатком R. Установите modGroups[0] = 1. 2⃣Итерирование по массиву. Для каждого элемента массива nums вычислите новый prefixMod как (prefixMod + nums[i] % k + k) % k, чтобы избежать отрицательных значений. Увеличьте result на значение modGroups[prefixMod], чтобы добавить количество подмассивов с текущим остатком. Увеличьте значение modGroups[prefixMod] на 1 для будущих совпадений. 3⃣Возврат результата. Верните значение result, которое содержит количество подмассивов, сумма которых делится на k. 😎 Решение:

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int prefixMod = 0, result = 0;
        vector<int> modGroups(k);
        modGroups[0] = 1;

        for (int num : nums) {
            prefixMod = (prefixMod + num % k + k) % k;
            result += modGroups[prefixMod];
            modGroups[prefixMod]++;
        }

        return result;
    }
};

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

80 лет назад: хроники Победы Собрали самое главное: ✨ Военные сводки и хроники с фронта ✨ Герои и их подвиги ✨ Культура 1941—1945 годов ✨ Настоящие новости тех лет Перейти на сайт #реклама 16+ dzen.ru О рекламодателе

Задача: 1024. Video Stitching Сложность: medium Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается массивом clips, где clips[i] = [starti, endi] указывает, что i-й клип начинается в starti и заканчивается в endi. Мы можем произвольно разрезать эти клипы на сегменты. Например, клип [0, 7] может быть разрезан на сегменты [0, 1] + [1, 3] + [3, 7]. Верните минимальное количество клипов, необходимое для того, чтобы мы могли разрезать клипы на сегменты, охватывающие все спортивное событие [0, время]. Если задача невыполнима, верните -1. Пример:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3

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

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int T) {
        sort(clips.begin(), clips.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
        });
        int end = -1, end2 = 0, res = 0;
        for (const auto& clip : clips) {
            if (end2 >= T || clip[0] > end2) break;
            if (end < clip[0] && clip[0] <= end2) {
                res++;
                end = end2;
            }
            end2 = max(end2, clip[1]);
        }
        return end2 >= T ? res : -1;
    }
};

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

Виртуальный сервер в аренду в Турции или России. Отказоустойчивый виртуальный облачный сервер на базе виртуализации VMWARE по модели подписки. - Бесплатная миграция инфраструктуры в Турцию - Размещайте ресурсы в Турции или России и оплачивайте в рублях, турицких лирах или евро. - Храните резервные копии данных за рубежом для минимизации рисков - Продолжайте использовать импортное ПО, скачивайте обновления и патчи, общайтесь с техподдержкой - Доступность сервиса — от 99,982% SLA - Дата центры Tier III в России и Турции - Почасовой биллинг и постоплата Подключите услугу сегодня со скидкой 50% на инфраструктуру. Подать заявку #реклама cloud4y.ru О рекламодателе

Задача: 1510. Stone Game IV Сложность: hard Алиса и Боб поочередно играют в игру, причем Алиса начинает первой. Изначально в куче n камней. В ходе каждого хода игрок удаляет любое ненулевое количество камней, являющееся квадратом целого числа. Кроме того, если игрок не может сделать ход, он/она проигрывает игру. Дано положительное целое число n, верните true, если и только если Алиса выиграет игру, иначе верните false, предполагая, что оба игрока играют оптимально. Пример:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.

👨‍💻 Алгоритм: 1⃣Функция dfs(remain) представляет собой проверку, должен ли текущий игрок выиграть при оставшихся remain камнях. 2⃣Для определения результата dfs(n) необходимо итерировать k от 0, чтобы проверить, существует ли такое k, что dfs(remain - k*k) == False. Чтобы предотвратить избыточные вычисления, используйте карту для хранения результатов функции dfs. 3⃣Не забудьте базовые случаи: dfs(0) == False и dfs(1) == True. 😎 Решение:

class Solution {
public:
    bool winnerSquareGame(int n) {
        unordered_map<int, bool> cache;
        cache[0] = false;
        return dfs(cache, n);
    }

    bool dfs(unordered_map<int, bool>& cache, int remain) {
        if (cache.find(remain) != cache.end()) {
            return cache[remain];
        }
        int sqrt_root = (int) sqrt(remain);
        for (int i = 1; i <= sqrt_root; ++i) {
            if (!dfs(cache, remain - i * i)) {
                cache[remain] = true;
                return true;
            }
        }
        cache[remain] = false;
        return false;
    }
};

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

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

Задача: 122. Best Time to Buy and Sell Stock II Сложность: medium Вам дан массив целых чисел prices, где prices[i] — это цена акции в i-й день. Каждый день вы можете купить и/или продать акцию, но держать в руках можно только одну. Разрешено покупать и продавать в тот же день. Найдите и верните максимальную прибыль, которую можно получить. Пример:

Input: prices = [7,1,5,3,6,4] Output: 7
Explanation:
Купить на 2-й день (цена = 1), продать на 3-й (цена = 5), прибыль = 4
Купить на 4-й день (цена = 3), продать на 5-й (цена = 6), прибыль = 3
Итоговая прибыль = 4 + 3 = 7

👨‍💻 Алгоритм: 1⃣Найдём все возрастающие отрезки (впадина → пик), и прибавим к прибыли разницу между пиком и впадиной. 2⃣Не стоит пытаться найти один глобальный минимум и максимум — это уменьшит прибыль. Лучше учитывать все локальные сделки, даже если они малы. 3⃣Реализуем проход по массиву: Ищем впадину (где цена начинает расти) Затем ищем пик (где рост заканчивается) Добавляем разницу в maxprofit Повторяем до конца 😎 Решение:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int i = 0;
        int valley = prices[0];
        int peak = prices[0];
        int maxprofit = 0;

        while (i < prices.size() - 1) {
            while (i < prices.size() - 1 && prices[i] >= prices[i + 1]) i++;
            valley = prices[i];

            while (i < prices.size() - 1 && prices[i] <= prices[i + 1]) i++;
            peak = prices[i];

            maxprofit += peak - valley;
        }

        return maxprofit;
    }
};

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

Задача: 240. Search a 2D Matrix II Сложность: medium Целые числа в каждой строке отсортированы по возрастанию слева направо Целые числа в каждом столбце отсортированы по возрастанию сверху вниз Пример:

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 Output: true

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

class Solution {
public:
    bool binarySearch(vector<vector<int>>& matrix, int target, int start, bool vertical) {
        int lo = start;
        int hi = vertical ? matrix[0].size() - 1 : matrix.size() - 1;

        while (hi >= lo) {
            int mid = (lo + hi) / 2;
            if (vertical) {
                if (matrix[start][mid] < target) {
                    lo = mid + 1;
                } else if (matrix[start][mid] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            } else {
                if (matrix[mid][start] < target) {
                    lo = mid + 1;
                } else if (matrix[mid][start] > target) {
                    hi = mid - 1;
                } else {
                    return true;
                }
            }
        }
        return false;
    }

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;

        int shorterDim = min(matrix.size(), matrix[0].size());
        for (int i = 0; i < shorterDim; i++) {
            if (binarySearch(matrix, target, i, true) || binarySearch(matrix, target, i, false)) {
                return true;
            }
        }
        return false;
    }
};

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

Я смотрю на эту цифру и до сих пор не верю. Когда я запускал этот проект, мне реально было страшно. Страшно, что ничего не получится. Что я и мой проект никому не нужен. Страшно, что все увидят, как я публично обосрался. Я ставил планку в 300т рублей. В самом позитивном сценарии 1млн. Но про 5 миллионов… даже мысли не было. Уже в первые часы стало понятно, что кампания идет не по плану. Сайт краудфандинга не выдержал нашей нагрузки и лег 😁 Особенно в последние три дня — просто какой-то разрыв! Я ощущал, как будто ловлю попутный ветер. В последний час не хватало 50к до 5 млн, и я уже думал сам их докинуть, чтобы красиво закрыть 😁 Но финальная сумма это не так важно. Самое главное это как мы её собрали. Это не инвестиции, не чьи-то деньги под условия и контроль, не кредит. Это вы поверили и поддержали меня напрямую. Вы дали мне возможность оставить за собой полный контроль над easyoffer. Я чувствую огромную ответственность и нервничаю из-за высоких ожиданий. А вдруг что-то пойдёт не так? А вдруг на релизе кому-то что-то не понравится? Именно поэтому я рад, что могу честно выйти на новый этап и без давления от левых инвесторов. В такие моменты вспоминаю, с чего всё начиналось. Как 2 года назад я писал свои первые посты на 500 человек о том, как учу программирование. Как записывал первое видео на YouTube про поиск работы. Как пилил первую версию easyoffer, вообще без понимания, что из этого выйдет. И сейчас я думаю — может, эта история вдохновит кого-то из вас. Может, кто-то запустит свой айтишный проект, найдёт поддержку и соберёт бабки на развитие. Было бы круто Спасибо за невероятную и колосальную поддержку ❤️ О такой аудитории как вы я не мог мечтать

Почему вы не используете Битрикс24 CRM с AI? 1- не знал 2- забыл Рассказываем и напоминаем! ✅Битрикс24 CRM с AI помогает увеличивать продажи, работать с постоянными клиентами и сохранять все важные данные. AI-помощник CoPilot внутри сервиса расшифрует телефонные разговоры и автоматически заполнит карточки клиента в CRM. Битрикс24 можно использовать бесплатно для всех команд, независимо от их размера. ⚡Не тратьте время на рутину. Узнать больше #реклама 16+ bitrix24.ru О рекламодателе

🚨 60 минут до финала Через час мы закроем краудфандинг easyoffer 2.0 Это последний шанс вписаться в самые выгодные условия. 👉 https://planeta.ru/campaigns/easyoffer

Финальный отсчёт: 3 часа до конца краудфандинга easyoffer 2.0! Это не просто скидка. Это шанс поддержать проект, который поможет и вам и тысячам айтишников готовиться к собеседованиям быстрее, эффективнее и увереннее. За последние недели: 💥 Нас поддержали уже больше 1450 человек; 🔥 Вместе собрали больше 4,5 млн. рублей на запуск проекта; Но сейчас важнее другое. ⏳ Через 3 часа всё закончится. – Больше не будет подписки за 3 200 руб. на целый год! – Не будет шанса первыми воспользоваться EasyOffer 2.0 на бета-тестировании Если вы: + Планируете менять работу в этом или следующем году; + Хотите иметь под рукой 40,000+ вопросов собеседований с разборами, видео-ответами и тренажёрами; + Хотите зафиксировать лучшую цену на целый год… (потом будет в 12 раз дороже) 👉 Тогда просто переходите и поддержите нас сейчас: https://planeta.ru/campaigns/easyoffer 📢 Три часа — и всё. Не откладывайте на потом. Спасибо всем, кто уже с нами! 💙

Задача: 780. Reaching Points Сложность: hard Даны четыре целых числа sx, sy, tx и ty, верните true, если возможно преобразовать точку (sx, sy) в точку (tx, ty) с помощью некоторых операций, иначе верните false. Допустимая операция для некоторой точки (x, y) заключается в преобразовании её либо в (x, x + y), либо в (x + y, y). Пример:

Input: sx = 1, sy = 1, tx = 3, ty = 5
Output: true
Explanation:
One series of moves that transforms the starting point to the target is:
(1, 1) -> (1, 2)
(1, 2) -> (3, 2)
(3, 2) -> (3, 5)

👨‍💻 Алгоритм: 1⃣Повторно вычитайте меньшее из {tx, ty} из большего из {tx, ty}. 2⃣Продолжайте вычитание, пока tx и ty больше или равны sx и sy соответственно. 3⃣Ответ будет true, если и только если в конечном итоге мы достигнем точки sx, sy. 😎 Решение:

class Solution {
public:
    bool reachingPoints(int sx, int sy, int tx, int ty) {
        while (tx >= sx && ty >= sy) {
            if (sx == tx && sy == ty) return true;
            if (tx > ty) {
                tx -= ty;
            } else {
                ty -= tx;
            }
        }
        return false;
    }
};

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