LEETCODE 1396. Design Underground System 解题思路分析

题目大意:

设计地铁系统

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

1. checkIn(int id, string stationName, int t)

  • 编号为 id 的乘客在 t 时刻进入地铁站 stationName 。
  • 一个乘客在同一时间只能在一个地铁站进入或者离开。

2. checkOut(int id, string stationName, int t)

  • 编号为 id 的乘客在 t 时刻离开地铁站 stationName 。

3. 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

提示:

  • 总共最多有 20000 次操作。
  • 1 <= id, t <= 10^6
  • 所有的字符串包含大写字母,小写字母和数字。
  • 1 <= stationName.length <= 10
  • 与标准答案误差在 10^-5 以内的结果都视为正确结果。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1396

解题思路分析:

这道题的关键在于如何存储数据。我们首先使用一个HashMap来存储所有checkin的数据。

Map<Integer, Data> map=new HashMap<>();

由于同一人的同一行程中checkin与checkout必定是成对出现的,因此我们可以在checkin函数中记录下该行程的起点信息,其中key为乘客id,value是该行程的起点站名以及进站时间。由于value中存在两个变量,因此我们可以将这两个信息包装成为一个类保存至map中。

在checkout函数中,我们从map中取出当前乘客的进站(checkin)信息,这时我们就可以知道一条完整的行程。进站站名,出站站名,以及行程时间(出站时刻减去进站时刻)。这时我们需要另外两个HashMap来存储每种相同行程的的总时间,以及每种行程的数量。其中使用进站名称与出站名称的组合作为key,value是该行程的总时间或者该行程数量。

Map<String, Integer> time=new HashMap<>();
Map<String, Integer> count=new HashMap<>();

有了以上的铺垫,getAverageTime函数就变得非常简单。我们使用参数中的进站名与出站名组成一个key,分别从time和count这两个HashMap中找到该行程的总时间以及行程数量,两者相除即是该行程的平均花费时间。

实现代码:

Map<String, Integer> time=new HashMap<>();
Map<String, Integer> count=new HashMap<>();
Map<Integer, Data> map=new HashMap<>();
public UndergroundSystem() {

}

public void checkIn(int id, String stationName, int t) {
    Data data=new Data(stationName,t);
    map.put(id,data);
}

public void checkOut(int id, String stationName, int t) {
    Data data=map.get(id);
    String key=data.stationName+"_"+stationName;
    int allTime = time.getOrDefault(key,0);
    time.put(key, allTime+t-data.time);
    int allCount = count.getOrDefault(key,0);
    count.put(key, allCount+1);
}

public double getAverageTime(String startStation, String endStation) {
    String key=startStation+"_"+endStation;
    int allTime = time.get(key);
    int allCount = count.get(key);
    return (double)allTime/allCount;
}

class Data{
    Data(String s, int t){
        stationName=s;
        time=t;
    }
    String stationName;
    int time;
}

本题解法执行时间为73ms。

Runtime: 73 ms, faster than 87.06% of Java online submissions for Design Underground System.

Memory Usage: 54.1 MB, less than 100.00% of Java online submissions for Design Underground System.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1396-design-underground-system-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

LEETCODE 1396. Design Underground System 解题思路分析》有1条回应

    发表评论

    您的电子邮箱地址不会被公开。