1396. Design Underground System

Leetcode link

解题思路

题目要求我们实现一个 UndergroundSystem 类，该类有三个方法：

• checkIn：记录某个用户的 id，进站的站名，进站的时间
• checkOut：记录某个用户的 id，出站的站名，出站的时间
• getAverageTime：返回所有直接从站 A 到坐到站 B 的乘客所花的平均时间

另外题目还保证了用户只要进站就会出站，且出站时间一定比进站时间晚。

有了以上信息，我们可以构造两个映射表：

1. routeTime：它保存了从站 A 到站 B 的路线名称与记录所有旅客旅行时间的数组
   • { “startStation_endStation”: [routeTime1, routeTime2, ...] }
2. checkInInfo：它保存了用户 A 的 Uid 与进站站名，进站时间
   • { Uid: [stationName, time] }

下一步，我们可以借助映射表保存的数据，对三个方法进行操作：

• checkIn：把用户的 id，进站的站名，进站的时间保存到 checkInInfo 中
• checkOut：根据 checkInInfo，找出有同样 id 的进站用户，拼接进出站名称，然后跟经过时间一起保存到 routeTime 中
• getAverageTime：根据 routeTime 中的数据，给用户的旅行时间求一个平均值并返回

C++

class UndergroundSystem {
 private:
  //  {startStation_endStation: [routeTime1, routeTime2, ...]}
  unordered_map<string, vector<int>> routeTime;
  //   {Uid: [stationName, time]}
  unordered_map<int, pair<string, int>> checkInInfo;

 public:
  UndergroundSystem() {}

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

  void checkOut(int id, string stationName, int t) {
    string station = checkInInfo[id].first + "_" + stationName;
    int time = t - checkInInfo[id].second;
    routeTime[station].push_back(time);
  }

  double getAverageTime(string startStation, string endStation) {
    string station = startStation + "_" + endStation;
    int totalTime = 0;
    int count = 0;
    for (auto &time : routeTime[station]) {
      totalTime += time;
      count++;
    }
    // 题目要求输出 double
    return (double)totalTime / count;
  }
};

Javascript

var UndergroundSystem = function() {
    //  {startStation_endStation: [routeTime1, routeTime2, ...]}
    this.routeTime = {};
    //   {Uid: [stationName, time]}
    this.checkInInfo = {};
};

/** 
 * @param {number} id 
 * @param {string} stationName 
 * @param {number} t
 * @return {void}
 */
UndergroundSystem.prototype.checkIn = function(id, stationName, t) {
    this.checkInInfo[id] = [stationName, t];
};

/** 
 * @param {number} id 
 * @param {string} stationName 
 * @param {number} t
 * @return {void}
 */
UndergroundSystem.prototype.checkOut = function(id, stationName, t) {
    const station = this.checkInInfo[id][0] + "_" + stationName;
    const time = t - this.checkInInfo[id][1];
    (this.routeTime[station] === undefined) && (this.routeTime[station] = []);
    this.routeTime[station].push(time);
};

/** 
 * @param {string} startStation 
 * @param {string} endStation
 * @return {number}
 */
UndergroundSystem.prototype.getAverageTime = function(startStation, endStation) {
    const station = startStation + "_" + endStation;
    let totalTime = 0;
    let count = 0;
    for (let time of this.routeTime[station]) {
      totalTime += time;
      count++;
    }
    return totalTime / count;
};