Leetcode 1396. Design Underground System (python)_综合

题目

在这里插入图片描述

错误解法

先分享一种错误解法。下面的这种错误解法错在很多个点上。首先，他每个操作不是O(1)的，时间复杂度就错了。第二，如果某个id先进出某两个站，然后再进了某个站，这个时候计算他的travel time是错的，因为按照下面这种解法会是出站时间小于进站时间，也就是这种解法不满足同一个id多次进出的情况。第三，如果某个idA进B出，然后C进D出，这个时候按下面的解法，在query(A,D)这个pair的时候就会被错误的包括进去，所以start和end必须是以pair的形式储存的

class UndergroundSystem:def __init__(self):self.checkin_dict = {
    }self.checkout_dict = {
    }def checkIn(self, id: int, stationName: str, t: int) -> None:if stationName in self.checkin_dict:self.checkin_dict[stationName][id] = telse:self.checkin_dict[stationName] = {
    }self.checkin_dict[stationName][id] = tdef checkOut(self, id: int, stationName: str, t: int) -> None:if stationName in self.checkout_dict:self.checkout_dict[stationName][id] = telse:self.checkout_dict[stationName] = {
    }self.checkout_dict[stationName][id] = tdef getAverageTime(self, startStation: str, endStation: str) -> float:#print(self.checkin_dict)total_time = 0cnt = 0if startStation in self.checkin_dict and endStation in self.checkout_dict:for id,t in self.checkin_dict[startStation].items():if id in self.checkout_dict[endStation]:cnt += 1total_time += self.checkout_dict[endStation][id] - self.checkin_dict[startStation][id]return total_time/cnt

正确解法

这道题正确解法远没有这么复杂。前面这么些是因为默认了checkin和checkout的情况需要被储存下来，其实只要储存checkin，checkout的时候就可以直接计算相应的时间了

class UndergroundSystem:def __init__(self):self.checkin_dict = {
    }self.travel_time = collections.defaultdict(int)self.travel_cnt = collections.defaultdict(int)def checkIn(self, id: int, stationName: str, t: int) -> None:self.checkin_dict[id] = (stationName,t)def checkOut(self, id: int, stationName: str, t: int) -> None:startStation,start_t = self.checkin_dict[id]self.travel_time[(startStation,stationName)] += t - start_tself.travel_cnt[(startStation,stationName)] += 1def getAverageTime(self, startStation: str, endStation: str) -> float:return self.travel_time[(startStation,endStation)]/self.travel_cnt[(startStation,endStation)]