leetcode
leetcode 1301 ~ 1350
设计地铁系统

设计地铁系统

难度:

标签:

题目描述

代码结果

运行时间: 111 ms, 内存: 27.9 MB


import java.util.HashMap;
import java.util.Map;

class UndergroundSystem {
    private Map<Integer, CheckInData> checkInMap;
    private Map<String, TravelData> travelDataMap;

    public UndergroundSystem() {
        checkInMap = new HashMap<>();
        travelDataMap = new HashMap<>();
    }

    public void checkIn(int id, String stationName, int t) {
        checkInMap.put(id, new CheckInData(stationName, t));
    }

    public void checkOut(int id, String stationName, int t) {
        CheckInData checkInData = checkInMap.get(id);
        String route = checkInData.stationName + "," + stationName;
        int travelTime = t - checkInData.time;

        travelDataMap.computeIfAbsent(route, k -> new TravelData()).addTravelTime(travelTime);

        checkInMap.remove(id);
    }

    public double getAverageTime(String startStation, String endStation) {
        String route = startStation + "," + endStation;
        TravelData travelData = travelDataMap.get(route);
        return travelData.getAverageTime();
    }

    private static class CheckInData {
        String stationName;
        int time;

        CheckInData(String stationName, int time) {
            this.stationName = stationName;
            this.time = time;
        }
    }

    private static class TravelData {
        private int totalTime;
        private int tripCount;

        void addTravelTime(int time) {
            totalTime += time;
            tripCount++;
        }

        double getAverageTime() {
            return (double) totalTime / tripCount;
        }
    }
}

解释

方法:

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

时间复杂度:

O(1)

空间复杂度:

O(P + S)

代码细节讲解

🦆
在`checkIn`和`checkOut`方法中,如果一个乘客多次使用同一ID进站或在未进站的情况下尝试离站,系统是如何处理的?
在提供的代码中,并没有直接处理乘客使用相同ID多次进站或在未进站情况下尝试离站的情况。如果一个乘客多次使用同一ID进站,后一次的进站信息将会覆盖之前的记录,因此可能会导致数据不准确。如果在未进站的情况下尝试离站,由于`startInfo`字典中找不到对应的乘客ID,这将导致一个错误,比如在Python中可能会抛出`KeyError`。为了处理这些情况,可以在`checkIn`和`checkOut`方法中添加逻辑来检查和处理这些特殊情况,例如使用异常处理或在`checkOut`前验证进站记录是否存在。
🦆
解决方案中如何确保`startInfo`字典中的数据在`checkOut`后被适当管理,以避免内存泄漏或不必要的数据保留?
在当前的实现中,`checkOut`方法完成后,并没有从`startInfo`字典中移除对应的乘客信息。为了避免内存泄漏或不必要的数据保留,应在`checkOut`方法中,在计算完行程时间后删除对应的进站信息。这可以通过在`checkOut`方法里添加一行代码来实现,例如:`del self.startInfo[id]`,这样可以确保只有在乘客离站时才从字典中移除其记录。
🦆
在`checkOut`方法中,如果`startInfo`字典中不存在对应乘客ID的记录时,程序会如何处理?
在提供的代码示例中,如果`startInfo`字典中不存在对应乘客ID的记录,尝试访问该记录将导致抛出`KeyError`异常。为了使系统更加健壮,可以在`checkOut`方法中添加异常处理逻辑,如使用`try-except`结构来捕获这种异常,并提供适当的错误处理或者错误消息,确保程序的稳定性和用户的良好体验。
🦆
在并发环境下,这种字典操作是否安全,或者需要考虑加锁以防止数据竞争?
在并发环境下,直接操作字典可能不是线程安全的,这可能导致数据竞争或不一致的数据状态。为了确保数据的一致性和线程安全,可以考虑使用线程锁(如Python中的`threading.Lock`)。在每次修改字典之前获取锁,并在修改完成后释放锁,可以有效防止多个线程同时修改同一数据导致的问题。

相关问题