跳至主要内容

1396. Design Underground System

題意

  • 設計一個地鐵系統,含有幾個function

    • void checkIn(int id, string stationName, int t)

      • idstationName 的進站時間 t
    • void checkOut(int id, string stationName, int t)

      • idstationName的出站時間 t
    • double getAverageTime(string startStation, string endStation)

      • 計算兩個站之間平均進出站花費時間

      • 進出站相反的狀況,花費時間可能會不同

  • 假設每次 call getAverageTime的時候資料都已經有了

限制

  • 1 <= id, t <= 10610^6

  • 1 <= stationName.length, startStation.length, endStation.length <= 10

  • All strings consist of uppercase and lowercase English letters and digits.

  • There will be at most 2 * 10410^4 calls in total to checkIn, checkOut, and getAverageTime.

  • Answers within 10510^{-5} of the actual value will be accepted.

題目思考

  • checkOut被call的時間不固定,因此需要先建好 id的辨識方法以提供cheukout時可以拿到資料計算

  • 每次有人 checkOut 都更新 startStation - endStation的資料供查詢

Coding流程

  • 給一組 unordered_map<int, pair<string, int>> customers,代表搭車中的乘客 id ⇒ { stationName, t }

  • 給一組 unordered_map<string, pair<long, int>> routes,代表當前地圖資料

    • string“${startStation}-${endStation}” 的字串,作為兩站之間的唯一辨識符

    • pair<long, int>(總花費時間, 人次)

  • 每次 checkIn,往 customers 增加對應的進站資料

  • 每次 checkOut,取出 customers中相同id的資料,並更新 routes

  • getAverageTime,從 routes 取出對應的資料並計算平均值

Solution

class UndergroundSystem {
private:
unordered_map<int, pair<string, int>> customers;
unordered_map<string, pair<long, int>> routes;
public:
UndergroundSystem() {

}

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

void checkOut(int id, string stationName, int t) {
int time = t - customers[id].second;
string routingKey = customers[id].first + "-" + stationName;
routes[routingKey].first += time;
routes[routingKey].second += 1;

customers.erase(id);
}

double getAverageTime(string startStation, string endStation) {
string routingKey = startStation + "-" + endStation;
return (double) routes[routingKey].first / routes[routingKey].second;
}
};

/**
* 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);
*/