C/C++ | LeetCode

Получи грант до 1,2 млн руб. на обучение в магистратуре 4 офлайн программы, онлайн-магистратура по ML. Гранты до 1,2 млн руб. Стажировки, диплом гос. образца и фокус на твоей карьере в ЦУ Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 496. Next Greater Element I Сложность: easy Следующий больший элемент для некоторого элемента x в массиве — это первый больший элемент, который находится справа от x в том же массиве. Вам даны два различных целочисленных массива с индексами, начинающимися с 0: nums1 и nums2, где nums1 является подмножеством nums2. Для каждого 0 <= i < nums1.length найдите индекс j, такой что nums1[i] == nums2[j], и определите следующий больший элемент для nums2[j] в nums2. Если следующего большего элемента нет, то ответ для этого запроса — -1. Верните массив ans длиной nums1.length, где ans[i] — это следующий больший элемент, как описано выше. Пример:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

👨‍💻 Алгоритм: 1⃣Инициализация и поиск совпадений Создайте массив res для хранения результатов. Для каждого элемента nums1[i] найдите его индекс j в массиве nums2. 2⃣Поиск следующего большего элемента После нахождения индекса j в nums2 начните поиск элемента справа от nums2[j], который больше nums1[i]. Если такой элемент найден, добавьте его в res. 3⃣Заполнение результата Если следующий больший элемент не найден, добавьте -1 в соответствующую позицию res. Верните массив res. 😎 Решение:

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res(nums1.size(), -1);
        
        for (int i = 0; i < nums1.size(); i++) {
            bool found = false;
            for (int j = 0; j < nums2.size(); j++) {
                if (nums2[j] == nums1[i]) {
                    found = true;
                }
                if (found && nums2[j] > nums1[i]) {
                    res[i] = nums2[j];
                    break;
                }
            }
        }
        
        return res;
    }
};

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

Продолжение следует в «Летово Игра» ✨Стоит сделать первый шаг в «Летово» — и привычное лето превращается в межгалактическое приключение. Летающие тарелки на горизонте, учёные ловят таинственные сигналы, чтобы встать на защиту планеты, нужно быть готовым к новым открытиям и испытаниям. «Летово Игра» — это образовательная игра для подростков 10–17 лет, созданная на базе школы «Летово» лучшими педагогами и опытными игротехниками. Знания и навыки здесь осваиваются не за партой, а через действия, вызовы и работу в команде. Каждый день - это шаг в неизведанное: новые вызовы, важные задачи, совместные решения.😊 📅Смены длятся 10 дней и стартуют с 1 июля. Количество мест ограничено. Подать заявку #реклама 16+ letovogame.ru О рекламодателе

Задача: 540. Single Element in a Sorted Array Сложность: medium Дан отсортированный массив, состоящий только из целых чисел, где каждый элемент встречается ровно дважды, кроме одного элемента, который встречается ровно один раз. Верните единственный элемент, который встречается только один раз. Ваше решение должно работать за время O(log n) и использовать O(1) памяти. Пример:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

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

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        for (int i = 0; i < nums.size() - 1; i += 2) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums.back();
    }
};

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

Внимание родителям учеников 5–11 классов! Если вы чувствуете, что традиционная школа не раскрывает потенциал вашего ребёнка — пришло время действовать. SOTKA.PREMIUM — элитная образовательная программа от онлайн-школы «Сотка», резидента «Сколково» и обладателя лицензии Министерства образования РФ. Что получает ваш ребенок: ✅ Персональный образовательный трек и занятия с ведущими педагогами страны ✅ Менторство от студентов МГУ, ВШЭ и других топ-вузов ✅ Развитие навыков будущего: от критического мышления до работы с нейросетями ✅ Участие в олимпиадах, проектах, летних выездных сборах и офлайн-лагере ⚡Главное: программа гарантирует поступление в ведущие вузы страны. Сейчас открыто всего 7 мест. При записи — бесплатная аналитика сильных сторон ребёнка в подарок. Записаться #реклама 16+ mrqz.me О рекламодателе

Задача: 1416. Restore The Array Сложность: hard Программа должна была напечатать массив целых чисел. Программа забыла напечатать пробелы, и массив напечатан как строка цифр s, и всё, что мы знаем, это что все числа в массиве были в диапазоне [1, k] и в массиве нет ведущих нулей. Учитывая строку s и целое число k, верните количество возможных массивов, которые могут быть напечатаны как s с использованием упомянутой программы. Так как ответ может быть очень большим, верните его по модулю 10^9 + 7. Пример:

Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]

👨‍💻 Алгоритм: 1⃣Создать массив dp размера m + 1, чтобы хранить значения dfs(x). 2⃣Для получения значения dfs(start), если dp[start] не равно нулю, вернуть его значение. Иначе: Если s[start] == 0, вернуть 0. Если start = m, вернуть 1. Инициализировать count = 0, чтобы считать количество возможных массивов. Перебрать все возможные конечные индексы end, и если s[start ~ end] представляет допустимое число, продолжить рекурсивный вызов dfs(end + 1) и обновить count как count += dfs(end + 1). Обновить dp[start] значением dfs(start). 3⃣Вернуть dfs(0). 😎 Решение:

class Solution {
public:
    int mod = 1_000_000_007;

    int dfs(vector<int>& dp, int start, const string& s, int k) {
        if (dp[start] != 0) return dp[start];
        if (start == s.size()) return 1;
        if (s[start] == '0') return 0;

        long count = 0;
        for (int end = start; end < s.size(); ++end) {
            string currNumber = s.substr(start, end - start + 1);
            if (stol(currNumber) > k) break;
            count = (count + dfs(dp, end + 1, s, k)) % mod;
        }

        dp[start] = count;
        return count;
    }

    int numberOfArrays(string s, int k) {
        vector<int> dp(s.size() + 1);
        return dfs(dp, 0, s, k);
    }
};

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

Скидки на электрические зубные щетки Oral-B ORAL-B Genius-X с искусственным интеллектом – первая в мире зубная щетка, которая распознает стиль чистки зубов и дает рекомендации по улучшению. Купить #реклама market.yandex.ru О рекламодателе

Задача: 583. Delete Operation for Two Strings Сложность: medium Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми. На одном шаге можно удалить ровно один символ в любой строке. Пример:

Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

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

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<int> dp(n + 1, 0);

        for (int i = 0; i <= m; ++i) {
            vector<int> temp(n + 1, 0);
            for (int j = 0; j <= n; ++j) {
                if (i == 0 || j == 0) {
                    temp[j] = i + j;
                } else if (word1[i - 1] == word2[j - 1]) {
                    temp[j] = dp[j - 1];
                } else {
                    temp[j] = 1 + min(dp[j], temp[j - 1]);
                }
            }
            dp = temp;
        }

        return dp[n];
    }
};

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

Датчики тока ELHART ATE.S Бесконтактные датчики тока для контроля работы оборудования. Российские датчики тока ELHART ATE.S - это современные приборы отечественного производства, качественнее, дешевле европейских аналогов с доставкой по России и Белоруссии от 1 дня! ⚡ Точность до 0,2% ⚡ Выход 4..20 мА ⚡ Защита от длительных перегрузок ⚡ Время отклика от 0,1 с ⚡ Частота измеряемого тока от 40 до 400 Гц Подробное описание на сайте. Оптимизируйте производство современными датчиками ELHART Перейти на сайт #реклама kipservis.ru О рекламодателе

Задача: 1482. Minimum Number of Days to Make m Bouquets Сложность: medium Вам дан массив целых чисел bloomDay, целое число m и целое число k. Вам нужно сделать m букетов. Для создания букета необходимо использовать k соседних цветов из сада. Сад состоит из n цветов, i-й цветок расцветет на bloomDay[i] и затем может быть использован ровно в одном букете. Верните минимальное количество дней, которое нужно подождать, чтобы можно было сделать m букетов из сада. Если сделать m букетов невозможно, верните -1. Пример:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.

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

class Solution {
private:
    int getNumOfBouquets(vector<int>& bloomDay, int mid, int k) {
        int numOfBouquets = 0, count = 0;
        for (int day : bloomDay) {
            if (day <= mid) {
                count++;
            } else {
                count = 0;
            }
            if (count == k) {
                numOfBouquets++;
                count = 0;
            }
        }
        return numOfBouquets;
    }

public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        if (bloomDay.size() < m * k) return -1;
        int start = 0, end = *max_element(bloomDay.begin(), bloomDay.end());
        int minDays = -1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (getNumOfBouquets(bloomDay, mid, k) >= m) {
                minDays = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return minDays;
    }
};

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

Получи грант до 1,2 млн руб. на обучение в магистратуре 4 офлайн программы, онлайн-магистратура по ML. Гранты до 1,2 млн руб. Стажировки, диплом гос. образца и фокус на твоей карьере в ЦУ Подать заявку #реклама 16+ apply.centraluniversity.ru О рекламодателе

Задача: 1518. Water Bottles Сложность: easy Есть numBottles бутылок с водой, которые изначально наполнены водой. Вы можете обменять numExchange пустых бутылок на одну полную бутылку воды на рынке. Операция питья полной бутылки воды превращает её в пустую бутылку. Даны два целых числа numBottles и numExchange. Верните максимальное количество бутылок с водой, которые вы можете выпить. Пример:

Input: numBottles = 9, numExchange = 3
Output: 13
Explanation: You can exchange 3 empty bottles to get 1 full water bottle.
Number of water bottles you can drink: 9 + 3 + 1 = 13.

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

class Solution {
public:
    int numWaterBottles(int numBottles, int numExchange) {
        int consumedBottles = 0;

        while (numBottles >= numExchange) {
            consumedBottles += numExchange;
            numBottles -= numExchange;
            numBottles++;
        }

        return consumedBottles + numBottles;
    }
};

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

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

Задача: 499. The Maze III Сложность: hard В лабиринте есть мячик с пустыми пространствами (0) и стенами (1). Мячик может катиться вверх, вниз, влево или вправо, пока не столкнется со стеной, затем выбрать новое направление. В лабиринте также есть отверстие, куда мячик упадет, если закатится в него. Дан лабиринт размером m x n, позиция мяча ball и отверстия hole, где ball = [ballrow, ballcol] и hole = [holerow, holecol]. Верните строку instructions с кратчайшим путем мячика к отверстию. Если существует несколько вариантов, верните лексикографически минимальный. Если путь невозможен, верните "impossible". Ответ должен содержать 'u' (вверх), 'd' (вниз), 'l' (влево) и 'r' (вправо). Расстояние — это количество пройденных пустых пространств от начальной позиции (исключительно) до конечной (включительно). Вы можете предположить, что границы лабиринта — это стены. В примере ниже они не указаны. Пример:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], ball = [4,3], hole = [0,1]
Output: "lul"

👨‍💻 Алгоритм: 1⃣Инициализация и вспомогательные функции Создайте функцию valid для проверки, находится ли координата (row, col) в пределах лабиринта и является ли она пустым пространством. Создайте функцию getNeighbors для получения списка соседей для данной позиции. Двигайтесь в каждом направлении (вверх, вниз, влево, вправо) до встречи со стеной. 2⃣Запуск алгоритма Дейкстры Инициализируйте очередь с начальной позицией мяча, где элементы с меньшим расстоянием имеют высокий приоритет, а при равных расстояниях выбирайте минимальную строку пути. Создайте структуру seen для отслеживания посещенных узлов. 3⃣Поиск кратчайшего пути Пока очередь не пуста, извлекайте узел с наименьшим расстоянием. Если узел посещен, пропустите его. Если это отверстие, верните текущий путь. Отметьте узел как посещенный, добавьте его соседей в очередь, обновив расстояние и путь. Если пути нет, верните "impossible". 😎 Решение:

#include <vector>
#include <queue>
#include <string>
#include <functional>

using namespace std;

struct State {
    int row, col, dist;
    string path;
    bool operator>(const State& other) const {
        return dist == other.dist ? path > other.path : dist > other.dist;
    }
};

class Solution {
public:
    string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
        int m = maze.size(), n = maze[0].size();
        vector<vector<int>> directions = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};
        vector<string> textDirections = {"l", "u", "r", "d"};
        priority_queue<State, vector<State>, greater<State>> heap;
        vector<vector<bool>> seen(m, vector<bool>(n));
        heap.push({ball[0], ball[1], 0, ""});
        
        while (!heap.empty()) {
            auto [row, col, dist, path] = heap.top(); heap.pop();
            if (seen[row][col]) continue;
            if (row == hole[0] && col == hole[1]) return path;
            seen[row][col] = true;
            
            for (int i = 0; i < 4; ++i) {
                int r = row, c = col, d = 0;
                while (valid(r + directions[i][0], c + directions[i][1], maze)) {
                    r += directions[i][0]; c += directions[i][1]; d++;
                    if (r == hole[0] && c == hole[1]) break;
                }
                heap.push({r, c, dist + d, path + textDirections[i]});
            }
        }
        return "impossible";
    }
    
    bool valid(int row, int col, vector<vector<int>>& maze) {
        return row >= 0 && row < maze.size() && col >= 0 && col < maze[0].size() && maze[row][col] == 0;
    }
};

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

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

Задача: 82. Remove Duplicates from Sorted List II Сложность: medium Дан head — начало отсортированного связного списка. Удалите все узлы, содержащие повторяющиеся числа, оставив только уникальные значения. Верните отсортированный список без дубликатов. Пример:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

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

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* sentinel = new ListNode(0, head);
        ListNode* pred = sentinel;
        while (head != NULL) {
            if (head->next != NULL && head->val == head->next->val) {
                while (head->next != NULL && head->val == head->next->val) {
                    head = head->next;
                }
                pred->next = head->next;
            } else {
                pred = pred->next;
            }
            head = head->next;
        }
        return sentinel->next;
    }
};

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

Инструменты для дома и дачи Ресанта Мойки высокого давления и дрели-шуруповёрты от Ресанта, Huter и Вихрь со скидкой до 40%! Обновите свой арсенал инструментов! Купить #реклама market.yandex.ru О рекламодателе

Задача: 901. Online Stock Span Сложность: medium Разработайте алгоритм, который собирает ежедневные котировки цен на некоторые акции и возвращает размах цены этой акции за текущий день. Размах цены акции за один день - это максимальное количество дней подряд (начиная с этого дня и в обратном направлении), в течение которых цена акции была меньше или равна цене этого дня. Например, если цены акции за последние четыре дня равны [7,2,1,2], а цена акции сегодня равна 2, то размах сегодняшнего дня равен 4, поскольку, начиная с сегодняшнего дня, цена акции была меньше или равна 2 в течение 4 дней подряд. Также, если цена акции за последние четыре дня равна [7,34,1,2], а цена акции сегодня равна 8, то размах сегодняшнего дня равен 3, так как начиная с сегодняшнего дня цена акции была меньше или равна 8 в течение 3 дней подряд. Реализация класса StockSpanner: StockSpanner() Инициализирует объект класса. int next(int price) Возвращает размах цены акции, учитывая, что сегодняшняя цена равна price. Пример:

Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]

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

class StockSpanner {
    stack<pair<int, int>> stk;

public:
    StockSpanner() {}

    int next(int price) {
        int span = 1;
        while (!stk.empty() && stk.top().first <= price) {
            span += stk.top().second;
            stk.pop();
        }
        stk.push({price, span});
        return span;
    }
};

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

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

Задача: 41. First Missing Positive Сложность: hard Дан неотсортированный массив целых чисел nums. Верните наименьшее положительное целое число, которого нет в массиве nums. Необходимо реализовать алгоритм, который работает за время O(n) и использует O(1) дополнительной памяти. Пример:

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

👨‍💻 Алгоритм: 1⃣Перебрать массив и попытаться разместить каждое число в правильной позиции: nums[i] должен быть равен i + 1 2⃣Используем swap, чтобы поставить каждый элемент на его "правильное" место, если это возможно 3⃣После расстановки — находим первый индекс, где nums[i] != i + 1. Возвращаем i + 1 😎 Решение:

int firstMissingPositive(std::vector<int>& nums) {
    for (int i = 0; i < nums.size(); ) {
        if (nums[i] <= 0 || nums[i] > nums.size()) {
            ++i;
            continue;
        }
        if (nums[i] == i + 1) {
            ++i;
            continue;
        }
        int j = nums[i];
        if (nums[j - 1] == nums[i]) {
            ++i;
            continue;
        }
        std::swap(nums[j - 1], nums[i]);
    }

    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }

    return nums.size() + 1;
}

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