【leetcode hot 100 146】LRU缓存

解法一：（哈希表 + 双向链表）LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

• 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
• 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。

class LRUCache {class DLinkNode{int key;int value;DLinkNode prev;DLinkNode next;// 记得写构造函数public DLinkNode(){}public DLinkNode(int key, int value){this.key=key; this.value=value;}}private Map<Integer,DLinkNode> mapID = new HashMap<>();private int capacity;private int size;private DLinkNode head,tail;  // 全部放到构造函数去初始化public LRUCache(int capacity) {this.capacity = capacity;this.size = 0;head = new DLinkNode();tail = new DLinkNode();head.next = tail;tail.prev = head;}public int get(int key) {DLinkNode node = mapID.get(key);if(node==null){return -1;}// 将node放到双链表头部，表示刚刚访问过moveToHead(node);return node.value;}public void put(int key, int value) {DLinkNode node = mapID.get(key);if(node==null){// 不存在：申请node，放在头部，超过数量就删除尾部DLinkNode newNode = new DLinkNode(key, value);addNode(newNode);mapID.put(key,newNode); // mapID也要做相应的put和removesize++;if(size>capacity){DLinkNode tail = deleteTail();// mapID.remove(key)不可，要返回删除的key，以此为准来一移除mapID.remove(tail.key);size--;}}else{// 已经存在：修改v值，移到最前面node.value = value;moveToHead(node);}}private void moveToHead(DLinkNode node){removeNode(node);addNode(node);}private DLinkNode removeNode(DLinkNode node){node.prev.next = node.next;node.next.prev = node.prev;return node;}private void addNode(DLinkNode node){node.next = head.next;head.next = node;node.prev = head;node.next.prev = node;}private DLinkNode deleteTail(){DLinkNode res = removeNode(tail.prev);return res;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/

注意：

• 参数的初始化全部放到构造函数去初始化
• 双链表进行添加和移除时候，mapID也要做相应的put和remove
• mapID进行移除时，mapID.remove(key)不可，要返回删除的key，以此为准来一移除
• 双链表DLinkNode用于维护最近使用策略，哈希表mapID用于提供get和set操作