九、LRU
访问 www.coding-time.cn 阅读原文动画效果，体验更佳。
最近最少使用（LRU）缓存按使用顺序组织项目，允许您快速识别最长时间未使用的项目。
想象一下衣服架，衣服总是挂在一边。要找到最近最少使用的项目，请查看架子的另一端的项目。
1. 问题描述
实现LRUCache类：
∙ LRUCache(int capacity) 使用正数大小capacity初始化LRU缓存。
∙ int get(int key) 如果存在key，则返回key的值，否则返回undefined。
∙ void set(int key, int value) 如果存在key，则更新key的值。否则，将key-value对添加到缓存中。如果此操作导致键的数量超过capacity，则删除最近最少使用的键。
函数get()和set()的平均时间复杂度必须为O(1)。
2. 实现
版本1：双向链表 + 哈希映射
请参阅LRUCache.js中的LRUCache实现示例。该解决方案使用HashMap快速访问缓存项（平均时间复杂度为O(1)）和DoublyLinkedList快速推广和驱逐缓存项（以保持最大允许的缓存容量，平均时间复杂度为O(1)）。
链表
带你读《图解算法小抄》九、LRU（2）https://developer.aliyun.com/article/1348200?groupCode=tech_library
