设计题 解题模板

适用场景

数据结构设计：LRU、Trie、LFU、线程安全

通用模板

LRU 缓存

 
# 哈希表 + 双向链表
 
class DLinkedNode:
 
    def __init__(self, key=0, val=0):
 
        self.key = key; self.val = val
 
        self.prev = None; self.next = None
 
#       超出容量则删除尾部
 

Trie（前缀树）

 
class TrieNode:
 
    def __init__(self):
 
        self.children = [None]*26
 
        self.is_end = False
 
# insert/search/startsWith 都从 root 开始逐字符走
 

关键要点

• LRU 为什么用双向链表？O(1) 删除需知前驱

• Trie 空间换时间，前缀匹配比哈希表快

• 设计题画图讲清思路再写代码

→ 查看该分类题目：LeetCode学习路线图 > 十五、设计题

---

关联题型

关联题型	常见结合方式	典型题目
链表	链表实现LRU	146LRU缓存
栈与队列	栈实现队列 / 队列实现栈	225/232互相实现
堆	堆维护数据流中位数	295数据流中位数