C/C++ | LeetCode

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

Задача: 820. Short Encoding of Words Сложность: medium Допустимым кодированием массива слов является любая опорная строка s и массив индексов indices, такие что: words.length == indices.length Опорная строка s заканчивается символом '#'. Для каждого индекса indices[i], подстрока строки s, начинающаяся с indices[i] и заканчивающаяся (но не включительно) следующим символом '#', равна words[i]. Дан массив слов, верните длину самой короткой возможной опорной строки s для любого допустимого кодирования слов. Пример:

Input: words = ["time", "me", "bell"]
Output: 10
Explanation: A valid encoding would be s = "time#bell#" and indices = [0, 2, 5].
words[0] = "time", the substring of s starting from indices[0] = 0 to the next '#' is underlined in "time#bell#"
words[1] = "me", the substring of s starting from indices[1] = 2 to the next '#' is underlined in "time#bell#"
words[2] = "bell", the substring of s starting from indices[2] = 5 to the next '#' is underlined in "time#bell#"

👨‍💻 Алгоритм: 1⃣Поскольку слово имеет не более 6 собственных суффиксов (так как words[i].length <= 7), давайте итерироваться по всем из них. Для каждого собственного суффикса мы попытаемся удалить его из нашего списка слов. Для эффективности сделаем words множеством. 2⃣Затем создадим список оставшихся слов и сформируем опорную строку, объединяя каждое слово с символом '#'. 3⃣В конце вернем длину полученной опорной строки. 😎 Решение:

class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
        unordered_set<string> good(words.begin(), words.end());
        for (const string& word : words) {
            for (int k = 1; k < word.length(); ++k) {
                good.erase(word.substr(k));
            }
        }
        int length = 0;
        for (const string& word : good) {
            length += word.length() + 1;
        }
        return length;
    }
};

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

Бесплатное льготное обучение: 3 месяца Ищем людей, которые хотят обучиться и работать в IT-сфере из дома В конце обучения вы пройдете стажировку и устроитесь на работу с зп от 150.000 рублей Образование, место жительства, трудовой стаж — не важны! Для старта нужно: — пройти короткий тест — заполнить анкету На что можно рассчитывать, после обучения: ✅ удаленная работа ✅ зп от 150.000 рублей (потолка нет) ✅ стабильная подработка, если не хотите уходить с основной работы ⚡ Осталось всего 47 бесплатных мест. Успейте пройти тест и оставить заявку: Узнать больше #реклама 16+ technolium.ru О рекламодателе

Задача: 1120. Maximum Average Subtree Сложность: medium Дан корень бинарного дерева. Верните максимальное среднее значение поддерева этого дерева. Ответы, отличающиеся от фактического ответа не более чем на 10^-5, будут приняты. Поддерево дерева — это любой узел этого дерева плюс все его потомки. Среднее значение дерева — это сумма его значений, деленная на количество узлов. Пример:

Input: root = [5,6,1]
Output: 6.00000
Explanation: 
For the node with value = 5 we have an average of (5 + 6 + 1) / 3 = 4.
For the node with value = 6 we have an average of 6 / 1 = 6.
For the node with value = 1 we have an average of 1 / 1 = 1.
So the answer is 6 which is the maximum.

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

class Solution {
public:
    struct State {
        int nodeCount;
        int valueSum;
        double maxAverage;

        State(int nodes, int sum, double maxAvg)
            : nodeCount(nodes), valueSum(sum), maxAverage(maxAvg) {}
    };

    double maximumAverageSubtree(TreeNode* root) {
        return maxAverage(root).maxAverage;
    }

private:
    State maxAverage(TreeNode* root) {
        if (root == nullptr) {
            return State(0, 0, 0);
        }

        State left = maxAverage(root->left);
        State right = maxAverage(root->right);

        int nodeCount = left.nodeCount + right.nodeCount + 1;
        int sum = left.valueSum + right.valueSum + root->val;
        double currentAverage = static_cast<double>(sum) / nodeCount;
        double maxAverage = std::max(currentAverage, std::max(left.maxAverage, right.maxAverage));

        return State(nodeCount, sum, maxAverage);
    }
};

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

Качаем скиллы PostgreSQL на PG BootCamp Russia 2025! Регистрируйся на бесплатную конференцию по PostgreSQL — 10.04.2025.📅 ✅ Бесплатное участие ✅ Опытные спикеры ✅ Тематические доклады ✅ Рабочие кейсы Каждый участник получает именной Сертификат участника мероприятия. Одни из немногих спикеров конференции: — Андрей Бородин PostgreSQL contributor, руководитель подразделения разработки РСУБД с открытым исходным кодом Yandex Cloud — Александр Никитин Ведущий администратор БД DBA.Team — Максим Милютин PostgreSQL Contributor, openGauss Contributor ... и многие другие. Регистрируйся, будет интересно! И бесплатно! Зарегистрироваться #реклама pgbootcamp.ru О рекламодателе

Задача: 1015. Smallest Integer Divisible by K Сложность: medium Задано целое положительное число k, необходимо найти длину наименьшего целого положительного числа n, такого, что n делится на k, и n содержит только цифру 1. Верните длину n. Если такого n не существует, верните -1. Примечание: n может не поместиться в 64-битное знаковое целое число. Пример:

Input: k = 1
Output: 1

👨‍💻 Алгоритм: 1⃣Использование остатка для нахождения числа с цифрами 1: Создайте переменную num и установите ее равной 1. Создайте переменную length и установите ее равной 1 для отслеживания длины числа. 2⃣Итеративное нахождение числа: Используйте цикл, чтобы умножать num на 10 и добавлять 1 в каждой итерации, и каждый раз вычисляйте остаток от деления num на k. Увеличивайте length на 1 в каждой итерации. Если в какой-то итерации num % k == 0, верните length. 3⃣Проверка бесконечного цикла: Если цикл длится слишком долго (например, 10^6 итераций), верните -1, чтобы предотвратить бесконечный цикл для случаев, когда решение не существует. 😎 Решение:

class Solution {
public:
    int smallestRepunitDivByK(int k) {
        int num = 1, length = 1;
        unordered_set<int> seen;
        
        while (num % k != 0) {
            if (seen.count(num % k)) {
                return -1;
            }
            seen.insert(num % k);
            num = (num * 10 + 1) % k;
            length++;
        }
        
        return length;
    }
};

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

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

Задача: 1372. Longest ZigZag Path in a Binary Tree Сложность: medium Вам дан корень бинарного дерева. Зигзагообразный путь для бинарного дерева определяется следующим образом: Выберите любой узел в бинарном дереве и направление (вправо или влево). Если текущее направление вправо, перейдите к правому дочернему узлу текущего узла; иначе перейдите к левому дочернему узлу. Измените направление с вправо на влево или с влево на вправо. Повторяйте второй и третий шаги, пока не сможете двигаться по дереву. Длина зигзагообразного пути определяется как количество посещенных узлов минус 1 (один узел имеет длину 0). Верните длину самого длинного зигзагообразного пути, содержащегося в этом дереве. Пример:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

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

#include <algorithm>

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

class Solution {
public:
    int maxLength = 0;

    int longestZigZag(TreeNode* root) {
        dfs(root, true, 0);
        dfs(root, false, 0);
        return maxLength;
    }

    void dfs(TreeNode* node, bool isLeft, int length) {
        if (!node) return;
        maxLength = std::max(maxLength, length);
        if (isLeft) {
            dfs(node->left, false, length + 1);
            dfs(node->right, true, 1);
        } else {
            dfs(node->right, true, length + 1);
            dfs(node->left, false, 1);
        }
    }
};

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

Задача: 684. Redundant Connection Сложность: medium В этой задаче дерево — это неориентированный граф, который является связным и не содержит циклов. Вам дан граф, который изначально был деревом с n узлами, пронумерованными от 1 до n, и к которому добавили одно дополнительное ребро. Добавленное ребро соединяет две разные вершины, выбранные из 1 до n, и это ребро не существовало ранее. Граф представлен массивом edges длины n, где edges[i] = [ai, bi] указывает на то, что существует ребро между узлами ai и bi в графе. Верните ребро, которое можно удалить, чтобы результирующий граф стал деревом из n узлов. Если существует несколько ответов, верните тот, который встречается последним в исходных данных. Пример:

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

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

#include <vector>
#include <unordered_set>
#include <array>

class Solution {
public:
    std::unordered_set<int> seen;
    static const int MAX_EDGE_VAL = 1000;

    std::vector<int> findRedundantConnection(std::vector<std::vector<int>>& edges) {
        std::array<std::vector<int>, MAX_EDGE_VAL + 1> graph;
        for (auto& edge : edges) {
            seen.clear();
            if (!graph[edge[0]].empty() && !graph[edge[1]].empty() && dfs(graph, edge[0], edge[1])) {
                return edge;
            }
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        throw std::runtime_error("No redundant connection found");
    }

    bool dfs(const std::array<std::vector<int>, MAX_EDGE_VAL + 1>& graph, int source, int target) {
        if (!seen.count(source)) {
            seen.insert(source);
            if (source == target) return true;
            for (int nei : graph[source]) {
                if (dfs(graph, nei, target)) return true;
            }
        }
        return false;
    }
};

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

Большая онлайн-конференция UserGate OpenConf ⚡ ИТ-конференция про защиту в открытую. Диалог между заказчиками, партнерами, экспертами и специалистами в сфере продуктов, технологий и услуг информационной безопасности. Зарегистрироваться #реклама 16+ openconf.usergate.com О рекламодателе

Задача: 1247. Minimum Swaps to Make Strings Equal Сложность: hard Вам даны две строки s1 и s2 одинаковой длины, состоящие только из букв "x" и "y". Ваша задача - сделать эти две строки равными друг другу. Вы можете поменять местами любые два символа, принадлежащие разным строкам, что означает: поменять местами s1[i] и s2[j]. Верните минимальное количество обменов, необходимое для того, чтобы сделать s1 и s2 равными, или верните -1, если это невозможно сделать. Пример:

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

👨‍💻 Алгоритм: 1⃣Подсчет несоответствующих пар: Пройдите по строкам s1 и s2, чтобы подсчитать количество пар xy и yx. Пара xy возникает, когда s1[i] равно 'x', а s2[i] равно 'y'. Пара yx возникает, когда s1[i] равно 'y', а s2[i] равно 'x'. 2⃣Проверка четности: Если сумма количества пар xy и yx нечетная, то невозможно сделать строки равными, поскольку каждая замена уменьшает сумму несоответствующих пар на 2. В этом случае верните -1. 3⃣Вычисление минимального количества замен: Если количество пар xy четное и количество пар yx четное, то каждые две пары xy и каждые две пары yx можно обменять за один ход. Поэтому минимальное количество замен равно xy // 2 + yx // 2. Если количество пар xy нечетное и количество пар yx нечетное, то мы можем обменять одну пару xy и одну пару yx за два хода. Поэтому минимальное количество замен равно xy // 2 + yx // 2 + 2. 😎 Решение:

class Solution {
public:
    int minimumSwap(string s1, string s2) {
        int xy = 0, yx = 0;
        for (int i = 0; i < s1.length(); ++i) {
            if (s1[i] == 'x' && s2[i] == 'y') {
                ++xy;
            } else if (s1[i] == 'y' && s2[i] == 'x') {
                ++yx;
            }
        }
        if ((xy + yx) % 2 != 0) {
            return -1;
        }
        return xy / 2 + yx / 2 + (xy % 2) * 2;
    }
};

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

Бесплатное льготное обучение: 3 месяца Мы ищем людей, которые хотят работать в IT-сфере из дома 💰 Оплата от 150.000 рублей в месяц Образование, место жительства, трудовой стаж — не важны! Подходит, как для подработки / декретного отпуска, так и для полной занятости. Если заинтересовались, то для старта нужно: — пройти короткий тест — заполнить анкету На что можно рассчитывать: ✅ удаленная работа ✅ зп от 150.000 рублей (потолка нет) ✅ стабильная подработка, если не хотите уходить с основной работы ⚡ Количество бесплатных мест ограничено. Успейте пройти тест и оставить заявку: Узнать больше #реклама technolium.ru О рекламодателе

Задача: 999. Available Captures for Rook Сложность: easy Вам дана матрица 8 x 8, изображающая шахматную доску. На ней есть ровно одна белая ладья, представленная символом "R", некоторое количество белых слонов "B" и некоторое количество черных пешек "p". Пустые клетки обозначаются символом '.'. Ладья может перемещаться на любое количество клеток по горизонтали или вертикали (вверх, вниз, влево, вправо), пока не достигнет другой фигуры или края доски. Ладья атакует пешку, если она может переместиться на ее клетку за один ход. Примечание: Ладья не может перемещаться через другие фигуры, такие как слоны или пешки. Это означает, что ладья не может атаковать пешку, если путь ей преграждает другая фигура. Верните количество пешек, которые атакует белая ладья. Пример:

Input: board = [[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".","R",".",".",".","p"],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".","p",".",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".","."]]

Output: 3

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

class Solution {
public:
    int numRookCaptures(vector<vector<char>>& board) {
        auto count_pawns = [&](int x, int y, int dx, int dy) {
            while (x >= 0 && x < 8 && y >= 0 && y < 8) {
                if (board[x][y] == 'B') break;
                if (board[x][y] == 'p') return 1;
                x += dx;
                y += dy;
            }
            return 0;
        };

        for (int i = 0; i < 8; ++i) {
            for (int j = 0; j < 8; ++j) {
                if (board[i][j] == 'R') {
                    return count_pawns(i, j, -1, 0) + count_pawns(i, j, 1, 0) +
                           count_pawns(i, j, 0, -1) + count_pawns(i, j, 0, 1);
                }
            }
        }
        return 0;
    }
};

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

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

Задача: 1160. Find Words That Can Be Formed by Characters Сложность: easy Вам дан массив строк words и строка chars. Строка считается хорошей, если она может быть составлена из символов chars (каждый символ может быть использован только один раз). Верните сумму длин всех хороших строк в words. Пример:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

👨‍💻 Алгоритм: 1⃣Создайте хеш-таблицу counts, которая будет записывать частоту каждого символа в chars. Инициализируйте переменную ans = 0. 2⃣Итерируйте по каждому слову в words. Создайте хеш-таблицу wordCount, которая будет записывать частоту каждого символа в слове. Установите good = true. Итерируйте по каждому ключу c в wordCount. Пусть freq = wordCount[c]. Если counts[c] < freq, установите good = false и прервите цикл. 3⃣Если good = true, добавьте длину слова к ans. Верните ans. 😎 Решение:

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        unordered_map<char, int> counts;
        for (char c : chars) {
            counts[c]++;
        }
        
        int ans = 0;
        for (string word : words) {
            unordered_map<char, int> wordCount;
            for (char c : word) {
                wordCount[c]++;
            }
            
            bool good = true;
            for (auto& [c, freq] : wordCount) {
                if (counts[c] < freq) {
                    good = false;
                    break;
                }
            }
            
            if (good) {
                ans += word.size();
            }
        }
        
        return ans;
    }
};

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

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

Задача: 1262. Greatest Sum Divisible by Three Сложность: medium Если задан целочисленный массив nums, верните максимально возможную сумму элементов массива, которая делится на три. Пример:

Input: nums = [3,6,5,1,8]
Output: 18

👨‍💻 Алгоритм: 1⃣Найдите сумму всех элементов массива. 2⃣Если сумма делится на 3, то она и есть ответ. 3⃣Если сумма при делении на 3 дает остаток 1, удалите один элемент с остатком 1 или два элемента с остатком 2 (если их сумма равна 2). Если сумма при делении на 3 дает остаток 2, удалите один элемент с остатком 2 или два элемента с остатком 1 (если их сумма равна 2). 😎 Решение:

class Solution {
public:
    int maxSumDivThree(vector<int>& nums) {
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        if (totalSum % 3 == 0) {
            return totalSum;
        }
        
        vector<int> mod1, mod2;
        for (int num : nums) {
            if (num % 3 == 1) {
                mod1.push_back(num);
            } else if (num % 3 == 2) {
                mod2.push_back(num);
            }
        }
        
        sort(mod1.begin(), mod1.end());
        sort(mod2.begin(), mod2.end());
        
        if (totalSum % 3 == 1) {
            int remove1 = mod1.empty() ? INT_MAX : mod1[0];
            int remove2 = mod2.size() < 2 ? INT_MAX : mod2[0] + mod2[1];
            return totalSum - min(remove1, remove2);
        } else {
            int remove2 = mod2.empty() ? INT_MAX : mod2[0];
            int remove1 = mod1.size() < 2 ? INT_MAX : mod1[0] + mod1[1];
            return totalSum - min(remove2, remove1);
        }
    }
};

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

Задача: 349. Intersection of Two Arrays Сложность: easy Даны два целочисленных массива nums1 и nums2. Верните массив их пересечения. Каждый элемент в результате должен быть уникальным, и вы можете вернуть результат в любом порядке. Пример:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

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

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1(nums1.begin(), nums1.end());
        unordered_set<int> set2(nums2.begin(), nums2.end());
        vector<int> result;
        for (int num : set1) {
            if (set2.find(num) != set2.end()) {
                result.push_back(num);
            }
        }
        return result;
    }
};

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

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

Задача: 1396. Design Underground System Сложность: medium Подземная железнодорожная система отслеживает время поездок пассажиров между различными станциями. Эти данные используются для вычисления среднего времени, необходимого для поездки от одной станции до другой. Реализуйте класс UndergroundSystem: - void checkIn(int id, string stationName, int t) Пассажир с карточкой, идентификатор которой равен id, регистрируется на станции stationName в момент времени t. Пассажир может быть зарегистрирован только в одном месте в одно и то же время. - void checkOut(int id, string stationName, int t) Пассажир с карточкой, идентификатор которой равен id, покидает станцию stationName в момент времени t. - double getAverageTime(string startStation, string endStation) Возвращает среднее время, необходимое для поездки от startStation до endStation. Среднее время вычисляется на основе всех предыдущих временных интервалов поездок от startStation до endStation, которые происходили непосредственно, т.е. регистрация на startStation с последующим выходом на endStation. Время, необходимое для поездки от startStation до endStation, может отличаться от времени поездки от endStation до startStation. Перед вызовом getAverageTime будет как минимум один пассажир, который уже совершил поездку от startStation до endStation. Вы можете предположить, что все вызовы методов checkIn и checkOut являются последовательными. Если пассажир регистрируется в момент времени t1, а затем выходит в момент времени t2, то t1 < t2. Все события происходят в хронологическом порядке. Пример:

Input
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]
Output
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]
Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30); // Customer 2 "Leyton" -> "Paradise" in 30-21 = 9
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 6.66667, (5 + 6 + 9) / 3 = 6.66667

👨‍💻 Алгоритм: 1⃣При регистрации на входе сохраняем информацию о начале пути (станция и время) в словаре checkInData. 2⃣При регистрации на выходе извлекаем информацию о начале пути из checkInData, вычисляем время поездки и обновляем статистику для маршрута в journeyData. 3⃣Для получения среднего времени поездки по заданному маршруту извлекаем статистику из journeyData и вычисляем среднее значение. 😎 Решение:

class UndergroundSystem {
    unordered_map<string, pair<double, double>> journeyData;
    unordered_map<int, pair<string, int>> checkInData;

public:
    void checkIn(int id, string stationName, int t) {
        checkInData[id] = {stationName, t};
    }

    void checkOut(int id, string stationName, int t) {
        auto [startStation, startTime] = checkInData[id];
        checkInData.erase(id);
        string routeKey = startStation + "->" + stationName;
        double tripTime = t - startTime;
        journeyData[routeKey].first += tripTime;
        journeyData[routeKey].second += 1;
    }

    double getAverageTime(string startStation, string endStation) {
        auto [totalTime, trips] = journeyData[startStation + "->" + endStation];
        return totalTime / trips;
    }
};

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