首页 > 其他分享 >Leetcode 1396. 设计地铁系统

Leetcode 1396. 设计地铁系统

时间:2024-09-25 10:34:13浏览次数:11  
标签:self endStation id 进站 地铁 stationName 1396 startStation Leetcode

1.题目基本信息

1.1.题目描述

地铁系统跟踪不同车站之间的乘客出行时间,并使用这一数据来计算从一站到另一站的平均时间。

实现 UndergroundSystem 类:

  • void checkIn(int id, string stationName, int t)
    • 通行卡 ID 等于 id 的乘客,在时间 t ,从 stationName 站进入
    • 乘客一次只能从一个站进入
  • void checkOut(int id, string stationName, int t)
    • 通行卡 ID 等于 id 的乘客,在时间 t ,从 stationName 站离开
  • double getAverageTime(string startStation, string endStation)
    • 返回从 startStation 站到 endStation 站的平均时间
    • 平均时间会根据截至目前所有从 startStation 站 直接 到达 endStation 站的行程进行计算,也就是从 startStation 站进入并从 endStation 离开的行程
    • 从 startStation 到 endStation 的行程时间与从 endStation 到 startStation 的行程时间可能不同
    • 在调用 getAverageTime 之前,至少有一名乘客从 startStation 站到达 endStation 站

你可以假设对 checkIn 和 checkOut 方法的所有调用都是符合逻辑的。如果一名乘客在时间 t1 进站、时间 t2 出站,那么 t1 < t2 。所有时间都按时间顺序发生。

1.2.题目地址

https://leetcode.cn/problems/design-underground-system/description

2.解题方法

2.1.解题思路

设计俩哈希表进行存储: 第一张哈希表(临时记录进站信息用): 用户ID->(最近的进站站点,最近的进站时间); 第二张哈希表(直接对应getAverageTime函数,快速计算平均时间用): (进站ID,出站ID)->(总时间,总人数)。

2.2.解题步骤

第一步,设计存储的数据结构。

第二步,当用户id进入stationName站时,将该用户的进站站点和进入时间信息记录到map1。

第三步,当用户出站时,将map2中(出站,进站)路线的总时间和总人数更新一下。

第四步,直接根据出站和进站信息获取该路线的总时间和总人数,相除即可获取平均时间。

3.解题代码

Python代码

class UndergroundSystem:
    # 关键: 设计俩哈希表进行存储: 第一张哈希表(临时记录进站信息用): 用户ID->(最近的进站站点,最近的进站时间); 第二张哈希表(直接对应getAverageTime函数,快速计算平均时间用): (进站ID,出站ID)->(总时间,总人数)。
    # 第一步,设计存储的数据结构。第二步,当用户id进入stationName站时,将该用户的进站站点和进入时间信息记录到map1。第三步,当用户出站时,将map2中(出站,进站)路线的总时间和总人数更新一下。第四步,直接根据出站和进站信息获取该路线的总时间和总人数,相除即可获取平均时间。
    def __init__(self):
        self.map1={}
        self.map2={}

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

    def checkOut(self, id: int, stationName: str, t: int) -> None:
        inStationName,inTime=self.map1[id]
        key=(inStationName,stationName)
        if key in self.map2:
            self.map2[key]=[self.map2[key][0]+t-inTime,self.map2[key][1]+1]
        else:
            self.map2[key]=[t-inTime,1]

    def getAverageTime(self, startStation: str, endStation: str) -> float:
        timeSum,personsCnt=self.map2[(startStation,endStation)]
        return timeSum/personsCnt

4.执行结果

在这里插入图片描述

标签:self,endStation,id,进站,地铁,stationName,1396,startStation,Leetcode
From: https://www.cnblogs.com/geek0070/p/18430837

相关文章

  • 计算机低能儿从0刷leetcode | 17.电话号码的数字组合 | 回溯思想
    题目:17.电话号码的字母组合解答:看题解学习到这种思想叫做回溯法,学习了一下,这是建立在DFS的基础上搜索思路,还分为递归式回溯以及非递归式回溯,这道题使用的是递归回溯。递归回溯的大致框架如下:voidDFS(inti){//搜索第i层   if(i>n){//搜索结束       ......
  • leetcode 2207. 字符串中最多数目的子序列
    3/100天刷题记录字符串中最多数目的子序列](https://leetcode.cn/problems/maximize-number-of-subsequences-in-a-string/)给你一个下标从0开始的字符串text和另一个下标从0开始且长度为2的字符串pattern,两者都只包含小写英文字母。你可以在text中任意位置......
  • 【算法题】20. 有效的括号-力扣(LeetCode)
    【算法题】20.有效的括号-力扣(LeetCode)1.题目下方是力扣官方题目的地址20.有效的括号给定一个只包括'(',')','{','}','[',']'的字符串s,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对......
  • 【算法题】11. 盛最多水的容器-力扣(LeetCode)
    【算法题】11.盛最多水的容器-力扣(LeetCode)1.题目下方是力扣官方题目的地址11.盛最多水的容器给定一个长度为n的整数数组height。有n条垂线,第i条线的两个端点是(i,0)和(i,height[i])。找出其中的两条线,使得它们与x轴共同构成的容器可以容纳最多的......
  • 【算法题】53. 最大子数组和-力扣(LeetCode)
    【算法题】53.最大子数组和-力扣(LeetCode)1.题目下方是力扣官方题目的地址53.最大子数组和给你一个整数数组nums,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。子数组是数组中的一个连续部分。示例1:输入:nums=[-2,1,-3,4,-1,2,1,-......
  • 【LeetCode Hot 100】17. 电话号码的字母组合
    题目描述本题需要用回溯算法遍历穷举所有可能的解。回溯算法维护一个字符串序列,记录已经有的字母排列,用一个索引值记录该字符串序列下一个将要处理的位置。每次递归将索引值加一,回溯之后将字符串序列中上次加入的字符退出序列中,枚举下一个可能的值。总的来说是一个较为基础的回溯......
  • Leetcode 43. 字符串相乘
    1.题目基本信息1.1.题目描述给定两个以字符串形式表示的非负整数num1和num2,返回num1和num2的乘积,它们的乘积也表示为字符串形式。注意:不能使用任何内置的BigInteger库或直接将输入转换为整数。1.2.题目地址https://leetcode.cn/problems/multiply-strings/descripti......
  • LeetCode 1014. 最佳观光组合
    题目简介:给你一个正整数数组 values,其中 values[i] 表示第 i 个观光景点的评分,并且两个景点 i 和 j 之间的 距离 为 j-i。一对景点(i<j)组成的观光组合的得分为 values[i]+values[j]+i-j ,也就是景点的评分之和 减去 它们两者之间的距离。返回一对观......
  • Day 23 贪心算法part01| LeetCode 455.分发饼干,376.摆动序列,53.最大子序和
    455.分发饼干455.分发饼干classSolution{publicintfindContentChildren(int[]g,int[]s){Arrays.sort(g);Arrays.sort(s);intindex=s.length-1;intcount=0;for(inti=g.le......
  • 387. 字符串中的第一个唯一字符-LeetCode(C++)
    387.字符串中的第一个唯一字符题目给定一个字符串s,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回-1。提示:1<=s.length<=105s只包含小写字母示例示例1:输入:s="leetcode"输出:0示例2:输入:s="loveleetcode"输出:2示例3:......