车站之间的平均行程时间错误。 Leetcode #1396 测试用例失败

Question

地下铁路系统正在跟踪客户在不同车站之间的出行时间。他们正在使用这些数据来计算从一个车站到另一个车站所需的平均时间。

实现
UndergroundSystem
类：
void checkIn(int id, string stationName, int t)
卡ID等于
id
的顾客，在
stationName
时间
t
到车站办理报到。
一位顾客一次只能在一个地方办理登机手续。
void checkOut(int id, string stationName, int t)
卡ID等于
id
的顾客，在
stationName
时间
t
从车站结账。
double getAverageTime(string startStation, string endStation)
返回从
startStation
到
endStation
所需的平均时间。
平均时间是根据之前从
startStation
到
endStation
直接发生的所有旅行时间计算的，这意味着在
startStation
办理登机手续，然后从
endStation
办理退房。
从
startStation
到
endStation
所需的时间可能与从
endStation
到
startStation
所需的时间不同。
在
startStation
被呼叫之前，至少有一名顾客已从
endStation
前往
getAverageTime
。
您可以假设对
checkIn
和
checkOut
方法的所有调用都是一致的。如果客户在时间
t₁
入住，然后在
t₂
时间退房，然后
t₁
<
t₂
。所有事件均按时间顺序发生。

对于这个 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);
 */

编辑：

如果有人好奇我是如何修复它的，这就是我所做的，可能不是最好的方法，但仍然：

class UndergroundSystem {

    HashMap<Integer, LinkedList<String>> checkIns = new HashMap<>();
    HashMap<String, int[]> travelTimes = new HashMap<>();

    public UndergroundSystem() {}

    public void checkIn(int id, String stationName, int t) {
        checkIns.put(id, new LinkedList<>(List.of(stationName, Integer.toString(t))));
    }

    public void checkOut(int id, String stationName, int t) {
        if (checkIns.containsKey(id)) {
            LinkedList<String> checkInInfo = checkIns.remove(id);
            String key = checkInInfo.getFirst() + "," + stationName;
            int[] data = travelTimes.getOrDefault(key, new int[]{0, 0});
            data[0] += t - Integer.parseInt(checkInInfo.getLast()); // Calculate travel time correctly
            data[1]++;
            travelTimes.put(key, data);
        }
    }

    public double getAverageTime(String startStation, String endStation) {
        String key = startStation + "," + endStation;
        int[] data = travelTimes.get(key);
        return data != null && data[1] != 0 ? (double) data[0] / data[1] : 0; // Avoid division by zero
    }
}

Answer 1

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

```
checkIn
```
不会执行任何操作。
```
checkOut
```
获取
```
map.get(id).get(1)
```
，而不检查这是 current 行程的条目，这将是 map.get(id) 中的
```
last
```
条目。现在，同一个人的所有行程始终采用相同的登机时间。
```
checkIn
```
和
```
checkOut
```
都会在每次调用时创建一个新列表，将一个事件的信息放入其中，然后将该列表写入相关映射。这意味着地图条目将始终具有一个列表，其中仅包含一个事件的信息，而绝不会更多。没有代码可以扩展地图中已存在的列表。
```
getAverageTime
```
永远不会在链表中进一步查找，只希望第一个条目的电台能够匹配。这再次意味着，如果同一个人 (
```
id
```
) 进行多次旅行，您将无法报告所有这些。

测试用例

这是一个简单的测试用例，您的代码失败了：

LeetCode 格式：

["UndergroundSystem","checkIn","checkOut","checkIn","checkOut","getAverageTime"]
[[],[1,"A",1],[1,"B",2],[1,"B",3],[1,"C",4],["B","C"]]

或者输入代码：

UndergroundSystem subway = new UndergroundSystem();
subway.checkIn(1, "A", 1);
subway.checkOut(1, "A", 2);
subway.checkIn(1, "B", 3);
subway.checkOut(1, "B", 4);
System.out.println(subway.getAverageTime("B", "C"));

建议的方法

我不会继续使用这个数据结构；这不是最好的选择：必须查看链接列表才能找到正确的车站对来返回平均行程时间，效率不高。事实上，如果我们在退房时记录旅行信息，我们不需要某个

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();
    }
}

车站之间的平均行程时间错误。 Leetcode #1396 测试用例失败

问题描述投票：0回答：1

我的代码

1个回答

测试用例

建议的方法

最新问题

车站之间的平均行程时间错误。 Leetcode #1396 测试用例失败

问题描述 投票：0回答：1

我的代码

1个回答

测试用例

建议的方法

最新问题

问题描述投票：0回答：1