1396. Проектирование подземной системы LeetCode Solution.

Вопрос:

Ссылка: https://leetcode.com/problems/design-underground-system/

Подземная железнодорожная система отслеживает время в пути клиентов между различными станциями. Они используют эти данные для расчета среднего времени, необходимого для перемещения от одной станции к другой.

Реализуйте класс 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.
• Будет хотя бы один клиент, который проехал от startStation до endStation до звонка getAverageTime.

Вы можете предположить, что все вызовы методов checkIn и checkOut согласованы. Если клиент регистрируется в t1, затем выезжает в t2, а затем в t1 < t2. Все события происходят в хронологическом порядке.

Пример 1:

Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]
Output
[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]
Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);  // Customer 45 "Leyton" -> "Waterloo" in 15-3 = 12
undergroundSystem.checkOut(27, "Waterloo", 20);  // Customer 27 "Leyton" -> "Waterloo" in 20-10 = 10
undergroundSystem.checkOut(32, "Cambridge", 22); // Customer 32 "Paradise" -> "Cambridge" in 22-8 = 14
undergroundSystem.getAverageTime("Paradise", "Cambridge"); // return 14.00000. One trip "Paradise" -> "Cambridge", (14) / 1 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 11.00000. Two trips "Leyton" -> "Waterloo", (10 + 12) / 2 = 11
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 11.00000
undergroundSystem.checkOut(10, "Waterloo", 38);  // Customer 10 "Leyton" -> "Waterloo" in 38-24 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // return 12.00000. Three trips "Leyton" -> "Waterloo", (10 + 12 + 14) / 3 = 12

Пример 2:

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 <= id, t <= 106
• 1 <= stationName.length, startStation.length, endStation.length <= 10
• Все строки состоят из прописных и строчных английских букв и цифр.
• Всего будет всего 2 * 104 звонков на номера checkIn, checkOut и getAverageTime.
• Будут приняты ответы в пределах 10-5 фактического значения.

Решение:

Подход:

Приведенный выше код реализует класс UndergroundSystem, представляющий подземную транспортную систему. Он отслеживает время регистрации и выезда клиентов и предоставляет функциональные возможности для расчета среднего времени в пути между различными станциями.

В классе есть следующие методы:

1. UndergroundSystem(): Конструктор для инициализации подземной системы.
2. checkIn(int id, string stationName, int t): записывает время регистрации клиента с заданными id, stationName и t (время).
3. checkOut(int id, string stationName, int t): записывает время выезда клиента с заданными id, stationName и t (время). Он вычисляет время в пути между станциями регистрации и выезда и сохраняет его в структуре данных m (карта).
4. getAverageTime(string startStation, string endStation): вычисляет и возвращает среднее время в пути между startStation и endStation на основе записанного времени заезда и выезда, хранящегося на карте m.

Структуры данных, используемые в реализации:

• m1: unordered_map для хранения сведений о регистрации клиентов (id -> (название станции, время)).
• m2: unordered_map для хранения информации о кассах клиентов (id -> (название станции, время)).
• m: unordered_map для хранения времени в пути между станциями (startStation -> endStation -> вектор пар времени в пути).

Временная и пространственная сложность каждого метода следующая:

1. UndergroundSystem(): Конструктор имеет временную сложность O(1), поскольку он не выполняет никаких значительных операций. Сложность пространства также O (1).
2. checkIn(int id, string stationName, int t): Метод регистрации имеет временную сложность O(1), так как выполняет простые операции присваивания. Сложность пространства составляет O(1), так как она добавляет одну запись на карту m1.
3. checkOut(int id, string stationName, int t): Метод проверки имеет временную сложность O(1), поскольку он выполняет простые операции присваивания и добавляет запись на карту m. Сложность пространства составляет O(1), так как она добавляет одну запись к карте m2 и карте m.
4. getAverageTime(string startStation, string endStation): метод расчета среднего времени в пути имеет временную сложность O(n), где n — количество записанных времен в пути между startStation и endStation. Он перебирает вектор пар времени в пути и вычисляет сумму времени в пути. Сложность пространства составляет O (1), поскольку для расчета используется только несколько переменных.

Код:

class UndergroundSystem {
public:
    unordered_map<int,pair<string,int>> m1,m2;
    unordered_map<string,vector<pair<int,int>>> m;
    UndergroundSystem() {
        
    }
    
    void checkIn(int id, string stationName, int t) {
        m1[id]={stationName,t};
    }
    
    void checkOut(int id, string stationName, int t) {
        m2[id]={stationName,t};
        string ans="";
        ans+=m1[id].first;
        ans+="->";
        ans+=m2[id].first;
        m[ans].push_back({m1[id].second,m2[id].second});
    }
    
    double getAverageTime(string startStation, string endStation) {
        string tempo=startStation + "->" + endStation;
        auto x = m[tempo];
        double a=0.0;
        int n=x.size();
        for(auto y:x){
            a+=(double)(y.second-y.first);
        }
        return (double)(a/n);
    }
};

/**
 * Your UndergroundSystem object will be instantiated and called as such:
 * UndergroundSystem* obj = new UndergroundSystem();
 * obj->checkIn(id,stationName,t);
 * obj->checkOut(id,stationName,t);
 * double param_3 = obj->getAverageTime(startStation,endStation);
 */

Временная сложность: O(N)

Космическая сложность: O(1)

Заключение:

У нас есть два подхода к данной постановке задачи. Надеюсь, что решение окажется полезным и вам, ребята, понравилось. Давайте обсудим новые подходы.

Удачного кодирования.