设计地铁系统
难度:
标签:
题目描述
代码结果
运行时间: 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进站或在未进站的情况下尝试离站,系统是如何处理的?
▷🦆
解决方案中如何确保`startInfo`字典中的数据在`checkOut`后被适当管理,以避免内存泄漏或不必要的数据保留?
▷🦆
在`checkOut`方法中,如果`startInfo`字典中不存在对应乘客ID的记录时,程序会如何处理?
▷🦆
在并发环境下,这种字典操作是否安全,或者需要考虑加锁以防止数据竞争?
▷