设计一个支持以下操作的LRU缓存（最近最少使用）：get(key) - 获取key对应的value，如果不存在返回-1；put(key, value) - 插入或更新key-value对，如果容量已满则移除最久未使用的元素。要求get和put的时间复杂度均为O(1)。
分类: technical
难度: medium
标签:
答题技巧
经典考察点：哈希表+双向链表的组合；哈希表用于O(1)查找，链表用于维护访问顺序；get时需要将节点移动到头部，put时也需要处理已存在/容量满的情况；注意链表头尾节点的定义（dummy节点更方便）。
参考答案
使用HashMap存储<key, Node>，Node包含key、value、prev、next；使用双向链表维护顺序，新访问/插入的节点移动到头部（最近使用）；容量满时删除尾部节点（最久未使用）并从HashMap移除。get和put均在O(1)完成。