LeetCode 1396. Design Underground System

关注
发布于: 2020 年 05 月 05 日
LeetCode 1396. Design Underground System
@(LeetCode)
问题描述﻿
实现 UndergroundSystem 类，使其支持如下三个函数：
﻿
checkIn(int id, string stationName, int t)
﻿
一个卡片 id 为 id 的用户，在 t 时进站 stationName。
一个用户在某个时间点只能进入一个站点。
	
checkOut(int id, string stationName, int t)
﻿
一个卡片 id 为 id 的用户，在 t 时出站 stationName。
	
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]
﻿
解释：
﻿
第一次调用 getAverageTime，此时旅程信息如下：
{
  'Leyton-Waterloo' => [ { id: 45, interval: 12 }, { id: 27, interval: 10 } ],
  'Paradise-Cambridge' => [ { id: 32, interval: 14 } ] 
}
Paradise-Cambridge 的平均值为：14。
﻿
第二次调用 getAverageTime，此时旅程信息如下：
{
  'Leyton-Waterloo' => [ { id: 45, interval: 12 }, { id: 27, interval: 10 } ],
  'Paradise-Cambridge' => [ { id: 32, interval: 14 } ] 
}
Leyton-Waterloo 的平均值为：11 = (12 + 10) / 2。
﻿
第三次调用 getAverageTime，此时旅程信息如下：
{
  'Leyton-Waterloo' => [ { id: 45, interval: 12 }, { id: 27, interval: 10 } ],
  'Paradise-Cambridge' => [ { id: 32, interval: 14 } ] 
}
Leyton-Waterloo 的平均值为：11 = (12 + 10) / 2。
﻿
第四次调用 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 以内都是正确的。
﻿
想看英文原文的戳这里：https://leetcode.com/problems/design-underground-system。
解题思路﻿
这道题的思路比较简单。由于进站和出站是有先后顺序的，也就是说当出站时，一定有对应的进站信息。那么当调用 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
};
﻿
发布于: 2020 年 05 月 05 日阅读数: 48
原文链接:【http://xie.infoq.cn/article/3cccbe1dd22c92df48de84010】。
liu_liu

关注
不要相信自己的记忆力 2017.11.13 加入
还未添加个人简介
发布
暂无评论
创作场景

LeetCode 1396. Design Underground System

问题描述

解题思路

liu_liu

评论
