🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 1396. Design Underground System
Сложность: 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 последовательны и происходят в хронологическом порядке.
Пример:
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]
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
👨💻 Алгоритм:
1⃣При регистрации на входе сохраняем информацию о начале пути (станция и время) в словаре checkInData.
2⃣При регистрации на выходе извлекаем информацию о начале пути из checkInData, вычисляем время поездки и обновляем статистику для маршрута в journeyData.
3⃣Для получения среднего времени поездки по заданному маршруту извлекаем статистику из journeyData и вычисляем среднее значение.
😎 Решение:
type UndergroundSystem struct {
journeyData map[string][2]float64
checkInData map[int][2]interface{}
}
func Constructor() UndergroundSystem {
return UndergroundSystem{
journeyData: make(map[string][2]float64),
checkInData: make(map[int][2]interface{}),
}
}
func (this *UndergroundSystem) CheckIn(id int, stationName string, t int) {
this.checkInData[id] = [2]interface{}{stationName, t}
}
func (this *UndergroundSystem) CheckOut(id int, stationName string, t int) {
checkIn := this.checkInData[id]
startStation := checkIn[0].(string)
startTime := checkIn[1].(int)
delete(this.checkInData, id)
routeKey := startStation + "->" + stationName
tripTime := float64(t - startTime)
if _, exists := this.journeyData[routeKey]; !exists {
this.journeyData[routeKey] = [2]float64{0, 0}
}
this.journeyData[routeKey][0] += tripTime
this.journeyData[routeKey][1] += 1
}
func (this *UndergroundSystem) GetAverageTime(startStation string, endStation string) float64 {
stats := this.journeyData[startStation+"->"+endStation]
return stats[0] / stats[1]
}
Ставь 👍 и забирай 📚 Базу знаний
