企业官网建设流程全解析

• 教程
• 文档
• 知识库

本篇技术指南以 AlgoNote 仓库中 design-log-storage-system.md 为骨架，完整讲解 LeetCode 0635「设计日志存储系统」的题目约束、算法思路与可运行代码，并结合仓库内 哈希表章节 的原理做源码级印证。读完本篇，你将掌握「利用字符串定长截取 + 字典比较实现多粒度区间检索」这一设计题的标准解法，并能独立实现 LogSystem 的 put / retrieve 两个接口。

一、题目速览：要设计一个怎样的日志存储系统

本题属于「设计」类题目，标签为设计、哈希表、字符串、有序集合，难度中等，收录于 AlgoNote 的 0600–0699 题解区间（见 docs/solutions/0600-0699/index.md 与 00_05_solutions_list.md）。

题目描述：系统会收到多条日志，每条日志都有唯一的id和timestamp。时间戳是形如Year:Month:Day:Hour:Minute:Second的字符串，例如2017:01:01:23:59:59，所有字段都是零填充的十进制数（即月份、日期等不足两位时补0）。

需要实现的接口：

start、end与timestamp格式相同。granularity从["Year", "Month", "Day", "Hour", "Minute", "Second"]六个值中选取。例如start = "2017:01:01:23:59:59"、end = "2017:01:02:23:59:59"、granularity = "Day"，意味着要查找从 2017 年 1 月 1 日到 2017 年 1 月 2 日这一「天」粒度范围内的日志，而忽略每条日志的Hour、Minute、Second字段。

数据范围与约束（题解原文完整保留）：

• 1 ≤ id ≤ 500
• 2000 ≤ Year ≤ 2017
• 1 ≤ Month ≤ 12
• 1 ≤ Day ≤ 31
• 0 ≤ Hour ≤ 23
• 0 ≤ Minute, Second ≤ 59
• granularity是["Year", "Month", "Day", "Hour", "Minute", "Second"]之一
• 最多调用put和retrieve各 500 次

约束总量非常小（至多 500 次操作），这意味着即便是「每次 retrieve 都遍历全部日志」的朴素做法，在最坏情况下也只需500 × 500 = 250000次字符串比较，完全在可接受范围内。这也正是思路一采用简单遍历的底气所在。

二、示例逐步推演：理解粒度截取的含义

题解中的示例完整复现如下：

输入： ["LogSystem", "put", "put", "put", "retrieve", "retrieve"] [[], [1, "2017:01:01:23:59:59"], [2, "2017:01:01:22:59:59"], [3, "2016:01:01:00:00:00"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year"], ["2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour"]] 输出： [null, null, null, null, [3, 2, 1], [2, 1]]

逐步执行：

LogSystem logSystem = new LogSystem() logSystem.put(1, "2017:01:01:23:59:59") logSystem.put(2, "2017:01:01:22:59:59") logSystem.put(3, "2016:01:01:00:00:00") # 返回 [3,2,1]，返回从 2016 年到 2017 年所有的日志。 logSystem.retrieve("2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year") # 返回 [2,1]，返回从 Jan. 1, 2016 01:XX:XX 到 Jan. 1, 2017 23:XX:XX 之间的所有日志 # 不返回日志 3 因为记录时间 Jan. 1, 2016 00:00:00 超过范围的起始时间 logSystem.retrieve("2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour")

关键理解点：

1. Year粒度：只比较前 4 个字符（年份部分），三条日志年份分别为2017、2017、2016，全部落在["2016", "2017"]区间内，因此返回[3, 2, 1]。

2. Hour粒度：比较前 13 个字符（到小时为止）。截取后：

   • 日志 1：2017:01:01:23
   • 日志 2：2017:01:01:22
   • 日志 3：2016:01:01:00
   • 区间：["2016:01:01:01", "2017:01:01:23"]

   日志 3 截取后的前缀2016:01:01:00小于区间下界2016:01:01:01，被排除，因此返回[2, 1]。注意这里retrieve返回的[2, 1]与 put 的先后顺序有关——遍历哈希表时按插入顺序（Python 3.7+ 字典保序），所以先插入的 2 排在前面。

这个例子揭示了本题最核心的机制：不同粒度 = 截取时间戳字符串的不同前缀长度，粒度越粗，前缀越短，匹配范围越宽。

三、思路一：哈希表 + 字符串前缀截取

3.1 算法设计

这是题解文档给出的标准思路：使用哈希表存储日志（键为日志 ID，值为时间戳），检索时根据时间粒度截取时间戳的相应前缀进行字典序比较。

算法步骤：

1. 初始化：创建哈希表logs，用于存储日志 ID 与时间戳的映射。
2. put(id, timestamp)：直接将id → timestamp写入哈希表，时间复杂度 O(1)。
3. retrieve(start, end, granularity)：
   • 根据时间粒度确定需要截取的时间戳前缀长度；
   • 截取start与end的对应前缀，得到区间上下界；
   • 遍历哈希表中所有日志，截取每条时间戳的对应前缀；
   • 判断截取结果是否落在[start_prefix, end_prefix]区间内（字符串字典序比较，闭区间包含两端）；
   • 返回所有满足条件的日志 ID 列表。

3.2 时间粒度与截取长度对照表

时间戳Year:Month:Day:Hour:Minute:Second的字符结构为：

• Year：4 位
• Month：2 位，前缀第 4~5 位（共 7 个字符，含冒号）
• Day：2 位，前缀到第 10 个字符
• Hour：2 位，前缀到第 13 个字符
• Minute：2 位，前缀到第 16 个字符
• Second：2 位，完整 19 个字符

因此各粒度对应的前缀截取长度如下（题解原文表格）：

该表的规律是「4 + 3 × k」，其中 k 为粒度层级索引（Year=0 … Second=5），每细化一层恰好多截取 3 个字符（一个冒号 + 两位数字）。这得益于题目要求的零填充十进制格式：所有字段定宽，使得「字典序比较 == 时间先后比较」严格成立。

3.3 完整可运行代码

题解原文代码（可直接在 LeetCode 编辑器或本地 Python 3 环境运行）：

from typing import List class LogSystem: def __init__(self): self.logs = {} # 存储日志 ID 和时间戳 # 时间粒度对应的截取长度 self.granularity_map = { "Year": 4, "Month": 7, "Day": 10, "Hour": 13, "Minute": 16, "Second": 19 } def put(self, id: int, timestamp: str) -> None: self.logs[id] = timestamp def retrieve(self, start: str, end: str, granularity: str) -> List[int]: # 根据时间粒度确定截取长度 length = self.granularity_map[granularity] # 截取 start 和 end 的相应部分 start_prefix = start[:length] end_prefix = end[:length] result = [] # 遍历所有日志 for log_id, timestamp in self.logs.items(): # 截取时间戳的相应部分 timestamp_prefix = timestamp[:length] # 判断是否在范围内 if start_prefix <= timestamp_prefix <= end_prefix: result.append(log_id) return result # Your LogSystem object will be instantiated and called as such: # obj = LogSystem() # obj.put(id, timestamp) # param_2 = obj.retrieve(start, end, granularity)

3.4 复杂度分析（题解原文）

• 时间复杂度：
  • put()：O(1)，哈希表直接写入。
  • retrieve()：O(n)，其中 n 是日志数量，需要遍历全部日志逐条比较。
• 空间复杂度：O(n)，需要存储 n 条日志的 ID 与时间戳。

在题目约束（最多 500 次操作、id 上限 500）下，最坏情况retrieve单次遍历 500 条日志，字符串前缀比较每次至多比较 19 个字符，性能完全充裕，这也是该朴素方案能够通过全部测试用例的原因。

四、思路二（延伸）：利用有序集合将检索加速到 O(log n + k)

题解标签中包含「有序集合」。从源码结构看，可以推断一种更优的变体：放弃按 ID 为键的哈希表，改为维护「时间戳 → ID 列表」的有序映射，从而用二分查找定位区间，避免每次全量扫描。其核心流程为：

1. put(id, timestamp)：以时间戳为排序键，把id追加到该时间戳对应的列表中。
2. retrieve(start, end, granularity)：
   • 先把start与end按粒度「截断」——但要注意，截断后需将end前缀补足到完整 19 位（用该粒度下的最大值补位），将start前缀补足到完整 19 位（用最小值补位），才能保证闭区间语义正确。
   • 例如granularity = "Year"时，start截断为"2016"后应补为"2016:01:01:00:00:00"，end截断为"2017"后应补为"2017:12:31:23:59:59"。
   • 然后对有序键集合做二分查找，直接定位[low, high]范围内的所有键，收集对应 ID。

该方案将retrieve降为 O(log n + k)（k 为命中日志数），更适合「日志量大、检索频繁」的场景，可作为进阶思考。由于题目数据规模很小，两种写法均可通过，思路一因实现最简而成为官方题解首选。

五、仓库侧印证：为什么「哈希表 + 定宽字符串」可行

本题的核心数据结构是哈希表。AlgoNote 的 03_06_hash_table.md 对哈希表的原理做了系统讲解：哈希表通过哈希函数将关键码 Key 映射到表内位置，实现高效的插入与查找，其基本操作流程为「插入关键码时用哈希函数计算区块索引并存入」「查找关键码时用同一哈希函数定位区块再检索」。

本题的logs字典正是这一原理的直接应用：

• put相当于「插入关键码」：以id为 Key，timestamp为 Value，哈希表定位并写入，摊还复杂度 O(1)；
• retrieve相当于「按 Value 条件做筛选」：由于哈希表按 Key 组织、不维护时间序，检索只能遍历全部条目，这正是思路一 O(n) 复杂度的来源。

这也解释了标签里「有序集合」的存在意义：若要让检索具备序相关加速能力，就需要换成有序的映射结构（如平衡树），即思路二。两种数据结构的取舍，正好对应哈希表章节中「不同结构解决不同查询需求」的设计思想。

此外，仓库中的设计类题解可以与本篇对照阅读，形成「设计 + 哈希表」解题方法的横向串联，例如：

• 0359. 日志速率限制器（设计、哈希表、数据流）：同样围绕「时间 + 日志」设计接口，用哈希表记录时间戳做限流判断；
• 0706. 设计哈希映射（设计、数组、哈希表、链表、哈希函数）：从零手写哈希表底层结构；
• 0622. 设计循环队列（设计、队列、数组、链表）：另一个经典的数据结构设计题。

完整的「哈希表题目」与「设计题目」索引可查阅 00_06_categories_list.md（哈希表题目列表在 哈希表题目 小节）。

六、边界与实现细节小结

综合题目约束与代码实现，以下是几个值得注意的边界点：

1. 闭区间语义：retrieve返回的是[start, end]包含两端的日志。前缀截取 +<=比较天然满足该语义，无需额外处理端点。
2. 零填充保证：题目保证所有字段是零填充十进制数（如01而非1），这是「字典序比较 == 时间序比较」的前提。若格式不统一，字符串比较会失效，必须先做规范化。
3. 粒度与前缀长度一一对应：granularity_map中 6 个长度值必须与时间戳格式严格匹配，任何一位偏差都会导致错误的检索结果。
4. 遍历顺序：Python 3.7+ 字典保持插入顺序，因此retrieve返回的 ID 顺序与put调用顺序一致（如示例输出[2, 1]）。若题目对返回顺序有额外要求，需要显式排序。
5. 数据规模小：最多 500 次操作、500 个 id，朴素遍历方案在时空上均无压力，优先保证正确性与简洁性。

七、总结

LeetCode 0635「设计日志存储系统」是一道典型的「设计 + 哈希表 + 字符串」综合题，其核心解法可概括为：

用哈希表存储id → timestamp，按粒度查表确定前缀长度，用字符串切片 + 字典序比较完成闭区间检索。

这一「定长前缀截取 + 字典序区间比较」的技巧，可以推广到任何「格式固定、字段定宽」的复合时间标识系统（如日志分析、指标监控中的时间桶聚合），是面试中值得沉淀的通用模式。掌握思路一（哈希表遍历）与思路二（有序集合二分）两种写法，即可在「简单正确」与「高效可扩展」之间做出合理权衡。

关联资料速查：

• 本题题解原文：docs/solutions/0600-0699/design-log-storage-system.md
• 哈希表原理章节：docs/03_stack_queue_hash_table/03_06_hash_table.md
• 题解目录索引：docs/solutions/0600-0699/index.md
• 全部题解列表（含本题条目）：docs/00_preface/00_05_solutions_list.md
• 分类题目列表（哈希表 / 设计）：docs/00_preface/00_06_categories_list.md

• 教程
• 文档
• 知识库