LeetCode 1396. 设计地铁系统

Categories:

题目描述
思路分析
1. 解法一：哈希表记录行程（推荐）
相似题目

题目描述

✅ 1396. 设计地铁系统

思路分析

解法一：哈希表记录行程（推荐）

核心思路：

checkIn 记录乘客起点与时间。

checkOut 时计算本次行程时间，并累加到 (start, end) 的统计信息中。

getAverageTime 返回总时间 / 次数。

复杂度分析：

时间复杂度：O(1) 每次操作。

空间复杂度：O(n)。

import java.util.HashMap;
import java.util.Map;

class UndergroundSystem {
    private static class CheckInInfo {
        String station;
        int time;
        CheckInInfo(String station, int time) {
            this.station = station;
            this.time = time;
        }
    }

    private static class Stat {
        long total;
        int count;
    }

    private final Map<Integer, CheckInInfo> inMap = new HashMap<>();
    private final Map<String, Stat> stats = new HashMap<>();

    public void checkIn(int id, String stationName, int t) {
        inMap.put(id, new CheckInInfo(stationName, t));
    }

    public void checkOut(int id, String stationName, int t) {
        CheckInInfo info = inMap.remove(id);
        String key = info.station + "->" + stationName;
        Stat s = stats.computeIfAbsent(key, k -> new Stat());
        s.total += t - info.time;
        s.count += 1;
    }

    public double getAverageTime(String startStation, String endStation) {
        Stat s = stats.get(startStation + "->" + endStation);
        return (double) s.total / s.count;
    }
}

type checkInInfo struct {
    station string
    time    int
}

type stat struct {
    total int64
    count int64
}

type UndergroundSystem struct {
    inMap map[int]checkInInfo
    stats map[string]stat
}

func Constructor() UndergroundSystem {
    return UndergroundSystem{
        inMap: make(map[int]checkInInfo),
        stats: make(map[string]stat),
    }
}

func (u *UndergroundSystem) CheckIn(id int, stationName string, t int) {
    u.inMap[id] = checkInInfo{station: stationName, time: t}
}

func (u *UndergroundSystem) CheckOut(id int, stationName string, t int) {
    info := u.inMap[id]
    delete(u.inMap, id)
    key := info.station + "->" + stationName
    s := u.stats[key]
    s.total += int64(t - info.time)
    s.count += 1
    u.stats[key] = s
}

func (u *UndergroundSystem) GetAverageTime(startStation string, endStation string) float64 {
    s := u.stats[startStation+"->"+endStation]
    return float64(s.total) / float64(s.count)
}

相似题目

题目	难度	考察点
146. LRU 缓存	中等	设计
380. O(1) 时间插入、删除和获取随机元素	中等	设计
359. 日志速率限制器	简单	设计
355. 设计推特	中等	设计
432. 全 O(1) 的数据结构	困难	设计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/21055444