LeetCode 1396. Design Undergroun

问题描述

实现 UndergroundSystem 类，使其支持如下三个函数：

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

   • 一个卡片 id 为 id 的用户，在 t 时进站 stationName。
   • 一个用户在某个时间点只能进入一个站点。

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

   • 一个卡片 id 为 id 的用户，在 t 时出站 stationName。

3. getAverageTime(string startStation, string endStation)

   • 返回出发地为 startStation，到达地为 endStation 的平均旅程时间。
   • 平均时间由之前所有从 startStation 直达 endStation 的旅程计算而来。
   • 对 getAverageTime 的调用总是有效。

你可以假设对 checkIn 和 checkOut 的调用是一致的。也就是说，当一个用户在 t1 时进站，在 t2 时出站，满足 t2 > t1。所有事件都是按时间顺序发生。

栗 1：

输入：

["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"]]

输出：

[null,null,null,null,null,null,null,14.00000,11.00000,null,11.00000,null,12.00000]

解释：

1. 第一次调用 getAverageTime，此时旅程信息如下：

{
  'Leyton-Waterloo' => [ { id: 45, interval: 12 }, { id: 27, interval: 10 } ],
  'Paradise-Cambridge' => [ { id: 32, interval: 14 } ] 
}

Paradise-Cambridge 的平均值为：14。

2. 第二次调用 getAverageTime，此时旅程信息如下：

{
  'Leyton-Waterloo' => [ { id: 45, interval: 12 }, { id: 27, interval: 10 } ],
  'Paradise-Cambridge' => [ { id: 32, interval: 14 } ] 
}

Leyton-Waterloo 的平均值为：11 = (12 + 10) / 2。

3. 第三次调用 getAverageTime，此时旅程信息如下：

{
  'Leyton-Waterloo' => [ { id: 45, interval: 12 }, { id: 27, interval: 10 } ],
  'Paradise-Cambridge' => [ { id: 32, interval: 14 } ] 
}

Leyton-Waterloo 的平均值为：11 = (12 + 10) / 2。

4. 第四次调用 getAverageTime，此时旅程信息如下：

{
  'Leyton-Waterloo' => [ { id: 45, interval: 12 },
    { id: 27, interval: 10 },
    { id: 10, interval: 14 } ],
  'Paradise-Cambridge' => [ { id: 32, interval: 14 } ] 
}

Leyton-Waterloo 的平均值为：12 = (12 + 10 + 14) / 3。

注意：

• 最多有 20000 个操作。
• 1 <= id, t <= 10^6。
• 所有的字符串包括大小写字母和数字。
• 1 <= stationName.length <= 10。
• 答案与实际值相差在 10^-5 以内都是正确的。

想看英文原文的戳这里。

解题思路

这道题的思路比较简单。由于进站和出站是有先后顺序的，也就是说当出站时，一定有对应的进站信息。那么当调用 checkout 时，便可以计算出某个用户在这段旅程上花费的时间。

而题目要求计算出给定起始点的旅程所花费的平均时间，那么得知道该路线对应的所有旅程信息，即需要记录所有用户在该路线上的旅程时间。而上面我们提到，某个用户在某段旅程上花费的时间是可以计算出来的。

为了快速得到所有旅程信息，能比较容易的想到使用 map 来进行存储。我们只需要将起始点作为 key，将各用户旅程时间记录下来即可。这是一种一对多的关系，即 { key: [t1, t2] }。

以上分析对应如下实现：

• checkin， 记录用户 id 的进站信息。
• checkout ，查找用户 id 的进站信息，计算旅程时长 t，并将其添加到该路线对应的旅程时间列表中。
• getAverageTime，根据起始点，获取路线对应的所有旅程时间列表，计算平均时间。

js 代码如下：

var UndergroundSystem = function () {

};

// 记录用户的旅程
UndergroundSystem.prototype.customerMap = new Map()

// 记录路线对应的时间信息
UndergroundSystem.prototype.stationMap = new Map()


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

  let checkInfo = {
    startStation: stationName,
    startTime: t
  }

  // 记录进入信息
  this.customerMap.set(id, checkInfo)
};

/** 
 * @param {number} id 
 * @param {string} stationName 
 * @param {number} t
 * @return {void}
 */
UndergroundSystem.prototype.checkOut = function (id, stationName, t) {

  if (this.customerMap.has(id)) {
    // 如果有进入过
    const checkInInfo = this.customerMap.get(id)
    if (checkInInfo) {
      const { startStation, startTime } = checkInInfo

      // 起始点
      const stationKey = `${startStation}-${stationName}`

      // 时间间隔
      const interval = t - startTime

      const stationInfo = {
        id,
        interval
      }

      // 记录起始点对应的信息
      let list
      if (this.stationMap.has(stationKey)) {
        list = this.stationMap.get(stationKey)
      } else {
        list = new Array()
      }

      list.push(stationInfo)
      this.stationMap.set(stationKey, list)
    }
  } else {
    console.log('error! no checkIn')
  }
};

/** 
 * @param {string} startStation 
 * @param {string} endStation
 * @return {number}
 */
UndergroundSystem.prototype.getAverageTime = function (startStation, endStation) {

  console.log(this.stationMap)

  const stationKey = `${startStation}-${endStation}`
  if (this.stationMap.has(stationKey)) {
    const list = this.stationMap.get(stationKey)
    if (list.length > 0) {
      // 计算总时间
      let totalTime = 0
      list.map((info) => {
        totalTime += info.interval
      })

      return totalTime / list.length
    }
  }

  return 0
};