LeetCode 1396. 设计地铁系统 JAVA 回看

怼烎@ 2022-12-18 05:54 243阅读 0赞

请你实现一个类 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 以内的结果都视为正确结果。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/design-underground-system
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：以下是错误的第一版，一开始的思路  
1、保存进站和出站站名与record的类进行映射，得到哪些人在哪些时间进站和出站  
2、计算平均时间时，对进入指定站人的id与出去指定站的人的id进行比较，若相同，则总时间增加，人数增加， 最后用总时间除以人数即可  
而问题就在这里，某一个人可能在同一个站点多次进站，在同一个或不同站点出站，这样代码便出现了问题。  
例如：  
某个人第一次在1号站进入，2站出去，第二次在1站进入，3站出去，而平均时间指定进站和出站是1,3，则会出现错误，代码上就会将其第一次在一号站进站后的时间与3站出去的时间比较，然后算作一次正确的进出站，还会将其第二次进站时间和3站比较，再做出一次正确进出站，从而导致了整个问题的错误，这也在52个中跑了48正确后，在第49个出现错误后，想了很久才发现的一个问题

class UndergroundSystem {
        
        Map<String,List<record>> Inmap;
        Map<String,List<record>> outmap;
        public UndergroundSystem() {
        
            outmap=new HashMap<>();
            Inmap=new HashMap<>();
        }
        
        public void checkIn(int id, String stationName, int t) {
        
            record tmp=new record(id,stationName,t);
            List<record> list=Inmap.getOrDefault(stationName,new ArrayList<>());
            list.add(tmp);
            Inmap.put(stationName,list);
        }
        
        public void checkOut(int id, String stationName, int t) {
        
            record tmp=new record(id,stationName,t);
            List<record> list=outmap.getOrDefault(stationName,new ArrayList<>());
            list.add(tmp);
            outmap.put(stationName,list);
        }
        
        public double getAverageTime(String startStation, String endStation) {
        
            List<record> inlist=Inmap.getOrDefault(startStation,new ArrayList<>());
            List<record> outlist=outmap.getOrDefault(endStation,new ArrayList<>());
            Map<Integer,Integer> map=new HashMap<>();
            double sum=0;
            double cnt=0;
            for(record rec:outlist) map.put(rec.id,rec.t);
            for(record in:inlist){
        
                int id=in.id;
                if(map.containsKey(id)){
        
                    sum+=(double)map.get(id)-(double)in.t;
                    cnt++;
                }
            }
            return sum/cnt;
        }
    }
    class record{
        
        int id;
        String startStation;
        int t;
        record(int id,String startStation,int t){
        
            this.id=id;
            this.startStation=startStation;
            this.t=t;
        }
    }

这一版是从题解拿过来，思路很清晰  
与上面的改变，是每一次更新id的进站时间和站点，并在每一次出站后，直接更新响应两个站点的平均时间，无论题目是否要求到该进出站点时间，都进行了计算，从而避免了错误

class UndergroundSystem {
        
        private Map<Integer,String> id_in_s;//保存进站人 Id 站名
        private Map<Integer,Integer> id_in_t;//保存进站时间
        private Map<String,Double> s_avrage_time;//保存站点间平均时间
        private Map<String,Integer> s_avrage_count;//保存站点间已计算平均时间的次数 
        public UndergroundSystem() {
        
            this.id_in_s=new HashMap<>();
            this.id_in_t=new HashMap<>();
            this.s_avrage_time=new HashMap<>();
            this.s_avrage_count=new HashMap<>();
        }
        
        public void checkIn(int id, String stationName, int t) {
        
            id_in_s.put(id,stationName);
            id_in_t.put(id,t);
        }
        
        public void checkOut(int id, String stationName, int t) {
        
            int in_t=id_in_t.get(id);
            String s_in=id_in_s.get(id);
            
            String start2endName=s_in+"#"+stationName;
            
            if(s_avrage_time.containsKey(start2endName)){
        
                double preavrage=s_avrage_time.get(start2endName);
                int count=s_avrage_count.get(start2endName);
                s_avrage_time.put(start2endName,(preavrage*count+t-in_t)/(count+1));
                s_avrage_count.put(start2endName,count+1);
            }else{
        
                s_avrage_time.put(start2endName,Double.valueOf(t-in_t));
                s_avrage_count.put(start2endName,1);
            }
            
        }
        
        public double getAverageTime(String startStation, String endStation) {
        
                return this.s_avrage_time.get(startStation+"#"+endStation);
        }
    }