LeetCode: 1396.设计地铁系统 Python实现（仅利用嵌套的数据结构）

74 阅读 0 评论 49 点赞

我是靠谱客的博主深情书包，这篇文章主要介绍LeetCode: 1396.设计地铁系统 Python实现（仅利用嵌套的数据结构），现在分享给大家，希望可以做个参考。

解题思路

本方法主要使用了字典嵌套列表以及元组的数据结构
注意：字典的key值不能为list类型，原因为 TypeError: unhashable type: ‘list’

StoE字典结构如下：
{(startStation,endStation):[time_total, times]}
time_total: 所有人从相同的始发站到终点站花费的时间总和
times: 从相同的始发站到终点站出行的人数总和

start字典结构如下：
{id:[stationName, t]}

额外操作：一个人可以多次乘坐地铁，所以为了避免出现数据混淆的情况，在checkOut之后要删除相应的乘车记录以进行下一次记录。ps：此操作也可以节约内存空间

代码

复制代码

class UndergroundSystem:

def __init__(self):
        self.start = {}
        self.StoE = {}

def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.start[id] = [stationName,t]

def checkOut(self, id: int, stationName: str, t: int) -> None:
        time_elapsed = t - self.start[id][1]
        if (self.start[id][0],stationName) not in self.StoE.keys():
            self.StoE[(self.start[id][0],stationName)] = [time_elapsed, 1]
            
        else:
            self.StoE[(self.start[id][0],stationName)][0] += time_elapsed
            self.StoE[(self.start[id][0],stationName)][1] += 1
        self.start.pop(id)

def getAverageTime(self, startStation: str, endStation: str) -> float:
        return self.StoE[(startStation,endStation)][0]/self.StoE[(startStation,endStation)][1]

# Your UndergroundSystem object will be instantiated and called as such:
# obj = UndergroundSystem()
# obj.checkIn(id,stationName,t)
# obj.checkOut(id,stationName,t)
# param_3 = obj.getAverageTime(startStation,endStation)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class UndergroundSystem:

    def __init__(self):
        self.start = {}
        self.StoE = {}

    def checkIn(self, id: int, stationName: str, t: int) -> None:
        self.start[id] = [stationName,t]
        

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        time_elapsed = t - self.start[id][1]
        if (self.start[id][0],stationName) not in self.StoE.keys():
            self.StoE[(self.start[id][0],stationName)] = [time_elapsed, 1]
            
        else:
            self.StoE[(self.start[id][0],stationName)][0] += time_elapsed
            self.StoE[(self.start[id][0],stationName)][1] += 1
        self.start.pop(id)
            
        

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        return self.StoE[(startStation,endStation)][0]/self.StoE[(startStation,endStation)][1]
        


# Your UndergroundSystem object will be instantiated and called as such:
# obj = UndergroundSystem()
# obj.checkIn(id,stationName,t)
# obj.checkOut(id,stationName,t)
# param_3 = obj.getAverageTime(startStation,endStation)