1.题目基本信息
1.1.题目描述
地铁系统跟踪不同车站之间的乘客出行时间,并使用这一数据来计算从一站到另一站的平均时间。
实现 UndergroundSystem 类:
- void checkIn(int id, string stationName, int t)
-
- 通行卡 ID 等于 id 的乘客,在时间 t ,从 stationName 站进入
-
- 乘客一次只能从一个站进入
- void checkOut(int id, string stationName, int t)
-
- 通行卡 ID 等于 id 的乘客,在时间 t ,从 stationName 站离开
- double getAverageTime(string startStation, string endStation)
-
- 返回从 startStation 站到 endStation 站的平均时间
-
- 平均时间会根据截至目前所有从 startStation 站 直接 到达 endStation 站的行程进行计算,也就是从 startStation 站进入并从 endStation 离开的行程
-
- 从 startStation 到 endStation 的行程时间与从 endStation 到 startStation 的行程时间可能不同
-
- 在调用 getAverageTime 之前,至少有一名乘客从 startStation 站到达 endStation 站
你可以假设对 checkIn 和 checkOut 方法的所有调用都是符合逻辑的。如果一名乘客在时间 t1 进站、时间 t2 出站,那么 t1 < t2 。所有时间都按时间顺序发生。
1.2.题目地址
https://leetcode.cn/problems/design-underground-system/description
2.解题方法
2.1.解题思路
设计俩哈希表进行存储: 第一张哈希表(临时记录进站信息用): 用户ID->(最近的进站站点,最近的进站时间); 第二张哈希表(直接对应getAverageTime函数,快速计算平均时间用): (进站ID,出站ID)->(总时间,总人数)。
2.2.解题步骤
第一步,设计存储的数据结构。
第二步,当用户id进入stationName站时,将该用户的进站站点和进入时间信息记录到map1。
第三步,当用户出站时,将map2中(出站,进站)路线的总时间和总人数更新一下。
第四步,直接根据出站和进站信息获取该路线的总时间和总人数,相除即可获取平均时间。
3.解题代码
Python代码
class UndergroundSystem:
# 关键: 设计俩哈希表进行存储: 第一张哈希表(临时记录进站信息用): 用户ID->(最近的进站站点,最近的进站时间); 第二张哈希表(直接对应getAverageTime函数,快速计算平均时间用): (进站ID,出站ID)->(总时间,总人数)。
# 第一步,设计存储的数据结构。第二步,当用户id进入stationName站时,将该用户的进站站点和进入时间信息记录到map1。第三步,当用户出站时,将map2中(出站,进站)路线的总时间和总人数更新一下。第四步,直接根据出站和进站信息获取该路线的总时间和总人数,相除即可获取平均时间。
def __init__(self):
self.map1={}
self.map2={}
def checkIn(self, id: int, stationName: str, t: int) -> None:
self.map1[id]=(stationName,t)
def checkOut(self, id: int, stationName: str, t: int) -> None:
inStationName,inTime=self.map1[id]
key=(inStationName,stationName)
if key in self.map2:
self.map2[key]=[self.map2[key][0]+t-inTime,self.map2[key][1]+1]
else:
self.map2[key]=[t-inTime,1]
def getAverageTime(self, startStation: str, endStation: str) -> float:
timeSum,personsCnt=self.map2[(startStation,endStation)]
return timeSum/personsCnt