请你实现一个类 UndergroundSystem ,它支持以下 3 种方法:

  1. checkIn(int id, string stationName, int t)
  • 编号为 id 的乘客在 t 时刻进入地铁站 stationName 。
  • 一个乘客在同一时间只能在一个地铁站进入或者离开。
  1. checkOut(int id, string stationName, int t)
  • 编号为 id 的乘客在 t 时刻离开地铁站 stationName 。
  1. getAverageTime(string startStation, string endStation)
  • 返回从地铁站 startStation 到地铁站 endStation 的平均花费时间。

  • 平均时间计算的行程包括当前为止所有从 startStation 直接到达 endStation 的行程。

  • 调用 getAverageTime 时,询问的路线至少包含一趟行程。

    你可以假设所有对 checkIn 和 checkOut 的调用都是符合逻辑的。也就是说,如果一个顾客在 t1 时刻到某个地铁站,那么他离开的时间 t2 一定满足 t2 > t1 。所有的事件都按时间顺序给出。

示例:

输入:

["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.0,11.0,null,11.0,null,12.0]

解释:

UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);
undergroundSystem.checkOut(27, "Waterloo", 20);
undergroundSystem.checkOut(32, "Cambridge", 22);
undergroundSystem.getAverageTime("Paradise", "Cambridge"); // 返回 14.0。从 "Paradise"(时刻 8)到 "Cambridge"(时刻 22)的行程只有一趟
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // 返回 11.0。总共有 2 躺从 "Leyton" 到 "Waterloo" 的行程,编号为 id=45 的乘客出发于 time=3 到达于 time=15,编号为 id=27 的乘客于 time=10 出发于 time=20 到达。所以平均时间为 ( (15-3) + (20-10) ) / 2 = 11.0
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // 返回 11.0
undergroundSystem.checkOut(10, "Waterloo", 38);
undergroundSystem.getAverageTime("Leyton", "Waterloo"); // 返回 12.0

提示:

解法

通过维护两个unorder_map(对map优化时间)进行操作

class UndergroundSystem {
private:
unordered_map<int, pair<string, int>> passenger;//<乘客id, <上车站, 上车时间>>
unordered_map<string, pair<int, int>> time;//<"上车站,下车站", <总用时, 总人次>>
public:
UndergroundSystem() {
} void checkIn(int id, string stationName, int t) {
passenger[id] = make_pair(stationName, t);
} void checkOut(int id, string stationName, int t) {
string s = passenger[id].first + ',' + stationName;//连接起始站和终点站
int pass_time = t - passenger[id].second;//存储经过时间
if(time.find(s) == time.end()){//查询是否计数过,计数过就加起来,不然就make_pair
time[s] = make_pair( pass_time , 1 );
}else{
time[s].first += pass_time;
time[s].second += 1;
}
} double getAverageTime(string startStation, string endStation) {
string s = startStation + ',' + endStation;
return (double)time[s].first/time[s].second;
}
}; /**
* Your UndergroundSystem object will be instantiated and called as such:
* UndergroundSystem* obj = new UndergroundSystem();
* obj->checkIn(id,stationName,t);
* obj->checkOut(id,stationName,t);
* double param_3 = obj->getAverageTime(startStation,endStation);
*/

Ps:

LeetCode | 力扣周赛C题 5370. 设计地铁系统-LMLPHP

比赛的时候被降智了

05-13 07:23