LeetCode 第359题：日志速率限制器

📖 文章摘要

本文详细解析LeetCode第359题“日志速率限制器”，这是一道设计类问题。文章提供了基于哈希表的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升系统设计能力的读者。

核心知识点： 哈希表、设计模式、时间戳 难度等级： 简单 推荐人群： 具有一定数据结构基础，想要提升系统设计能力的程序员

题目描述

请你设计一个日志系统，可以流式接收日志及其时间戳。

该日志系统支持以下操作：

接收日志：接收一条日志消息及其时间戳
判断是否应该打印：如果该条日志在给定的时间窗口内（例如10秒）没有被打印过，则返回true，否则返回false

示例

示例 1：

Logger logger = new Logger();

// 日志内容 "foo" 在时间戳 1 到达系统
logger.shouldPrintMessage(1, "foo"); // 返回 true

// 日志内容 "bar" 在时间戳 2 到达系统
logger.shouldPrintMessage(2, "bar"); // 返回 true

// 日志内容 "foo" 在时间戳 3 到达系统
logger.shouldPrintMessage(3, "foo"); // 返回 false

// 日志内容 "bar" 在时间戳 8 到达系统
logger.shouldPrintMessage(8, "bar"); // 返回 false

// 日志内容 "foo" 在时间戳 10 到达系统
logger.shouldPrintMessage(10, "foo"); // 返回 false

// 日志内容 "foo" 在时间戳 11 到达系统
logger.shouldPrintMessage(11, "foo"); // 返回 true

提示

0 <= timestamp <= 10^9
每个 timestamp 都会严格递增
1 <= message.length <= 30
最多调用 10^4 次 shouldPrintMessage

解题思路

本题可以使用哈希表来解决：

使用哈希表存储每个消息的最后打印时间
对于新消息，检查是否在时间窗口内
如果不在时间窗口内，更新最后打印时间并返回true
否则返回false

时间复杂度： O(1) 空间复杂度： O(n)，其中n是不同消息的数量

图解思路

数据结构设计

组件	数据结构	用途
消息记录	HashMap<message, timestamp>	存储消息的最后打印时间

操作流程分析

操作	步骤	说明
检查消息	1. 查找消息最后打印时间 2. 判断是否在时间窗口内	O(1)时间复杂度
更新消息	1. 更新消息最后打印时间	O(1)时间复杂度

代码实现

C# 实现

public class Logger {
    private Dictionary<string, int> messageTimestamps;
    private const int WINDOW_SIZE = 10;

    public Logger() {
        messageTimestamps = new Dictionary<string, int>();
    }
    
    public bool ShouldPrintMessage(int timestamp, string message) {
        if (!messageTimestamps.ContainsKey(message) || 
            timestamp - messageTimestamps[message] >= WINDOW_SIZE) {
            messageTimestamps[message] = timestamp;
            return true;
        }
        return false;
    }
}

Python 实现

class Logger:
    def __init__(self):
        self.message_timestamps = {}
        self.window_size = 10

    def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
        if message not in self.message_timestamps or \
           timestamp - self.message_timestamps[message] >= self.window_size:
            self.message_timestamps[message] = timestamp
            return True
        return False

C++ 实现

class Logger {
private:
    unordered_map<string, int> message_timestamps;
    const int window_size = 10;

public:
    Logger() {}
    
    bool shouldPrintMessage(int timestamp, string message) {
        if (message_timestamps.find(message) == message_timestamps.end() || 
            timestamp - message_timestamps[message] >= window_size) {
            message_timestamps[message] = timestamp;
            return true;
        }
        return false;
    }
};

执行结果

C# 实现

执行用时：156 ms
内存消耗：45.2 MB

Python 实现

执行用时：32 ms
内存消耗：16.4 MB

C++ 实现

执行用时：0 ms
内存消耗：7.2 MB

性能对比

语言	执行用时	内存消耗	特点
C++	0 ms	7.2 MB	执行效率最高，内存占用最小
Python	32 ms	16.4 MB	代码简洁，易于理解
C#	156 ms	45.2 MB	类型安全，内存占用较大

代码亮点

🎯 使用哈希表高效存储和查询
💡 常量定义时间窗口大小
🔍 处理边界情况和特殊情况
🎨 代码结构清晰，易于维护

常见错误分析

🚫 未考虑时间戳递增的特性
🚫 时间窗口计算错误
🚫 内存使用效率低下
🚫 未处理并发访问问题

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
哈希表	O(1)	O(n)	高效，实现简单	需要额外空间
队列	O(n)	O(n)	自动清理过期消息	实现复杂

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第359题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

提示

解题思路

图解思路

数据结构设计

操作流程分析

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流