What is the primary pattern used in the "Design Underground System" problem?

The primary pattern is a combination of hash tables and string manipulation, used to track check-in times and calculate average travel times between stations.

How does the check-in and check-out system work in this problem?

Customers check in at a station with a timestamp, and when they check out at another station, the system calculates the total time between the two stations to compute the average travel time.

How do you calculate the average travel time between two stations?

The average travel time is calculated by dividing the total travel time between the stations by the number of trips between them.

What is the time complexity of this problem?

The time complexity for each method is O(1), as hash table lookups are constant time operations.

What should be the precision of the average time calculation?

The average time should be calculated with a precision of 5 decimal places.

#1396

Medium

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

设计地铁系统

地铁系统跟踪不同车站之间的乘客出行时间，并使用这一数据来计算从一站到另一站的平均时间。实现 UndergroundSystem 类： void checkIn(int id, string stationName, int t) 通行卡 ID 等于 id 的乘客，在时间 t ，从 stationN…

哈希表字符串设计

题目描述

地铁系统跟踪不同车站之间的乘客出行时间，并使用这一数据来计算从一站到另一站的平均时间。

实现 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 方法的所有调用都是符合逻辑的。如果一名乘客在时间 t₁ 进站、时间 t₂ 出站，那么 t₁ < t₂ 。所有时间都按时间顺序发生。

示例 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]

解释
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);  // 乘客 45 "Leyton" -> "Waterloo" ，用时 15-3 = 12
undergroundSystem.checkOut(27, "Waterloo", 20);  // 乘客 27 "Leyton" -> "Waterloo" ，用时 20-10 = 10
undergroundSystem.checkOut(32, "Cambridge", 22); // 乘客 32 "Paradise" -> "Cambridge" ，用时 22-8 = 14
undergroundSystem.getAverageTime("Paradise", "Cambridge"); // 返回 14.00000 。只有一个 "Paradise" -> "Cambridge" 的行程，(14) / 1 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // 返回 11.00000 。有两个 "Leyton" -> "Waterloo" 的行程，(10 + 12) / 2 = 11
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // 返回 11.00000
undergroundSystem.checkOut(10, "Waterloo", 38);  // 乘客 10 "Leyton" -> "Waterloo" ，用时 38-24 = 14
undergroundSystem.getAverageTime("Leyton", "Waterloo");    // 返回 12.00000 。有三个 "Leyton" -> "Waterloo" 的行程，(10 + 12 + 14) / 3 = 12

示例 2：

输入
["UndergroundSystem","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime","checkIn","checkOut","getAverageTime"]
[[],[10,"Leyton",3],[10,"Paradise",8],["Leyton","Paradise"],[5,"Leyton",10],[5,"Paradise",16],["Leyton","Paradise"],[2,"Leyton",21],[2,"Paradise",30],["Leyton","Paradise"]]

输出
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]

解释
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // 乘客 10 "Leyton" -> "Paradise" ，用时 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // 返回 5.00000 ，(5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // 乘客 5 "Leyton" -> "Paradise" ，用时 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // 返回 5.50000 ，(5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30); // 乘客 2 "Leyton" -> "Paradise" ，用时 30-21 = 9
undergroundSystem.getAverageTime("Leyton", "Paradise"); // 返回 6.66667 ，(5 + 6 + 9) / 3 = 6.66667

提示：

1 <= id, t <= 10⁶
1 <= stationName.length, startStation.length, endStation.length <= 10
所有字符串由大小写英文字母与数字组成
总共最多调用 checkIn、checkOut 和 getAverageTime 方法 2 * 10⁴ 次
与标准答案误差在 10^-5 以内的结果都被视为正确结果

lightbulb

解题思路

方法一：哈希表

我们用两个哈希表来存储数据，其中：

ts：存储乘客的 id 和乘客的进站时间和进站站点。其中键为乘客的 id，值为元组 (t, stationName)。
d：存储乘客的进站站点和出站站点，以及乘客的行程时间和行程次数。其中键为元组 (startStation, endStation)，值为元组 (totalTime, count)。

当乘客进站时，我们将乘客的 id 和进站时间和进站站点存入 ts 中，即 ts[id] = (t, stationName)。

当乘客出站时，我们从 ts 中取出乘客的进站时间和进站站点 (t0, station)，然后计算乘客的行程时间 $t - t_0$ ，并将乘客的行程时间和行程次数存入 d 中。

当我们要求某个乘客的平均行程时间时，我们从 d 中取出乘客的行程时间和行程次数 (totalTime, count)，然后计算平均行程时间 $totalTime / count$ 即可。

时间复杂度 $O(1)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为乘客的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class UndergroundSystem:
    def __init__(self):
        self.ts = {}
        self.d = {}

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.ts[id] = (t, stationName)

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        t0, station = self.ts[id]
        x = self.d.get((station, stationName), (0, 0))
        self.d[(station, stationName)] = (x[0] + t - t0, x[1] + 1)

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        x = self.d[(startStation, endStation)]
        return x[0] / x[1]


# Your UndergroundSystem object will be instantiated and called as such:
# obj = UndergroundSystem()
# obj.checkIn(id,stationName,t)
# obj.checkOut(id,stationName,t)
# param_3 = obj.getAverageTime(startStation,endStation)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of hash table usage in managing time and space complexities.
question_mark
Assess the ability to handle multiple events and efficient data retrieval.
question_mark
Check for clarity in implementing the getAverageTime method and ensuring precision.

warning

常见陷阱

外企场景

error
Failing to correctly pair check-ins and check-outs for each customer, leading to incorrect calculations.
error
Inadequate handling of edge cases, such as the first check-in for a station pair.
error
Incorrect average time calculation, especially in handling precision up to 5 decimal places.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handle different station names or a higher number of station pairs.
arrow_right_alt
Optimize for scenarios where the system is under high traffic, with a large number of events.
arrow_right_alt
Consider adding features such as a real-time station occupancy tracker alongside travel time tracking.

help

常见问题

外企场景

继续练习

#981 基于时间的键值存储 #745 前缀和后缀搜索 #677 键值映射