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条回应

  1. Purdy说:

    Hey my name is Amy, I am from Leggings Hut.

    Thought I’d let you know that we ship our fitness apparel worldwide directly from New York City.

    Fitness leggings and athletic wear for women made with quality soft material.

    You will never overpay when shopping with us.

    Thanks and have a great day!

发表评论

电子邮件地址不会被公开。