企业官网建设流程全解析

LeetCode 635 设计日志存储系统（Design Log Storage System）

难度：Medium
标签：设计、字符串、有序存储、日志检索

题目原文

题目

你需要设计一个日志存储系统，可以存放日志，并且根据时间范围、指定时间粒度查询日志ID。

系统包含两个函数：

1. put(id: int, timestamp: str)：存入一条日志，id是日志编号，timestamp格式固定为"YYYY:MM:DD:HH:MM:SS"。
2. retrieve(start: str, end: str, granularity: str) -> List[int]：查询日志，返回所有时间落在 [start, end] 区间内的日志id，时间比较只到给定粒度，忽略后面更小的时间单位。

粒度可选值（从大到小）：
Year、Month、Day、Hour、Minute、Second

粒度含义举例：

• granularity = “Day”：比较时间只到天，后面的小时、分钟、秒全部忽略。

例如：start=“2017:01:01:23:59:59”，end=“2017:01:02:00:00:00”，粒度Day
等价于：查询 2017-01-01 ~ 2017-01-02 的所有日志，不管小时分秒。

示例

LogSystem log = new LogSystem(); log.put(1, "2017:01:01:23:59:59"); log.put(2, "2017:01:02:23:59:59"); log.put(3, "2017:01:03:23:59:59"); log.retrieve("2017:01:01:23:59:59", "2017:01:02:00:00:00", "Day"); // 输出 [1,2]

说明

• 日志ID唯一；
• 最多500条日志；
• 时间字符串固定长度，用冒号分隔6段；
• 查询是闭区间[start, end]。

费曼学习法拆解本题（通俗讲解，像讲给小白）

第一步：看懂题目到底要干嘛（费曼第一步：用大白话复述需求）

想象你在做服务器日志平台：

• 不断收到日志，每条日志有编号 + 时间戳字符串，格式固定年:月:日:时:分:秒；
• 用户查询的时候，可以指定精度：只按年查 / 按月查 / 按天查……

按天查 = 只要年月日在区间里就行，几点几分几秒不管。

核心难点：截断时间字符串。
时间戳被:切分成6个部分：
索引：0=Year，1=Month，2=Day，3=Hour，4=Minute，5=Second

粒度和截断下标映射：

举例子：时间"2017:01:01:23:59:59"，粒度Day，截断取前3段 →"2017:01:01"
所有日志的时间都做同样截断，然后比较字符串大小，字符串字典序 和真实时间顺序完全一致！
因为时间都是固定长度补零，字符串直接比较就等价时间大小，这是本题最大的技巧！

第二步：思考两种解法思路（费曼第二步：拆解方案，对比优劣）

解法1：朴素暴力（推荐，代码最简单，适合本题数据量≤500）

思路：

1. 用列表保存所有(id, timestamp)；
2. 建立字典：粒度→截断到第几段；
3. retrieve函数：
   • 拿到截断位置index；
   • 把start、end都截断，得到start_cut, end_cut；
   • 遍历全部日志，把每条日志的timestamp同样截断；
   • 如果start_cut ≤ log_cut ≤ end_cut，就把id收集返回。

✅优点：代码简短，逻辑直观，小数据量完全够用；
❌缺点：每次查询遍历全部日志，日志量大的时候性能差。

解法2：有序存储+二分查找（优化版，适合大量日志）

思路：

1. put的时候，把日志按timestamp有序插入列表，保持列表一直有序；
2. retrieve的时候，截断start/end；
3. 使用二分查找快速找到满足区间的左右边界，不用遍历全部；
   ✅优点：查询O(logN)，适合日志很多场景；
   ❌缺点：插入时维护有序，代码稍微复杂。

题目限制最多500条日志，暴力解法完全够用，面试优先写暴力解法，不容易写错。

第三步：边界测试（费曼第三步：找坑点）

坑1：字符串截断！不是取字符，是按冒号分段后取前N段，再拼接。
坑2：闭区间，等于start或end都要算进去；
坑3：时间字符串固定补零，所以字符串字典序可以直接比较时间，不需要转datetime。

第四步：现实应用场景举例

1. 服务器日志平台：日志入库，支持按年/月/日检索日志，不需要精确到秒；
2. IoT设备上报日志：设备定时上报，查询可以按天粒度筛选设备事件；
3. 审计系统：审计记录按时间保存，管理员查询时选择时间粒度；

例如运维想看1月1日~1月2日的所有日志，不管几点，粒度选Day，就是本题retrieve的场景。

Python代码实现（解法1：暴力遍历，每行详细注释）

fromtypingimportListclassLogSystem:def__init__(self):# 初始化日志存储列表，每个元素是元组 (日志id, 时间戳字符串)self.logs=[]# 建立粒度映射字典：key=粒度字符串，value=保留到第几个分段下标# 分段：0年，1月，2日，3时，4分，5秒self.gran_map={"Year":0,"Month":1,"Day":2,"Hour":3,"Minute":4,"Second":5}defput(self,id:int,timestamp:str)->None:""" 存入一条日志 :param id: 日志唯一编号 :param timestamp: "YYYY:MM:DD:HH:MM:SS" 格式时间字符串 """# 直接追加到日志列表self.logs.append((id,timestamp))defretrieve(self,start:str,end:str,granularity:str)->List[int]:""" 根据时间范围和粒度查询日志id :param start: 查询起始时间字符串 :param end: 查询结束时间字符串 :param granularity: 时间粒度 Year/Month/Day/Hour/Minute/Second :return: 符合条件的id列表 """# 获取当前粒度对应的截断下标cut_idx=self.gran_map[granularity]# 把起始时间按冒号切分成列表start_parts=start.split(":")# 截断，取前cut_idx+1段，再合并为字符串start_cut=":".join(start_parts[:cut_idx+1])# 处理结束时间，同样截断end_parts=end.split(":")end_cut=":".join(end_parts[:cut_idx+1])# 准备保存结果id列表result_ids=[]# 遍历全部日志forlog_id,log_tsinself.logs:# 拆分当前日志时间log_parts=log_ts.split(":")# 截断日志时间到指定粒度log_cut=":".join(log_parts[:cut_idx+1])# 判断：截断后的时间在 [start_cut, end_cut] 闭区间# 字符串字典序比较，等价真实时间大小（固定补零格式）ifstart_cut<=log_cut<=end_cut:result_ids.append(log_id)# 返回符合条件的idreturnresult_ids# ========== 测试示例 ==========if__name__=="__main__":# 创建日志系统实例obj=LogSystem()# 添加三条日志obj.put(1,"2017:01:01:23:59:59")obj.put(2,"2017:01:02:23:59:59")obj.put(3,"2017:01:03:23:59:59")# 查询，粒度Day，返回 [1,2]res=obj.retrieve("2017:01:01:23:59:59","2017:01:02:00:00:00","Day")print(res)# [1, 2]

优化解法：有序列表 + bisect二分查找（Python）

费曼补充：数据量大时，每次put保持有序，查询用二分定位边界，减少遍历次数。

importbisectfromtypingimportListclassLogSystem:def__init__(self):# 保存元组 (timestamp字符串, id)，始终保持列表按timestamp升序self.logs=[]# 粒度映射：key粒度，value截断下标self.gran_map={"Year":0,"Month":1,"Day":2,"Hour":3,"Minute":4,"Second":5}defput(self,id:int,timestamp:str)->None:"""插入日志，维持列表有序，bisect找到插入位置"""# bisect只比较第一个元素timestampbisect.insort(self.logs,(timestamp,id))defretrieve(self,start:str,end:str,granularity:str)->List[int]:cut_idx=self.gran_map[granularity]# 截断startstart_parts=start.split(":")start_cut=":".join(start_parts[:cut_idx+1])# 截断endend_parts=end.split(":")end_cut=":".join(end_parts[:cut_idx+1])res=[]# 遍历有序列表，一旦日志截断时间>end_cut，就break（提前终止）forts,log_idinself.logs:ts_parts=ts.split(":")ts_cut=":".join(ts_parts[:cut_idx+1])ifts_cut>end_cut:breakifstart_cut<=ts_cut<=end_cut:res.append(log_id)returnres# 测试if__name__=="__main__":obj=LogSystem()obj.put(1,"2017:01:01:23:59:59")obj.put(2,"2017:01:02:23:59:59")obj.put(3,"2017:01:03:23:59:59")print(obj.retrieve("2017:01:01:23:59:59","2017:01:02:00:00:00","Day"))

复杂度分析

1. 暴力解法
   put：O(1)；retrieve：O(N)，N日志条数，本题N≤500，性能无压力。
2. bisect有序解法
   put：O(N)（insort插入数组需要移动元素）；retrieve：最好O(logN)，提前break。

如果是海量日志，需要数据库索引，而不是内存列表。

费曼复盘总结

这道题不是考复杂算法，而是考字符串预处理 + 理解粒度截断。
核心 trick：固定补零的时间字符串，字典序直接等价时间顺序，不用转datetime对象，简化代码。