C/C++ | LeetCode

⏳ Осталось всего 14 дней до завершения краудфандинга Сейчас самое подходящее время подключиться, если вы ждали или откладывали: Все, кто поддержат проект сейчас, до релиза, получат: 🚀 PRO-доступ на 1 год по цене месячной подписки ➕ Бета-доступ к EasyOffer 2.0 (конец мая) 👉 Поддержать: https://planeta.ru/campaigns/easyoffer

Задача: 1094. Car Pooling Сложность: medium Есть автомобиль с пустыми сиденьями емкостью capacity. Автомобиль движется только на восток (то есть он не может повернуть и ехать на запад). Дан целочисленный параметр capacity и массив поездок trips, где trips[i] = [numPassengersi, fromi, toi] указывает, что на i-й поездке numPassengersi пассажиров должны быть забраны на позиции fromi и высажены на позиции toi. Позиции заданы как количество километров на восток от начальной точки автомобиля. Верните true, если возможно забрать и высадить всех пассажиров для всех указанных поездок, или false в противном случае. Пример:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

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

#include <vector>
#include <map>
using namespace std;

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        map<int, int> timestamp;
        for (auto& trip : trips) {
            timestamp[trip[1]] += trip[0];
            timestamp[trip[2]] -= trip[0];
        }
        int usedCapacity = 0;
        for (auto& change : timestamp) {
            usedCapacity += change.second;
            if (usedCapacity > capacity) {
                return false;
            }
        }
        return true;
    }
};

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

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

Задача: 1319. Number of Operations to Make Network Connected Сложность: medium Дано n компьютеров, пронумерованных от 0 до n - 1, соединённых Ethernet-кабелями connections, образующими сеть, где connections[i] = [ai, bi] представляет собой соединение между компьютерами ai и bi. Любой компьютер может достичь любого другого компьютера напрямую или косвенно через сеть. Вам даны начальные соединения сети. Вы можете извлекать определённые кабели между двумя напрямую соединёнными компьютерами и размещать их между любыми парами несоединённых компьютеров, чтобы сделать их напрямую соединёнными. Верните минимальное количество раз, которое необходимо сделать это, чтобы соединить все компьютеры. Если это невозможно, верните -1. Пример:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.

👨‍💻 Алгоритм: 1⃣Проверьте размер connections. Если он меньше n - 1, у нас недостаточно ребер, чтобы соединить весь граф. В этом случае возвращаем -1. 2⃣Создайте список смежности с помощью connections, где adj[x] содержит всех соседей узла x. Создайте целое число numberOfConnectedComponents, которое хранит количество компонент связности в графе. Инициализируйте его значением 0. 3⃣Создайте массив visit длиной n для отслеживания посещенных узлов. Пройдите по всем узлам, и для каждого узла i проверьте, был ли он посещен. Если узел i не был посещен, увеличьте numberOfConnectedComponents на 1 и начните обход DFS: Используйте функцию dfs для выполнения обхода. Для каждого вызова передавайте узел, ребра и visit в качестве параметров, начиная с узла i. Отметьте узел как посещенный. Пройдитесь по всем соседям узла. Если какой-либо сосед еще не был посещен, рекурсивно вызовите dfs с этим соседом в качестве узла. Верните numberOfConnectedComponents - 1. 😎 Решение:

class Solution {
public:
    void dfs(int node, unordered_map<int, vector<int>>& adj, vector<bool>& visit) {
        visit[node] = true;
        if (adj.find(node) == adj.end()) {
            return;
        }
        for (int neighbor : adj[node]) {
            if (!visit[neighbor]) {
                visit[neighbor] = true;
                dfs(neighbor, adj, visit);
            }
        }
    }

    int makeConnected(int n, vector<vector<int>>& connections) {
        if (connections.size() < n - 1) {
            return -1;
        }

        unordered_map<int, vector<int>> adj;
        for (auto& connection : connections) {
            adj[connection[0]].push_back(connection[1]);
            adj[connection[1]].push_back(connection[0]);
        }

        int numberOfConnectedComponents = 0;
        vector<bool> visit(n, false);
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                numberOfConnectedComponents++;
                dfs(i, adj, visit);
            }
        }

        return numberOfConnectedComponents - 1;
    }
};

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

Задача: 912. Sort an Array Сложность: medium Задав массив целых чисел nums, отсортируйте массив по возрастанию и верните его. Вы должны решить задачу без использования встроенных функций за время O(nlog(n)) и с минимально возможной пространственной сложностью. Пример:

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

👨‍💻 Алгоритм: 1⃣Используем алгоритм "Сортировка слиянием" (Merge Sort), который обеспечивает время выполнения O(n log n) и минимально возможную пространственную сложность для стабильного сортировочного алгоритма. 2⃣Разделить массив на две половины. Рекурсивно отсортировать каждую половину. 3⃣Слить две отсортированные половины. 😎 Решение:

void merge(vector<int>& nums, int left, int mid, int right) {
    vector<int> left_half(nums.begin() + left, nums.begin() + mid + 1);
    vector<int> right_half(nums.begin() + mid + 1, nums.begin() + right + 1);

    int i = 0, j = 0, k = left;
    while (i < left_half.size() && j < right_half.size()) {
        if (left_half[i] <= right_half[j]) {
            nums[k++] = left_half[i++];
        } else {
            nums[k++] = right_half[j++];
        }
    }

    while (i < left_half.size()) {
        nums[k++] = left_half[i++];
    }

    while (j < right_half.size()) {
        nums[k++] = right_half[j++];
    }
}

void mergeSort(vector<int>& nums, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
}

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

Задача: 1344. Angle Between Hands of a Clock Сложность: medium Даны два числа, hour и minutes. Вернуть меньший угол (в градусах), образованный часовой и минутной стрелками. Ответы с точностью до 10^-5 от фактического значения будут считаться правильными. Пример:

Input: hour = 12, minutes = 30
Output: 165

👨‍💻 Алгоритм: 1⃣Рассчитать углы: minutes_angle = 6 * minutes и hour_angle = (hour % 12 + minutes / 60) * 30. 2⃣Найти разницу: diff = abs(hour_angle - minutes_angle). 3⃣Вернуть меньший угол: min(diff, 360 - diff). 😎 Решение:

class Solution {
public:
    double angleClock(int hour, int minutes) {
        int oneMinAngle = 6;
        int oneHourAngle = 30;

        double minutesAngle = oneMinAngle * minutes;
        double hourAngle = (hour % 12 + minutes / 60.0) * oneHourAngle;

        double diff = abs(hourAngle - minutesAngle);
        return min(diff, 360 - diff);
    }
};

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

Задача: 760. Find Anagram Mappings Сложность: easy Вам даны два целочисленных массива nums1 и nums2, где nums2 - анаграмма nums1. Оба массива могут содержать дубликаты. Верните индексное отображение массива mapping из nums1 в nums2, где mapping[i] = j означает, что i-й элемент в nums1 появляется в nums2 по индексу j. Если ответов несколько, верните любой из них. Массив a является анаграммой массива b означает, что b создается путем случайного изменения порядка элементов в a. Пример:

Input: nums1 = [12,28,46,32,50], nums2 = [50,12,32,46,28]
Output: [1,4,3,2,0]

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

vector<int> anagramMapping(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, vector<int>> indexMap;
    for (int i = 0; i < nums2.size(); i++) {
        indexMap[nums2[i]].push_back(i);
    }
    
    vector<int> mapping;
    for (int num : nums1) {
        mapping.push_back(indexMap[num].back());
        indexMap[num].pop_back();
    }
    
    return mapping;
}

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

ТИМИ-2025: Встреча профессионалов в области ТИМ Конференция, где говорят на языке практиков. Общение САПР-профессионалов! ✅Как внедрить Model Studio CS в текущие процессы проектирования ✅Личный разговор с разработчиками и пользователями Model Studio CS и CADLib ✅Сравните ваш подход с методиками ведущих компаний Конференция 19 июня | Бесплатно | Подключайтесь из любой точки страны! Зарегистрироваться #реклама 16+ timi-conf.ru О рекламодателе

Задача: 944. Delete Columns to Make Sorted Сложность: easy Учитывая массив строк words, верните наименьшую строку, которая содержит каждую строку в words в качестве подстроки. Если существует несколько допустимых строк наименьшей длины, верните любую из них. Вы можете предположить, что ни одна строка в words не является подстрокой другой строки в words. Пример:

Input: strs = ["cba","daf","ghi"]
Output: 1

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

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int count = 0;
        int rows = strs.size();
        int cols = strs[0].size();
        for (int col = 0; col < cols; col++) {
            for (int row = 1; row < rows; row++) {
                if (strs[row][col] < strs[row - 1][col]) {
                    count++;
                    break;
                }
            }
        }
        return count;
    }
};

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

Ошибки в защите данных: как СУБД Jatoba избегает их? Дата: 17 апреля (четверг) Время: 12:00 - 13:30 МСК Не пропустите вебинар «Кластерные решения для больших объемов данных: отечественный опыт» Эксперты УЦСБ и «Газинформсервис» расскажут, как избежать ошибок в настройке СУБД, повысить доступность данных и защитить их от утечек, даже при пиковых нагрузках. 1. Как Jatoba обеспечивает высокую доступность данных при максимальных нагрузках? 2. Почему стоит выбрать отечественную СУБД для хранения и защиты данных? 3. Реальные примеры успешных внедрений в крупных компаниях. 4. Демонстрация интерфейса и отказоустойчивости Jatoba DB в действии! Бонус: фирменный мерч от «Газинформсервис» за самый интересный вопрос! Зарегистрироваться #реклама 16+ sec.ussc.ru О рекламодателе

Задача: 1178. Number of Valid Words for Each PuzzleHardTopicsHint Сложность: hard Относительно заданной строки-головоломки, слово является допустимым, если выполняются оба следующих условия: Слово содержит первую букву головоломки. Каждая буква в слове присутствует в головоломке. Например, если головоломка "abcdefg", то допустимыми словами являются "faced", "cabbage" и "baggage", а недопустимыми словами являются "beefed" (не включает 'a') и "based" (включает 's', которой нет в головоломке). Верните массив answer, где answer[i] - это количество слов в данном списке слов words, которые допустимы относительно головоломки puzzles[i]. Пример:

Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
Output: [0,1,3,2,0]

👨‍💻 Алгоритм: 1⃣Постройте карту. Для каждого слова в списке words: Преобразуйте его в битовую маску его символов. Если эта битовая маска не была ранее встречена, сохраните ее в качестве ключа в карте со значением 1. Если она была ранее встречена, увеличьте счетчик для этой битовой маски на 1. 2⃣Подсчитайте количество допустимых слов для каждой головоломки. Для каждой головоломки в списке puzzles: Преобразуйте ее в битовую маску ее символов. Итерируйте по каждой возможной подмаске, содержащей первую букву головоломки (puzzle[i][0]). Слово является допустимым для головоломки, если его битовая маска совпадает с одной из подмасок головоломки. 3⃣Для каждой подмаски увеличивайте счетчик на количество слов, соответствующих подмаске. Мы можем найти количество слов, соответствующих подмаске, используя карту, построенную на предыдущем шаге. 😎 Решение:

class Solution {
private:
    int bitmask(string word) {
        int mask = 0;
        for (char letter : word) {
            mask |= 1 << (letter - 'a');
        }
        return mask;
    }

public:
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        unordered_map<int, int> wordCount;
        for (string word : words) {
            int mask = bitmask(word);
            wordCount[mask]++;
        }

        vector<int> result;
        for (string puzzle : puzzles) {
            int first = 1 << (puzzle[0] - 'a');
            int count = wordCount[first];
            int mask = bitmask(puzzle.substr(1));
            for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
                count += wordCount[submask | first];
            }
            result.push_back(count);
        }
        return result;
    }
};

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

26–27 апреля проводим Weekend Offer Frontend Устроиться в Яндекс за выходные — реально. Ищем крутых фронтендеров с опытом работы от 4 лет, готовых работать в офисном или гибридном режиме в России. Подавайте заявку до 23 апреля — и всего за два дня пройдите все технические собеседования. После сможете пообщаться с нанимающими менеджерами и выбрать из 10 команд ту, которая покажется самой интересной. Если всё сложится хорошо, сразу же пришлём вам офер. Зарегистрироваться #реклама yandex.ru О рекламодателе

Задача: 252. Meeting Rooms Сложность: easy Дан массив intervals, где каждый элемент — это временной интервал встречи [start, end]. Нужно определить, может ли человек посетить все встречи, то есть проверить, нет ли перекрывающихся интервалов. Пример:

Input: intervals = [[0,30],[5,10],[15,20]] Output: false

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

class Solution {
public:
    bool overlap(vector<int>& interval1, vector<int>& interval2) {
        return interval1[0] >= interval2[0] && interval1[0] < interval2[1]
            || interval2[0] >= interval1[0] && interval2[0] < interval1[1];
    }
    
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        for (size_t i = 0; i < intervals.size(); i++) {
            for (size_t j = i + 1; j < intervals.size(); j++) {
                if (overlap(intervals[i], intervals[j])) {
                    return false;
                }
            }
        }
        return true;
    }
};

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

6 мастхэв инструментов для совместной работы в Битрикс24 Читайте подробнее в карточках. Регистрируйтесь сейчас, чтобы забрать их все себе бесплатно😊 Зарегистрироваться #реклама 16+ office-online.bitrix24.ru О рекламодателе

Задача: 924. Minimize Malware Spread Сложность: hard Вам дана сеть из n узлов, представленная в виде графа с матрицей смежности n x n, где i-й узел непосредственно связан с j-м узлом, если graph[i][j] == 1. Некоторые узлы изначально заражены вредоносным ПО. Если два узла соединены напрямую и хотя бы один из них заражен вредоносным ПО, то оба узла будут заражены вредоносным ПО. Такое распространение вредоносного ПО будет продолжаться до тех пор, пока не останется ни одного узла, который можно было бы заразить таким образом. Предположим, что M(initial) - это конечное число узлов, зараженных вредоносным ПО, во всей сети после прекращения распространения вредоносного ПО. Мы удалим из initial ровно один узел. Верните тот узел, удаление которого минимизирует M(initial). Если можно удалить несколько узлов, чтобы минимизировать M(initial), верните такой узел с наименьшим индексом. Обратите внимание, что если узел был удален из начального списка зараженных узлов, он все равно может быть заражен позже из-за распространения вредоносного ПО. Пример:

Input: arr = [1,1,2,2,3,3,4,4,5,5], target = 8
Output: 20

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

class Solution {
public:
    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n = graph.size();
        unordered_set<int> initialSet(initial.begin(), initial.end());
        sort(initial.begin(), initial.end());
        int minInfected = INT_MAX;
        int bestNode = initial[0];
        
        for (int node : initial) {
            unordered_set<int> infected(initialSet);
            infected.erase(node);
            for (int i : initialSet) {
                if (i != node) {
                    dfs(graph, i, infected);
                }
            }
            if (infected.size() < minInfected) {
                minInfected = infected.size();
                bestNode = node;
            }
        }
        
        return bestNode;
    }
    
private:
    void dfs(vector<vector<int>>& graph, int node, unordered_set<int>& infected) {
        for (int neighbor = 0; neighbor < graph.size(); neighbor++) {
            if (graph[node][neighbor] == 1 && infected.find(neighbor) == infected.end()) {
                infected.insert(neighbor);
                dfs(graph, neighbor, infected);
            }
        }
    }
};

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

10 апреля бесплатный онлайн-митап: Битрикс24 Доски Что вас ждет на митапе: - Знакомство с Битрикс24 Досками: как новый инструмент помогает быстро обмениваться идеями и структурировать информацию - Обзор возможностей: неограниченное количество участников и объектов, 20+ шаблонов - Гибкость и адаптация: создаем доски под уникальные потребности команды - Безопасность и доступ: делимся правами доступа к доскам с участниками удобно и бесплатно Перейти на сайт #реклама 16+ meetups.bitrix24.tech О рекламодателе

Задача: 896. Monotonic Array Сложность: easy Массив является монотонным, если он либо монотонно возрастает, либо монотонно убывает. Массив nums является монотонно возрастающим, если для всех i <= j, nums[i] <= nums[j]. Массив nums является монотонно убывающим, если для всех i <= j, nums[i] >= nums[j]. Если задан целочисленный массив nums, верните true, если данный массив монотонный, или false в противном случае. Пример:

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

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

class Solution {
public:
    bool isMonotonic(vector<int>& nums) {
        bool increasing = true, decreasing = true;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] > nums[i - 1]) decreasing = false;
            if (nums[i] < nums[i - 1]) increasing = false;
        }
        return increasing || decreasing;
    }
};

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

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

Задача: 960. Delete Columns to Make Sorted III Сложность: hard Вам дан массив из n строк strs, все одинаковой длины. Мы можем выбрать любые индексы для удаления, и мы удаляем все символы в этих индексах для каждой строки. Например, если у нас есть strs = ["abcdef","uvwxyz"] и индексы удаления {0, 2, 3}, то итоговый массив после удаления будет ["bef", "vyz"]. Предположим, мы выбрали набор индексов удаления answer таким образом, что после удаления итоговый массив имеет каждую строку (ряд) в лексикографическом порядке. (т.е. (strs[0][0] <= strs[0][1] <= ... <= strs[0][strs[0].length - 1]) и (strs[1][0] <= strs[1][1] <= ... <= strs[1][strs[1].length - 1]) и так далее). Верните минимально возможное значение answer.length. Пример:

Input: strs = ["babca","bbazb"]
Output: 3
Explanation: After deleting columns 0, 1, and 4, the final array is strs = ["bc", "az"].
Both these rows are individually in lexicographic order (ie. strs[0][0] <= strs[0][1] and strs[1][0] <= strs[1][1]).
Note that strs[0] > strs[1] - the array strs is not necessarily in lexicographic order.

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

class Solution {
public:
    int minDeletionSize(vector<string>& A) {
        int W = A[0].size();
        vector<int> dp(W, 1);

        for (int i = W - 2; i >= 0; --i) {
            for (int j = i + 1; j < W; ++j) {
                bool valid = true;
                for (const string& row : A) {
                    if (row[i] > row[j]) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    dp[i] = max(dp[i], 1 + dp[j]);
                }
            }
        }

        return W - *max_element(dp.begin(), dp.end());
    }
};

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

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