Сложность: medium
Подземная железнодорожная система отслеживает время поездок пассажиров между различными станциями. Эти данные используются для вычисления среднего времени, необходимого для поездки от одной станции до другой.
Реализуйте класс UndergroundSystem:
- void checkIn(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, регистрируется на станции stationName в момент времени t.
Пассажир может быть зарегистрирован только в одном месте в одно и то же время.
- void checkOut(int id, string stationName, int t)
Пассажир с карточкой, идентификатор которой равен id, покидает станцию stationName в момент времени t.
- 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. Все события происходят в хронологическом порядке.
Пример:
Input
["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"]]
Output
[null,null,null,5.00000,null,null,5.50000,null,null,6.66667]
Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(10, "Leyton", 3);
undergroundSystem.checkOut(10, "Paradise", 8); // Customer 10 "Leyton" -> "Paradise" in 8-3 = 5
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.00000, (5) / 1 = 5
undergroundSystem.checkIn(5, "Leyton", 10);
undergroundSystem.checkOut(5, "Paradise", 16); // Customer 5 "Leyton" -> "Paradise" in 16-10 = 6
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 5.50000, (5 + 6) / 2 = 5.5
undergroundSystem.checkIn(2, "Leyton", 21);
undergroundSystem.checkOut(2, "Paradise", 30); // Customer 2 "Leyton" -> "Paradise" in 30-21 = 9
undergroundSystem.getAverageTime("Leyton", "Paradise"); // return 6.66667, (5 + 6 + 9) / 3 = 6.66667
👨💻 Алгоритм:
1⃣При регистрации на входе сохраняем информацию о начале пути (станция и время) в словаре checkInData.
2⃣При регистрации на выходе извлекаем информацию о начале пути из checkInData, вычисляем время поездки и обновляем статистику для маршрута в journeyData.
3⃣Для получения среднего времени поездки по заданному маршруту извлекаем статистику из journeyData и вычисляем среднее значение.
😎 Решение:
cclass UndergroundSystem {
private var journeyData = [String: (totalTime: Double, trips: Double)]()
private var checkInData = [Int: (stationName: String, time: Int)]()
func checkIn(_ id: Int, _ stationName: String, _ t: Int) {
checkInData[id] = (stationName, t)
}
func checkOut(_ id: Int, _ stationName: String, _ t: Int) {
let checkIn = checkInData.removeValue(forKey: id)!
let routeKey = "\(checkIn.stationName)->\(stationName)"
let tripTime = Double(t - checkIn.time)
let stats = journeyData[routeKey, default: (0, 0)]
journeyData[routeKey] = (stats.totalTime + tripTime, stats.trips + 1)
}
func getAverageTime(_ startStation: String, _ endStation: String) -> Double {
let stats = journeyData["\(startStation)->\(endStation)"]!
return stats.totalTime / stats.trips
}
}Ставь 👍 и забирай 📚 Базу знаний