设计地铁系统--合适容器选择的重要性

最新推荐文章于 2022-08-15 22:57:40 发布

ATFWUS

最新推荐文章于 2022-08-15 22:57:40 发布

阅读量718

点赞数 23

分类专栏：算法

本文为ATFWUS原创，允许转载，但请附上作者署名和本文链接

本文链接：https://blog.csdn.net/ATFWUS/article/details/105177723

版权

算法专栏收录该内容

110 篇文章 97 订阅

订阅专栏

0x01.问题

请你实现一个类 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 时，询问的路线至少包含一趟行程。

调用 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

C++类形式：
class UndergroundSystem {
public:
    UndergroundSystem() {
        
    }
    
    void checkIn(int id, string stationName, int t) {
        
    }
    
    void checkOut(int id, string stationName, int t) {
        
    }
    
    double getAverageTime(string startStation, string endStation) {
        
    }
};
调用说明:

 * 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);

注：此题来源于Leetcode 第182场周赛第三题

0x02.简要分析

仔细读题，发现问题其实不是很难，不过需要注意以下几个地方：

两个站的平均用时需要考虑到所有这两个站的线路。
可能有多个相同名字的站并排，但确定线路的标准是乘车人的id。
有了基本的思路后，这个题可以有多种做法，下面提供两种思路：

思路一为比赛中AC的代码，效果比较差
思路二为赛后想的代码，效果很好

0x03.暴力的思路–乱用容器

比赛过程中，一时想不了那么多，就感觉问题很简单的，于是就想了一条简单的思路：

在每个站把站名，id，时间全部存入容器。
这里的容器指的是我用C思路的结构体嵌套得来的容器。
最后计算平均时间的时候，双层循环，先找到一个起点，然后再去找终点，然后看里面是不是有id相同的信息，如果有，就计算出来，并且重新开始找下一个起点，这样遍历所有存储的信息。

这个方法其实很粗暴，可以说很差，但是比赛的时候竟然过了，用了2s。

这种方法错误的地方首先在于容器选择的错误，造成了很多不必要的空间浪费，比如相同站名在这里面其实也存储在不同的地方了。
其次，前面两个函数只是无脑的存数据，并没有去处理数据，导致最后一个函数需要大量的去遍历这些数据，很耗时间。

下面是比赛时AC的代码：

class UndergroundSystem {
public:
    struct StationInformation {
        int id;
        int time;
    };
    struct station {
        string name;
        vector<struct StationInformation> p;
    };
    vector<struct station> All;
    UndergroundSystem() {

    }

    void checkIn(int id, string stationName, int t) {
        struct StationInformation informations;
        informations.id = id;
        informations.time = t;
        struct station c;
        c.name = stationName;
        c.p.push_back(informations);
        All.push_back(c);
    }

    void checkOut(int id, string stationName, int t) {
        struct StationInformation informations;
        informations.id = id;
        informations.time = t;
        struct station c;
        c.name = stationName;
        c.p.push_back(informations);
        All.push_back(c);
    }

    double getAverageTime(string startStation, string endStation) {
        vector<struct StationInformation> startSationInformation;
        vector<struct StationInformation> endStationInformation;
        double count = 0;
        double time = 0;
        for (int i = 0; i < All.size() - 1; i++) {
        ss:     if (All[i].name == startStation) {
                    startSationInformation = All[i].p;
                    for (int j = i + 1; j < All.size(); j++) {
                        if (All[j].name == endStation) {
                            endStationInformation = All[j].p;
                            for (int k = 0; k < startSationInformation.size(); k++) {
                                for (int h = 0; h < endStationInformation.size(); h++) {
                                    if (startSationInformation[k].id == endStationInformation[h].id) {
                                        time += endStationInformation[h].time - startSationInformation[k].time;
                                        count++;
                                        i++;
                                        goto ss;
                                    }
                                }
                            }
                        }
                    }
                }
        }
        return time / count;
    }
};

0x04.较优思路–map和pair搭配使用

赛后仔细一想，发现，用map和pair一起使用，完全可以。思路如下：

用一个maptableid，用于记录某一个id上车的车站和时间。
上车的时候只要记录下来就好了。
下车的时候，我们使用一个mapresult，记录起始点和终点合并的字符串，还有所用时间，线路次数。
因为题目保证了数据的合法性，说明下车的那个乘客一定之前上了车，所有只要操控对应得id就行了。
tableid的形式为：unordered_map<int, pair<string, int>> tableid;
result的形式为：unordered_map<string, pair<double, int>> result;

下面是代码：

class UndergroundSystem {
private:
    unordered_map<int, pair<string, int>> tableid;
    unordered_map<string, pair<double, int>> result;
public:
    UndergroundSystem() {

    }

    void checkIn(int id, string stationName, int t) {
        tableid[id] = { stationName ,t };
    }

    void checkOut(int id, string stationName, int t) {
        string name = tableid[id].first + stationName;
        t -= tableid[id].second;
        result[name].first += (double)t;
        result[name].second++;
    }

    double getAverageTime(string startStation, string endStation) {
        string name = startStation + endStation;
        return result[name].first / result[name].second;
    }
};

两者的空间消耗差不多，但时间的差距是数十倍。
所以选择合适的容器来存储数据真的很重要。

ATFWUS --Writing By 2020–03–29

ATFWUS

关注

23
点赞
踩
6

收藏

觉得还不错? 一键收藏
打赏
0
评论
设计地铁系统--合适容器选择的重要性

0x01.问题请你实现一个类 UndergroundSystem ，它支持以下 3 种方法：checkIn(int id, string stationName, int t)：编号为 id 的乘客在 t 时刻进入地铁站 stationName 。一个乘客在同一时间只能在一个地铁站进入或者离开。checkOut(int id, string stationName, int t)：编...
复制链接

扫一扫