织梦网站,搜索引擎优化方案,江津网站建设效果好不好,个人个案网站 类型1. 题目
请你实现一个类 UndergroundSystem #xff0c;它支持以下 3 种方法#xff1a; checkIn(int id, string stationName, int t) 编号为 id 的乘客在 t 时刻进入地铁站 stationName 。 一个乘客在同一时间只能在一个地铁站进入或者离开。 checkOut(int id, string st…1. 题目
请你实现一个类 UndergroundSystem 它支持以下 3 种方法 checkIn(int id, string stationName, int t) 编号为 id 的乘客在 t 时刻进入地铁站 stationName 。 一个乘客在同一时间只能在一个地铁站进入或者离开。 checkOut(int id, string stationName, int t) 编号为 id 的乘客在 t 时刻离开地铁站 stationName 。 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 的行程编号为 id45 的乘客出发于 time3 到达于 time15
// 编号为 id27 的乘客于 time10 出发于 time20 到达。所以平均时间为 ( (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提示
总共最多有 20000 次操作。
1 id, t 10^6
所有的字符串包含大写字母小写字母和数字。
1 stationName.length 10
与标准答案误差在 10^-5 以内的结果都视为正确结果。来源力扣LeetCode 链接https://leetcode-cn.com/problems/design-underground-system 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
map1 记录起点到终点后更新另一个map2的信息map1删除该条信息
class UndergroundSystem {mapvectorstring,vectorint station_time_n;//2个string起点终点2个int总时间人数mapint, pairstring,int id_startStation;// 乘客id起点出发时刻vectorstring s;
public:UndergroundSystem() { }void checkIn(int id, string stationName, int t) {id_startStation.insert({id,make_pair(stationName,t)});// 乘客id起点出发时刻}void checkOut(int id, string stationName, int t) {s {id_startStation[id].first, stationName};//起点终点if(!station_time_n.count(s))station_time_n.insert({s,{t-id_startStation[id].second,1}});else{station_time_n[s][0] t-id_startStation[id].second;station_time_n[s][1] 1;}id_startStation.erase(id);}double getAverageTime(string startStation, string endStation) {s {startStation, endStation};return station_time_n[s][0]/double(station_time_n[s][1]);}
};unordered_map key 为基本类型C内置的hash函数够用不能为vector需要自己写hash函数下面 pairint,int 不可以换成vectorint用[0],[1]去访问, 下面写法会报错vector 还不知道有几个元素
class UndergroundSystem {unordered_mapstring, unordered_mapstring,pairint,int Station_time_n;// 起点终点2个int总时间人数unordered_mapint, pairstring,int id_startStation_t;// 乘客id起点出发时刻string startStation;int time;
public:UndergroundSystem() { }void checkIn(int id, string stationName, int t) {id_startStation_t[id].first stationName;// 乘客id起点出发时刻id_startStation_t[id].second t;}void checkOut(int id, string stationName, int t) {startStation id_startStation_t[id].first;time t-id_startStation_t[id].second;Station_time_n[startStation][stationName].first time;Station_time_n[startStation][stationName].second 1;id_startStation_t.erase(id);}double getAverageTime(string startStation, string endStation) {return Station_time_n[startStation][endStation].first/double(Station_time_n[startStation][endStation].second);}
};需要先判断是否存在初始化vector为 {time, 1}
class UndergroundSystem {unordered_mapstring, unordered_mapstring,vectorint Station_time_n;// 起点终点2个int总时间人数unordered_mapint, pairstring,int id_startStation_t;// 乘客id起点出发时刻string startStation;int time;
public:UndergroundSystem() { }void checkIn(int id, string stationName, int t) {id_startStation_t[id].first stationName;// 乘客id起点出发时刻id_startStation_t[id].second t;}void checkOut(int id, string stationName, int t) {startStation id_startStation_t[id].first;time t-id_startStation_t[id].second;//--------------pairint,int 换成 vectorint----,区别是要先判断是否存在----------if(!Station_time_n[startStation].count(stationName))Station_time_n[startStation][stationName] {time,1};else{Station_time_n[startStation][stationName][0] time;Station_time_n[startStation][stationName][1] 1;}id_startStation_t.erase(id);}double getAverageTime(string startStation, string endStation) {return Station_time_n[startStation][endStation][0]/double(Station_time_n[startStation][endStation][1]);}
};
