LeetCode 635 设计日志存储系统Design Log Storage System难度Medium标签设计、字符串、有序存储、日志检索题目原文题目你需要设计一个日志存储系统可以存放日志并且根据时间范围、指定时间粒度查询日志ID。系统包含两个函数put(id: int, timestamp: str)存入一条日志id是日志编号timestamp格式固定为YYYY:MM:DD:HH:MM:SS。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个部分索引0Year1Month2Day3Hour4Minute5Second粒度和截断下标映射granularity保留到第几段下标保留部分Year0YYYYMonth1YYYY:MMDay2YYYY:MM:DDHour3YYYY:MM:DD:HHMinute4YYYY:MM:DD:HH:MMSecond5YYYY:MM:DD:HH:MM:SS举例子时间2017:01:01:23:59:59粒度Day截断取前3段 →2017:01:01所有日志的时间都做同样截断然后比较字符串大小字符串字典序 和真实时间顺序完全一致因为时间都是固定长度补零字符串直接比较就等价时间大小这是本题最大的技巧第二步思考两种解法思路费曼第二步拆解方案对比优劣解法1朴素暴力推荐代码最简单适合本题数据量≤500思路用列表保存所有(id, timestamp)建立字典粒度→截断到第几段retrieve函数拿到截断位置index把start、end都截断得到start_cut, end_cut遍历全部日志把每条日志的timestamp同样截断如果start_cut ≤ log_cut ≤ end_cut就把id收集返回。✅优点代码简短逻辑直观小数据量完全够用❌缺点每次查询遍历全部日志日志量大的时候性能差。解法2有序存储二分查找优化版适合大量日志思路put的时候把日志按timestamp有序插入列表保持列表一直有序retrieve的时候截断start/end使用二分查找快速找到满足区间的左右边界不用遍历全部✅优点查询O(logN)适合日志很多场景❌缺点插入时维护有序代码稍微复杂。题目限制最多500条日志暴力解法完全够用面试优先写暴力解法不容易写错。第三步边界测试费曼第三步找坑点坑1字符串截断不是取字符是按冒号分段后取前N段再拼接。坑2闭区间等于start或end都要算进去坑3时间字符串固定补零所以字符串字典序可以直接比较时间不需要转datetime。第四步现实应用场景举例服务器日志平台日志入库支持按年/月/日检索日志不需要精确到秒IoT设备上报日志设备定时上报查询可以按天粒度筛选设备事件审计系统审计记录按时间保存管理员查询时选择时间粒度例如运维想看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_idxself.gran_map[granularity]# 把起始时间按冒号切分成列表start_partsstart.split(:)# 截断取前cut_idx1段再合并为字符串start_cut:.join(start_parts[:cut_idx1])# 处理结束时间同样截断end_partsend.split(:)end_cut:.join(end_parts[:cut_idx1])# 准备保存结果id列表result_ids[]# 遍历全部日志forlog_id,log_tsinself.logs:# 拆分当前日志时间log_partslog_ts.split(:)# 截断日志时间到指定粒度log_cut:.join(log_parts[:cut_idx1])# 判断截断后的时间在 [start_cut, end_cut] 闭区间# 字符串字典序比较等价真实时间大小固定补零格式ifstart_cutlog_cutend_cut:result_ids.append(log_id)# 返回符合条件的idreturnresult_ids# 测试示例 if__name____main__:# 创建日志系统实例objLogSystem()# 添加三条日志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]resobj.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_idxself.gran_map[granularity]# 截断startstart_partsstart.split(:)start_cut:.join(start_parts[:cut_idx1])# 截断endend_partsend.split(:)end_cut:.join(end_parts[:cut_idx1])res[]# 遍历有序列表一旦日志截断时间end_cut就break提前终止forts,log_idinself.logs:ts_partsts.split(:)ts_cut:.join(ts_parts[:cut_idx1])ifts_cutend_cut:breakifstart_cutts_cutend_cut:res.append(log_id)returnres# 测试if__name____main__:objLogSystem()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))复杂度分析暴力解法putO(1)retrieveO(N)N日志条数本题N≤500性能无压力。bisect有序解法putO(N)insort插入数组需要移动元素retrieve最好O(logN)提前break。如果是海量日志需要数据库索引而不是内存列表。费曼复盘总结这道题不是考复杂算法而是考字符串预处理 理解粒度截断。核心 trick固定补零的时间字符串字典序直接等价时间顺序不用转datetime对象简化代码。