设计-功能系统

摘要: 力扣上的设计功能系统的题目分类汇总

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

本文总结了力扣上 2000 题以内的关于设计功能系统的 38 道题。将核心数据结构相同的放到了一起。刷完这份题目列表，力扣上的设计类的问题可以说刷爆了。

1. 带功能的基础数据结构

栈

题目	数据结构	索引结构	题解/ 备注
1381. 设计一个支持增量操作的栈	数组	无索引	设计一个支持增量操作的栈
716. 最大栈	链表	平衡树	加索引的链表
155. 最小栈	双栈	无索引	用额外的一个栈维护最小值
895. 最大频率栈	桶+栈	哈希表	力扣895-最大频率栈
1172. 餐盘栈	桶+栈	平衡树	桶内数据直接放平衡树上

哈希表

题目	数据结构	索引结构	题解
146. LRU缓存机制	链表	哈希表	力扣146-LRU,内存淘汰算法
460. LFU缓存	桶+链表	哈希表	力扣460-LFU
707. 设计链表	链表	哈希表	加索引的链表

---

2. 功能系统

用到多种数据结构或索引结果时，归类优先级：图 > 堆 > 队列 > 链表 > 平衡树 > 字典树 > 哈希表，优先级越低的数据结构使用越频繁

图

题目	数据结构	索引结构	题解
631. 设计 Excel 求和公式	邻接矩阵	无索引	力扣631-设计Excel求和公式

栈

题目	数据结构	索引结构	题解
1472. 设计浏览器历史记录	对顶栈	无索引	对顶栈

堆

题目	数据结构	索引结构	题解
295. 数据流的中位数	对顶堆	无索引	对顶堆
1500. 设计文件分享系统	堆	无索引	力扣1500-设计文件分享系统

队列

题目	数据结构	索引结构
346. 数据流中的移动平均值	队列	无索引
362. 敲击计数器	队列	无索引
353. 贪吃蛇	队列+哈希表	无索引
359. 日志速率限制器	队列+哈希表	无索引

链表

题目	数据结构	索引结构	题解
1429. 第一个唯一数字	链表	哈希表	索引链表
432. 全 O(1) 的数据结构	桶+链表	哈希表	力扣432-全O(1)的数据结构
379. 电话目录管理系统	链表+哈希表	无索引
355. 设计推特	链表+哈希表	无索引	力扣355-哈希表&链表多路归并

平衡树

题目	数据结构	索引结构
1146. 快照数组	哈希表+平衡树	哈希表和平衡树均自带索引
981. 基于时间的键值存储	哈希表+平衡树	哈希表和平衡树均自带索引
911. 在线选举	哈希表+平衡树	哈希表和平衡树均自带索引
1244. 力扣排行榜	哈希表+平衡树	哈希表和平衡树均自带索引
1348. 推文计数	哈希表+平衡树	哈希表和平衡树均自带索引
244. 最短单词距离 II	哈希表+平衡树	哈希表和平衡树均自带索引

字典树

题目	数据结构	索引结构	题解
211. 添加与搜索单词	Trie	自带索引
676. 实现一个魔法字典	Trie	自带索引
642. 设计搜索自动补全系统	Trie/哈希表	自带索引	力扣642-设计搜索自动补全系统
745. 前缀和后缀搜索	双向Trie	自带索引	双向Trie
588. 设计内存文件系统	Trie	自带索引	设计内存文件系统：平衡树TreeMap维护子节点的Trie
1268. 搜索推荐系统	Trie	自带索引
635. 设计日志存储系统	Trie	自带索引	力扣635-设计日志存储系统

哈希表

题目	数据结构	索引结构	题解
1396. 设计地铁系统	哈希表	自带索引
288. 单词的唯一缩写	哈希表	自带索引
1166. 设计文件系统	哈希表	自带索引
380. 常数时间插入、删除和获取随机元素	数组	哈希表	随机队列
381. O(1) 时间插入、删除和获取随机元素 - 允许重复	数组	哈希表	随机队列

---