C/C++ | LeetCode

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

#medium Задача: 721. Accounts Merge Дан список аккаунтов, в котором каждый элемент accounts[i] - это список строк, где первый элемент accounts[i][0] - это имя, а остальные элементы - это email, представляющие электронную почту аккаунта. Теперь мы хотим объединить эти аккаунты. Два аккаунта определенно принадлежат одному человеку, если у обоих аккаунтов есть какой-то общий email. Обратите внимание, что даже если два аккаунта имеют одинаковое имя, они могут принадлежать разным людям, поскольку у людей могут быть одинаковые имена. Изначально у человека может быть любое количество счетов, но все его счета обязательно должны иметь одинаковое имя. После объединения счетов верните счета в следующем формате: первый элемент каждого счета - имя, а остальные элементы - электронные письма в отсортированном порядке. Сами аккаунты могут быть возвращены в любом порядке. Пример:

nput: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]

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

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <algorithm>

using namespace std;

vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
    unordered_map<string, string> emailToName;
    unordered_map<string, unordered_set<string>> graph;

    
    for (auto& account : accounts) {
        string name = account[0];
        string firstEmail = account[1];
        for (int i = 1; i < account.size(); ++i) {
            string email = account[i];
            graph[firstEmail].insert(email);
            graph[email].insert(firstEmail);
            emailToName[email] = name;
        }
    }

    unordered_set<string> seen;
    vector<vector<string>> mergedAccounts;

   
    for (auto& [email, _] : emailToName) {
        if (seen.count(email) == 0) {
            vector<string> emails;
            stack<string> stk;
            stk.push(email);

            while (!stk.empty()) {
                string node = stk.top();
                stk.pop();
                if (seen.count(node) == 0) {
                    seen.insert(node);
                    emails.push_back(node);
                    for (auto& neighbor : graph[node]) {
                        if (!seen.count(neighbor)) {
                            stk.push(neighbor);
                        }
                    }
                }
            }

            sort(emails.begin(), emails.end());
            vector<string> account;
            account.push_back(emailToName[email]);
            account.insert(account.end(), emails.begin(), emails.end());
            mergedAccounts.push_back(account);
        }
    }

    return mergedAccounts;
}

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

#medium Задача: 491. Non-decreasing Subsequences Дан массив целых чисел nums. Верните все возможные различные неубывающие подпоследовательности данного массива, содержащие как минимум два элемента. Вы можете вернуть ответ в любом порядке. Пример:

Input: nums = [4,6,7,7]
Output: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

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

class Solution {
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        set<vector<int>> result;
        vector<int> sequence;
        backtrack(nums, 0, sequence, result);
        return vector<vector<int>>(result.begin(), result.end());
    }

private:
    void backtrack(vector<int>& nums, int index, vector<int>& sequence, set<vector<int>>& result) {
        if (index == nums.size()) {
            if (sequence.size() >= 2) {
                result.insert(sequence);
            }
            return;
        }
        if (sequence.empty() || sequence.back() <= nums[index]) {
            sequence.push_back(nums[index]);
            backtrack(nums, index + 1, sequence, result);
            sequence.pop_back();
        }
        backtrack(nums, index + 1, sequence, result);
    }
};

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

Квартиры в ЖК SOKOLNIKI! Рассрочка до 2,5 лет, ПВ от 10% Видовые квартиры бизнес+ класса возле парка от 28 м² от 400 000 руб./м² Первый взнос от 10% Гибкие программы рассрочки до 2,5х лет с переходом в ипотеку Квартиры от 28м² до 135м² От студий до семейных фоматов с большими гостиными Колясочные на этаже Все для удобства родителей Дизайнерские лобби Стильные входные группы Подземный паркинг Системы хранения велосипедов и самокатов Детский сад Закрытая территория Девелопер STONE 18 лет на рынке недвижимости. 27 проектов м. "Сокольники", 12 мин. от парка Перейти на сайт Проектная декларация на сайте https://наш.дом.рф/. Застройщик: ООО СЗ «КВАРТАЛ СОКОЛЬНИКИ». Финансовые услуги оказывает: ПАО "Совкомбанк". #реклама stone-sokolniki.ru О рекламодателе

#hard Задача: 489. Robot Room Cleaner Вы управляете роботом в комнате, представленной бинарной сеткой m x n, где 0 — стена, а 1 — пустая ячейка. Робот начинает в неизвестном месте, гарантированно пустом. У вас нет доступа к сетке, но вы можете перемещать робота через предоставленный API Robot. Роботу нужно очистить всю комнату (т.е. все пустые ячейки). Он может двигаться вперед, поворачивать налево или направо на 90 градусов. Если робот наталкивается на стену, его датчик препятствия обнаруживает это, и он остается на текущей ячейке. Разработайте алгоритм для очистки всей комнаты, используя следующие API:

interface Robot {
  // возвращает true, если следующая ячейка открыта и робот перемещается в эту ячейку.
  // возвращает false, если следующая ячейка является препятствием и робот остается на текущей ячейке.
  boolean move();

  // Робот останется на той же ячейке после вызова turnLeft/turnRight.
  // Каждый поворот составляет 90 градусов.
  void turnLeft();
  void turnRight();

  // Очистить текущую ячейку.
  void clean();
}

Пример:

Input: room = [[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,1,1,1,1,1,1],[0,0,0,1,0,0,0,0],[1,1,1,1,1,1,1,1]], row = 1, col = 3
Output: Robot cleaned all rooms.
Explanation: All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.

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

class Solution {
public:
    Robot* robot;
    set<pair<int, int>> visited;
    vector<pair<int, int>> directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    void goBack() {
        robot->turnRight();
        robot->turnRight();
        robot->move();
        robot->turnRight();
        robot->turnRight();
    }

    void backtrack(int row, int col, int d) {
        visited.insert({row, col});
        robot->clean();
        for (int i = 0; i < 4; ++i) {
            int newD = (d + i) % 4;
            int newRow = row + directions[newD].first;
            int newCol = col + directions[newD].second;
            if (visited.find({newRow, newCol}) == visited.end() && robot->move()) {
                backtrack(newRow, newCol, newD);
                goBack();
            }
            robot->turnRight();
        }
    }

    void cleanRoom(Robot* robot) {
        this->robot = robot;
        backtrack(0, 0, 0);
    }
};

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

#medium Задача: 490. The Maze В лабиринте есть шар, который может перемещаться по пустым пространствам (представленным как 0) и стенам (представленным как 1). Шар может катиться по пустым пространствам вверх, вниз, влево или вправо, но он не остановится до тех пор, пока не наткнется на стену. Когда шар останавливается, он может выбрать следующее направление. Дан лабиринт размером m x n, начальная позиция шара и место назначения, где start = [startrow, startcol] и destination = [destinationrow, destinationcol]. Верните true, если шар может остановиться в месте назначения, иначе верните false. Вы можете предположить, что границы лабиринта представляют собой стены. В приведённом ниже примере они не указаны. Пример:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.

👨‍💻 Алгоритм: 1⃣Инициализация и подготовка данных Определите количество строк и столбцов в лабиринте (m и n). Создайте 2D массив visit для отслеживания посещённых ячеек. Запустите DFS (глубокий поиск) с начальной позиции. 2⃣DFS обход Если текущая ячейка уже посещена, верните false. Если текущая ячейка совпадает с ячейкой назначения, верните true. Отметьте текущую ячейку как посещённую. Переберите все четыре направления движения (вверх, вправо, вниз, влево): продвигайтесь в выбранном направлении до тех пор, пока не столкнётесь со стеной или границей. После остановки вызовите DFS для новой позиции. 3⃣Результат Если любой вызов DFS возвращает true, завершите выполнение и верните true. Если ни один путь не приводит к цели, верните false. 😎 Решение:

class Solution {
public:
    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        int m = maze.size(), n = maze[0].size();
        vector<vector<bool>> visit(m, vector<bool>(n, false));
        return dfs(m, n, maze, start, destination, visit);
    }

private:
    vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    bool dfs(int m, int n, vector<vector<int>>& maze, vector<int>& curr, vector<int>& destination, vector<vector<bool>>& visit) {
        if (visit[curr[0]][curr[1]]) return false;
        if (curr == destination) return true;
        visit[curr[0]][curr[1]] = true;
        for (auto [dx, dy] : directions) {
            int r = curr[0], c = curr[1];
            while (r >= 0 && r < m && c >= 0 && c < n && maze[r][c] == 0) {
                r += dx;
                c += dy;
            }
            vector<int> newCurr = {r - dx, c - dy};
            if (dfs(m, n, maze, newCurr, destination, visit)) return true;
        }
        return false;
    }
};

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

Устроиться аналитиком в Яндекс за выходные 1–2 марта проводим Weekend Offer Analytics. До 24 февраля оставьте заявку на участие, 1 марта пройдите технические собеседования, а 2 марта познакомьтесь с командами и получите офер. В мероприятии участвует 11 команд: Большие данные, Алиса, Ecom-сценарии Поиска, Автономный транспорт, Поиск с Нейро, Карты, Рекламные технологии, Коммерческий департамент, Международные проекты Поиска в Турции и Казахстане, Crowd, Приложение «Яндекс с Алисой». Вы сможете пообщаться с менеджерами и выбрать проект, который покажется самым интересным. Зарегистрироваться #реклама 16+ yandex.ru О рекламодателе

#medium Задача: 720. Longest Word in Dictionary Если задан массив строк words, представляющих английский словарь, верните самое длинное слово из words, которое может быть построено по одному символу из других слов из words. Если существует более одного возможного ответа, верните самое длинное слово с наименьшим лексикографическим порядком. Если ответа нет, верните пустую строку. Обратите внимание, что слово должно строиться слева направо, причем каждый дополнительный символ добавляется в конец предыдущего слова. Пример:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"

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

string longestWord(vector<string>& words) {
    sort(words.begin(), words.end());
    unordered_set<string> validWords;
    validWords.insert("");
    string longest = "";
    for (const string& word : words) {
        if (validWords.count(word.substr(0, word.size() - 1))) {
            validWords.insert(word);
            if (word.size() > longest.size()) {
                longest = word;
            }
        }
    }
    return longest;
}

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

#hard Задача: 719. Find K-th Smallest Pair Distance Расстояние между парой целых чисел a и b определяется как абсолютная разность между a и b. Учитывая целочисленный массив nums и целое число k, верните k-е наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 <= i < j < nums.length. Пример:

Input: nums = [1,3,1], k = 1
Output: 0

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

int countPairs(const vector<int>& nums, int mid) {
    int count = 0, j = 0;
    for (int i = 0; i < nums.size(); i++) {
        while (j < nums.size() && nums[j] - nums[i] <= mid) {
            j++;
        }
        count += j - i - 1;
    }
    return count;
}

int smallestDistancePair(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    int left = 0, right = nums.back() - nums.front();
    while (left < right) {
        int mid = (left + right) / 2;
        if (countPairs(nums, mid) < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

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

Онлайн-интенсив для ИТ-специалистов в Открытых школах Т1 Уже есть опыт работы в ИТ, но хочешь прокачать скилы и продвинуться в карьере? Тогда скорее залетай на бесплатный ИТ-интенсив в Открытых школах Т1. Открытые школы — это возможность усилить свои навыки и получить оффер в ИТ-холдинг Т1. И все это за месяц, онлайн и в удобное вечернее время. Что ты получишь? ✅ бесплатное обучение в гибком формате: по вечерам, онлайн, из любого города РФ и РБ. ✅ материалы от HR для прокачки резюме и подготовки к интервью в Т1. ✅ много практики и уникальный рыночный опыт. ✅ поддержку опытных преподавателей и карьерный фаст-трек до мидла в Т1 для лучших выпускников. ✅ реальный шанс получить оффер в Т1. Более 1000 специалистов уже прошли этот путь — теперь твоя очередь! Регистрация до 14 марта! Подать заявку #реклама 16+ t1.ru О рекламодателе

#medium Задача: 718. Maximum Length of Repeated Subarray Если даны два целочисленных массива nums1 и nums2, верните максимальную длину подмассива, который встречается в обоих массивах. Пример:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3

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

int findLength(vector<int>& nums1, vector<int>& nums2) {
    vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
    int maxLength = 0;
    for (int i = nums1.size() - 1; i >= 0; i--) {
        for (int j = nums2.size() - 1; j >= 0; j--) {
            if (nums1[i] == nums2[j]) {
                dp[i][j] = dp[i + 1][j + 1] + 1;
                maxLength = max(maxLength, dp[i][j]);
            }
        }
    }
    return maxLength;
}

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

– Помощь с pet-проектом – Составление roadmap – Общая консультация – Проведение код-ревью и mock-собеседования – Помощь с трудоустройством Все это и многое другое может Ментор. Он обеспечит вам необходимый boost, ускорит и упростит вход в IT. 🔥 Узнай список топовых менторов ✴ Многие из них предлагают бесплатную первую консультацию

#easy Задача: 717. 1-bit and 2-bit Characters У нас есть два специальных символа: первый символ может быть представлен одним битом 0. Второй символ может быть представлен двумя битами (10 или 11). Если задан двоичный массив bits, который заканчивается 0, верните true, если последний символ должен быть однобитным. Пример:

Input: bits = [1,0,0]
Output: true

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

bool isOneBitCharacter(vector<int>& bits) {
    int i = 0;
    while (i < bits.size() - 1) {
        i += bits[i] + 1;
    }
    return i == bits.size() - 1;
}

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

Нужен человек, для сбора вопросов из собеседований на должность C/C++ разработчик. Что надо делать: 1. Смотреть записи собеседований (список будет дан) 2. Выписывать вопросы, которые задают кандидату Ставка: 450 руб. / час Примерная ЗП: 54 000 руб. / месяц (4 часа в день) Если интересно и можешь уделять работе от 4 часов / день, то отправь сообщение https://t.me/niniafd и сразу напиши какие языки программирования знаешь и какие лучше всего?

Целевые кибератаки 2024: аналитика и кейсы На вебинаре 27 февраля команда Solar 4RAYS подведет итоги по следам расследований целевых атак 2024 года Вы узнаете, как профессиональные хакеры атакуют российские компании и обходят системы безопасности, когда защита не соответствует уровню угроз. А также какие тактики используют киберпреступники, каков конечный импакт для систем ИБ от воздействия хакеров и как выстроить стратегию защиты. Что будет на вебинаре: - Какие инструменты противодействия актуальны в 2025 году; - Какие отрасли бизнеса подвергались атакам и с какой целью; - Какие интересные техники использовали злоумышленники: разбор кейсов расследований. Все примеры и рекомендации основаны на реальных расследованиях инцидентов в российских организациях. Зарегистрироваться #реклама 16+ rt-solar.ru О рекламодателе

#medium Задача: 776. Split BST Дан корень бинарного дерева поиска (BST) и целое число target, разделите дерево на два поддерева, где первое поддерево содержит узлы, которые меньше или равны значению target, а второе поддерево содержит узлы, которые больше значения target. Не обязательно, чтобы дерево содержало узел со значением target. Кроме того, большая часть структуры исходного дерева должна сохраниться. Формально, для любого потомка c с родителем p в исходном дереве, если они оба находятся в одном поддереве после разделения, то узел c все еще должен иметь родителя p. Верните массив из двух корней двух поддеревьев в порядке. Пример:

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

👨‍💻 Алгоритм: 1⃣Базовый случай: Если корень равен null, верните массив, содержащий два указателя null. Это необходимо для обработки случая, когда дерево пустое. 2⃣Проверьте, больше ли значение корня целевого значения. Если да, рекурсивно разделите левое поддерево, вызвав splitBST(root->left, target). Прикрепите правую часть разделенного к левому поддереву корня. Верните массив, содержащий левую часть разделенного и текущий корень. 3⃣Если значение корня меньше или равно целевому значению, рекурсивно разделите правое поддерево, вызвав splitBST(root->right, target). Прикрепите левую часть разделенного к правому поддереву корня. Верните массив, содержащий левую часть разделенного и текущий корень. 😎 Решение:

class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<TreeNode*> splitBST(TreeNode* root, int target) {
        if (!root) {
            return {nullptr, nullptr};
        }

        if (root->val > target) {
            auto left = splitBST(root->left, target);
            root->left = left[1];
            return {left[0], root};
        } else {
            auto right = splitBST(root->right, target);
            root->right = right[0];
            return {root, right[1]};
        }
    }
};

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

#hard Задача: 716. Max Stack Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова. Пример:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

👨‍💻 Алгоритм: 1⃣Инициализируйте MaxStack с двумя стеками: один для хранения всех элементов, другой для отслеживания максимальных элементов. 2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека. 3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно. 😎 Решение:

class MaxStack {
public:
    MaxStack() {}

    void push(int x) {
        stack.push(x);
        if (maxStack.empty() || x >= maxStack.top()) {
            maxStack.push(x);
        }
    }

    int pop() {
        int x = stack.top();
        stack.pop();
        if (x == maxStack.top()) {
            maxStack.pop();
        }
        return x;
    }

    int top() {
        return stack.top();
    }

    int peekMax() {
        return maxStack.top();
    }

    int popMax() {
        int maxVal = maxStack.top();
        maxStack.pop();
        stack<int> buffer;
        while (stack.top() != maxVal) {
            buffer.push(stack.top());
            stack.pop();
        }
        stack.pop();
        while (!buffer.empty()) {
            push(buffer.top());
            buffer.pop();
        }
        return maxVal;
    }

private:
    stack<int> stack;
    stack<int> maxStack;
};

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

ТОП 2 канала для тех кто увлекатеся хакингом и кибербезопасностью: Этичный Хакер — крупнейший в СНГ канал по информационной безопасности. OSINT, анонимность, пентест, социальная инженерия. Лаборатория Хакера — авторский канал от специалиста по ИБ. Новости даркнета, сетевая разведка, обзоры инструментов с github, полезные подборки.

MBA онлайн с аккредитацией и беспроцентной рассрочкой! Готов к карьерному рывку? Обучайся на программе MBA с международной аккредитацией и выйди на новый уровень карьеры! ✅ Форматы: онлайн и офлайн ✅ 37+ направлений ✅ Актуальные программы 2025 года ✅ Диплом за 1 год ✅ Беспроцентная рассрочка Не жди — запишись уже сегодня и начни свой путь к успеху! Стань лидером уже сейчас! Только до конца года Скидки до -45% на обучение в Московской Академии Бизнеса! Перейти на сайт #реклама 16+ moscow.mba О рекламодателе

#medium Задача: 775. Global and Local Inversions Дан массив целых чисел nums длиной n, который представляет собой перестановку всех чисел в диапазоне [0, n - 1]. Число глобальных инверсий — это количество различных пар (i, j), где: 0 <= i < j < n nums[i] > nums[j] Число локальных инверсий — это количество индексов i, где: 0 <= i < n - 1 nums[i] > nums[i + 1] Верните true, если количество глобальных инверсий равно количеству локальных инверсий. Пример:

Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.

👨‍💻 Алгоритм: 1⃣Локальная инверсия также является глобальной инверсией. Таким образом, нам нужно проверить, есть ли в нашей перестановке какие-либо нелокальные инверсии (A[i] > A[j], i < j) с j - i > 1. 2⃣Для этого мы можем перебрать каждый индекс i и проверить, есть ли индекс j, такой что j > i + 1 и nums[i] > nums[j]. Если такой индекс найден, это будет означать наличие нелокальной инверсии. 3⃣Если для всех индексов i условие выше не выполняется, это значит, что количество глобальных инверсий равно количеству локальных инверсий, и мы возвращаем true. В противном случае, если хотя бы одна нелокальная инверсия найдена, мы возвращаем false. 😎 Решение:

class Solution {
public:
    bool isIdealPermutation(vector<int>& A) {
        int N = A.size();
        for (int i = 0; i < N; ++i)
            for (int j = i + 2; j < N; ++j)
                if (A[i] > A[j]) return false;
        return true;
    }
};

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