公司网站优化教育培训机构报名

146. LRU 缓存 - 力扣（LeetCode）

法1：

调用java现有的LinkedHashMap的方法，但不太理解反正都不需要扩容，super(capacity, 1F, true);不行吗，干嘛还弄个装载因子0.75还中途扩容一次浪费时间。

class LRUCache extends LinkedHashMap<Integer, Integer>{private int capacity;public LRUCache(int capacity) {super(capacity, 0.75F, true);this.capacity = capacity;}public int get(int key) {return super.getOrDefault(key, -1);}public void put(int key, int value) {super.put(key, value);}@Overrideprotected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {return size() > capacity; }
}作者：力扣官方题解
链接：https://leetcode.cn/problems/lru-cache/solutions/259678/lruhuan-cun-ji-zhi-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

法2：

要实现O(1)的get和put，那得用哈希表但手撸一个哈希难度太大，应该不至于考那么过分，那就基于使用现有map的前提下实现LRU缓存。关键是要记录最近最少使用的是哪一个，那么需要每次将最新使用的放到“最后面”，这样每次取“最前面”那个进行淘汰就是最近最少使用的。那么采用双向链表比较合适，队列，栈又不能从中间取元素；数组从中间移动到最前面，移动太多，时间复杂度高；单向链表的话需要知道被移动元素的前一个元素才方便移动，所以最后相比之下双向链表最合适。 

双向链表放哪些内容呢，前后指针是要放的，value是要放的，key也需要因为当容量满了要删除map中head指向的节点，那么就要从这个双向链表节点中获取到key才行。

另外可以使用哑结点技巧，即head，tail都用一个不存value的空节点表示，也叫伪头结点，伪尾结点。这样有很多好处，1.当你尾插入时，正常不用哑结点要分3种情况讨论，（1）插入时，链表为空，head,tail都为空；（2）head=tail时即仅一个节点时（3）2个即以上节点时（正常情况时）,

2，当删除链表中head时，也要分2种情况，（1）capacity为1时，head = tail；（2）正常情况；

当使用哑结点技巧后，尾插和删除head都只用1种情况处理，简化太多。

class LRUCache {class DoubleLinkedList {int key; //不存key，到时候不好删除int val;DoubleLinkedList prev;DoubleLinkedList next;public DoubleLinkedList() {};public DoubleLinkedList(int key, int val) {this.key = key;this.val = val;}};private Map<Integer, DoubleLinkedList> map;private DoubleLinkedList head;private DoubleLinkedList tail;private int capacity;private int size;public LRUCache(int capacity) {map = new HashMap<Integer, DoubleLinkedList>(capacity, 1F);//哑结点head = new DoubleLinkedList();tail = new DoubleLinkedList();head.next = tail;tail.prev = head;this.capacity = capacity;size = 0;}public int get(int key) {if(!map.containsKey(key)) {return -1;}//含有，则1.更新到链表末尾，2.返回DoubleLinkedList node = map.get(key);//更新到链表尾部move2Tail(node);return node.val;}public void put(int key, int value) {//1.之前就存在if(map.containsKey(key)) {DoubleLinkedList node = map.get(key);node.val = value;//更新最新使用move2Tail(node);return;} else if(size < capacity) {//2.容量没满 新添加add(key, value);size++;return;} // 3.满了需要替换//3.1删除最久没使用的//tail末尾也搞个哑结点，不然capacity为1时，删除时还要考虑head.next.next为空的情况map.remove(head.next.key);deleteNode(head.next);// 3.2新添加进mapadd(key, value);}//更新最新使用，移到链表尾部public void move2Tail(DoubleLinkedList node) {//正常分3种情况，1.是head，2.在中间，3.本就在tail//利用头部和尾部哑结点，头,尾结点先用一个没有实际意义的节点，就可以1,2，3情况全合并了// 1.原链表中先删除节点deleteNode(node);// 2.插入到末尾insert2Tail(node);}//从链表中删除节点public void deleteNode(DoubleLinkedList node) {node.prev.next = node.next;node.next.prev = node.prev;}//新增map节点public void add(int key, int value) {DoubleLinkedList newNode = new DoubleLinkedList(key, value);//用了尾部哑结点，就不管是不是第一次插入都同样处理了map.put(key, newNode);insert2Tail(newNode);}//插入到尾部public void insert2Tail(DoubleLinkedList node) {node.prev = tail.prev;tail.prev.next = node;node.next = tail;tail.prev = node;}
}/*** 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);*/