题目

Implement the class UndergroundSystem that supports three methods:

1.checkIn(int id, string stationName, int t)

  • A customer with id card equal to id, gets in the station stationName at time t.
  • A customer can only be checked into one place at a time.

2.checkOut(int id, string stationName, int t)

  • A customer with id card equal to id, gets out from the station stationName at time t.

3.getAverageTime(string startStation, string endStation)

  • Returns the average time to travel between the startStation and the endStation.
  • The average time is computed from all the previous traveling from startStation to endStation that happened directly.
  • Call to getAverageTime is always valid.

You can assume all calls to checkIn and checkOut methods are consistent. That is, if a customer gets in at time t1 at some station, then it gets out at time t2 with t2 > t1. All events happen in chronological order.

Example 1:

  1. Input
  2. ["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
  3. [[],[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"]]
  5. Output
  6. [null,null,null,null,null,null,null,14.0,11.0,null,11.0,null,12.0]
  8. Explanation
  9. UndergroundSystem undergroundSystem = new UndergroundSystem();
  10. undergroundSystem.checkIn(45, "Leyton", 3);
  11. undergroundSystem.checkIn(32, "Paradise", 8);
  12. undergroundSystem.checkIn(27, "Leyton", 10);
  13. undergroundSystem.checkOut(45, "Waterloo", 15);
  14. undergroundSystem.checkOut(27, "Waterloo", 20);
  15. undergroundSystem.checkOut(32, "Cambridge", 22);
  16. undergroundSystem.getAverageTime("Paradise", "Cambridge");       // return 14.0. There was only one travel from "Paradise" (at time 8) to "Cambridge" (at time 22)
  17. undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.0. There were two travels from "Leyton" to "Waterloo", a customer with id=45 from time=3 to time=15 and a customer with id=27 from time=10 to time=20. So the average time is ( (15-3) + (20-10) ) / 2 = 11.0
  18. undergroundSystem.checkIn(10, "Leyton", 24);
  19. undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.0
  20. undergroundSystem.checkOut(10, "Waterloo", 38);
  21. undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 12.0

Constraints:

  • There will be at most 20000 operations.
  • 1 <= id, t <= 10^6
  • All strings consist of uppercase, lowercase English letters and digits.
  • 1 <= stationName.length <= 10
  • Answers within 10^-5 of the actual value will be accepted as correct.

题意

实现一个地铁系统类的三个方法。

思路

使用两个HashMap处理：

  1. 第一个map记录编号id的乘客的入站信息；
  2. 第二个map记录线路’A-B’对应的行驶总用时和行驶次数。

代码实现

Java

  1. class UndergroundSystem {
  2.     private Map<Integer, Object[]> start;
  3.     private Map<String, int[]> route;
  5.     public UndergroundSystem() {
  6.         start = new HashMap<>();
  7.         route = new HashMap<>();
  8.     }
  10.     public void checkIn(int id, String stationName, int t) {
  11.         start.putIfAbsent(id, new Object[2]);
  12.         Object[] list = start.get(id);
  13.         list[0] = stationName;
  14.         list[1] = t;
  15.     }
  17.     public void checkOut(int id, String stationName, int t) {
  18.         Object[] info = start.get(id);
  19.         String routeName = (String) info[0] + '-' + stationName;
  20.         int prev = (int) info[1];
  22.         route.putIfAbsent(routeName, new int[2]);
  23.         int[] list = route.get(routeName);
  24.         list[0] += t - prev;
  25.         list[1]++;
  26.     }
  28.     public double getAverageTime(String startStation, String endStation) {
  29.         String routeName = startStation + '-' + endStation;
  30.         int[] list = route.get(routeName);
  32.         return 1.0 * list[0] / list[1];
  33.     }
  34. }

JavaScript

  1. var UndergroundSystem = function () {
  2.   this.travel = new Map()
  3.   this.record = new Map()
  4. }
  6. /**
  7.  * @param {number} id
  8.  * @param {string} stationName
  9.  * @param {number} t
  10.  * @return {void}
  11.  */
  12. UndergroundSystem.prototype.checkIn = function (id, stationName, t) {
  13.   this.travel.set(id, [stationName, t])
  14. }
  16. /**
  17.  * @param {number} id
  18.  * @param {string} stationName
  19.  * @param {number} t
  20.  * @return {void}
  21.  */
  22. UndergroundSystem.prototype.checkOut = function (id, stationName, t) {
  23.   const from = this.travel.get(id)[0]
  24.   const to = stationName
  25.   const interval = t - this.travel.get(id)[1]
  27.   if (!this.record.has(from)) {
  28.     this.record.set(from, new Map())
  29.   }
  30.   if (!this.record.get(from).has(to)) {
  31.     this.record.get(from).set(to, [])
  32.   }
  33.   this.record.get(from).get(to).push(interval)
  35.   this.travel.delete(id)
  36. }
  38. /**
  39.  * @param {string} startStation
  40.  * @param {string} endStation
  41.  * @return {number}
  42.  */
  43. UndergroundSystem.prototype.getAverageTime = function (startStation, endStation) {
  44.   const arr = this.record.get(startStation).get(endStation)
  45.   return arr.reduce((acc, cur) => acc + cur) / arr.length
  46. }