设计地铁系统

标签: 设计 哈希表 字符串

难度: Medium

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

实现 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：

输入
["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 <= 106
  • 1 <= stationName.length, startStation.length, endStation.length <= 10 次
  • 所有字符串由大小写英文字母与数字组成
  • 总共最多调用 checkIn、checkOut 和 getAverageTime 方法 2 * 104
  • 与标准答案误差在 10-5 以内的结果都被视为正确结果

Submission

运行时间: 111 ms

内存: 27.9 MB

class UndergroundSystem:

    def __init__(self):
        self.startInfo = dict()
        self.table = dict()

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

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        startTime = self.startInfo[id][1]
        index = (self.startInfo[id][0], stationName)
        rec = self.table.get(index, (0, 0))
        self.table[index] = (rec[0] + t - startTime, rec[1] + 1)


    def getAverageTime(self, startStation: str, endStation: str) -> float:
        index = (startStation, endStation)
        sum, amount = self.table[index]
        return sum / amount




# 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)

Explain

这个解决方案使用了两个主要的字典结构来管理地铁系统的数据。首先，`startInfo` 字典用来存储每个乘客的进站信息，包括进站的车站名和时间。当乘客离站时，使用 `checkOut` 方法计算该乘客的行程时间并更新 `table` 字典。`table` 字典用来存储从一个车站到另一个车站的总行程时间和行程次数。键是一个包含起始站和终点站的元组，值是一个包含总时间和行程次数的元组。最后，`getAverageTime` 方法通过查找 `table` 字典中相应的记录来计算平均时间。

时间复杂度: O(1)

空间复杂度: O(P + S)

class UndergroundSystem:

    def __init__(self):
        self.startInfo = dict()  # 存储每个乘客的进站信息
        self.table = dict()  # 存储站对应的行程数据

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.startInfo[id] = (stationName, t)  # 记录乘客进站时间和站点

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        startTime = self.startInfo[id][1]
        index = (self.startInfo[id][0], stationName)
        rec = self.table.get(index, (0, 0))
        self.table[index] = (rec[0] + t - startTime, rec[1] + 1)  # 更新行程总时间和次数

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        index = (startStation, endStation)
        sum, amount = self.table[index]
        return sum / amount  # 计算平均时间

Explore

在提供的代码中，并没有直接处理乘客使用相同ID多次进站或在未进站情况下尝试离站的情况。如果一个乘客多次使用同一ID进站，后一次的进站信息将会覆盖之前的记录，因此可能会导致数据不准确。如果在未进站的情况下尝试离站，由于`startInfo`字典中找不到对应的乘客ID，这将导致一个错误，比如在Python中可能会抛出`KeyError`。为了处理这些情况，可以在`checkIn`和`checkOut`方法中添加逻辑来检查和处理这些特殊情况，例如使用异常处理或在`checkOut`前验证进站记录是否存在。

在当前的实现中，`checkOut`方法完成后，并没有从`startInfo`字典中移除对应的乘客信息。为了避免内存泄漏或不必要的数据保留，应在`checkOut`方法中，在计算完行程时间后删除对应的进站信息。这可以通过在`checkOut`方法里添加一行代码来实现，例如：`del self.startInfo[id]`，这样可以确保只有在乘客离站时才从字典中移除其记录。

在提供的代码示例中，如果`startInfo`字典中不存在对应乘客ID的记录，尝试访问该记录将导致抛出`KeyError`异常。为了使系统更加健壮，可以在`checkOut`方法中添加异常处理逻辑，如使用`try-except`结构来捕获这种异常，并提供适当的错误处理或者错误消息，确保程序的稳定性和用户的良好体验。

在并发环境下，直接操作字典可能不是线程安全的，这可能导致数据竞争或不一致的数据状态。为了确保数据的一致性和线程安全，可以考虑使用线程锁（如Python中的`threading.Lock`）。在每次修改字典之前获取锁，并在修改完成后释放锁，可以有效防止多个线程同时修改同一数据导致的问题。