为什么我的 Leetcode #1396 测试用例失败了

Question

对于这个 leetcode 问题，我通过了 52/59 个测试用例，但我无法弄清楚为什么我没有通过其余的测试用例。我无法比较预期的输出和我得到的输出，因为 Leetcode 截断了大的输出。谁能告诉我这里的问题可能是什么？

谢谢！

class UndergroundSystem {

    HashMap<Integer, LinkedList<String>> map = new HashMap<>(); //holds player id and station names with t time start
    HashMap<Integer, LinkedList<String>> cMap = new HashMap<>(); //holds player id and exit station name with t time diff
    public UndergroundSystem() {
        map = new HashMap<>(); 
        cMap = new HashMap<>();
    }
    
    public void checkIn(int id, String stationName, int t) {
        if(!map.containsKey(id)) {
        LinkedList<String> list = new LinkedList<>();
        list.add(stationName);
        list.add(Double.toString(t));
        map.put(id, list);
        }
    }
    
    public void checkOut(int id, String stationName, int t) {
        //same id then subtract the times
        if(map.containsKey(id)) {
            LinkedList<String> subList = new LinkedList<>();
            subList.add(stationName);
            subList.add(Double.toString(Math.abs(Double.parseDouble(map.get(id).get(1)) - t)));
            cMap.put(id, subList);
        }
    }
    
    public double getAverageTime(String startStation, String endStation) {
        //first map is going to give us the start station
        //second map is going to give us the end station and the time

        // LinkedList<String> l1 = new LinkedList<>(map.values());
        // LinkedList<String> l2 = new LinkedList<>(cMap.values());
        
        double count = 0;
        double sum = 0;

        // HashMap<Integer, LinkedList<String>> map1 = map;
        // HashMap<Integer, LinkedList<String>> cMap1 = cMap;

        for(Integer i: map.keySet()) {
            if(map.containsKey(i) && cMap.containsKey(i) && map.get(i).get(0).equals(startStation) && cMap.get(i).get(0).equals(endStation)) {
                sum += Double.parseDouble(cMap.get(i).get(1));
                count++;
           }
        }
        return  count == 0 ? 0 : sum / count;
    }
}

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

Answer 1

您的尝试中存在几个问题：

如果相同的 ID 已用于之前的行程（入住 + 退房），

• checkIn

  不会执行任何操作。

• checkOut

  获取

  map.get(id).get(1)

  ，而不检查这是 current 行程的条目，这将是 map.get(id) 中的

  last

  条目。现在，同一个人的所有行程始终采用相同的登机时间。

• checkIn

  和

  checkOut

  都会在每次调用时创建一个新列表，将一个事件的信息放入其中，然后将该列表写入相关映射。这意味着地图条目将始终具有一个列表，其中仅包含一个事件的信息，而绝不会更多。没有代码可以扩展地图中已存在的列表。

• getAverageTime

  从不进一步查看链表，只希望第一个条目的电台能够匹配。这再次意味着，如果同一个人 (

  id

  ) 进行多次旅行，您将无法报告所有这些。

但我不会尝试解决这些问题，因为数据结构的选择不好：必须查看链表才能找到正确的车站对来返回平均旅行时间，效率不高。事实上，如果我们在退房时记录旅行信息，我们不需要某个

id

进行的所有登记的列表：一旦旅行完成并且我们处理了旅行时间，它们就变得无关紧要。

您需要以不同的方式构建信息：

• 对于给定的

  id

  ，您只需要存储该卡ID最近一次签到的签到信息。不需要链表。而是使用一对电台和时间。

• 对于对车站名称，您需要跟踪行程次数以及在这些行程上花费的总累计时间。这可能是一个嵌套地图，但由于已知车站名称仅包含字母数字字符，因此我们可以使用两个车站名称（从-到）的逗号分隔串联作为一维地图的键。

这是一个可能的实现：

class UndergroundSystem {
    private class CheckIn {
        String startStation;
        int startTime;

        CheckIn(String stationName, int time) {
            startStation = stationName;
            startTime = time;
        }
    }

    private class Statistic {
        int tripCount = 0;
        int totalTravelTime = 0;

        void logTrip(int travelTime) {
            tripCount++;
            totalTravelTime += travelTime;
        }

        double getAverage() {
            return (double) totalTravelTime / tripCount;
        }
    }

    // Per card id: the most recent check-in information
    HashMap<Integer, CheckIn> checkIns = new HashMap<>();
    // Per pair of stations (concatenated): the overall trip statistics
    HashMap<String, Statistic> trips = new HashMap<>();
    
    public void checkIn(int id, String stationName, int time) {
        checkIns.put(id, new CheckIn(stationName, time));
    }
    
    public void checkOut(int id, String stationName, int time) {
        CheckIn checkIn = checkIns.get(id); // There must be a check-in.
        String tripName = checkIn.startStation + "," + stationName;
        if (!trips.containsKey(tripName)) { // First time someone makes this trip
            trips.put(tripName, new Statistic());
        }
        trips.get(tripName).logTrip(time - checkIn.startTime);
    }
    
    public double getAverageTime(String startStation, String endStation) {
        String tripName = startStation + "," + endStation;
        if (!trips.containsKey(tripName)) return -1; // No such trips
        return trips.get(tripName).getAverage();
    }
}