当前位置：首页 > article >正文

Leetcode 1396. 设计地铁系统

article 2025/1/18 12:49:52

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