力扣——146.LRU缓存

题目链接：

https://leetcode.cn/problems/lru-cache/solutions/259678/lruhuan-cun-ji-zhi-by-leetcode-solution/?envType=study-plan-v2&envId=top-100-liked
题目描述：

思路：

• 提到key-value一定有map；
  
• 要实现迩来最少利用，最常见的一种思路就是利用flag，某一个数迩来利用了，让其flag+1，这种方式比较贫苦，因为如果数据许多，每一个都必要flag，占用的空间变大；
  
• 另一种思路就是排序，如果这个数迩来利用了，就让他排到前/后面，这就必要这些数可以随意的前后移动，可以利用链表；这里规定排在前面
  
• 如果凌驾容量，必要删除排在末了面的数并把新加的数放在最前面，
  
• 删除的操作比较贫苦，因为要找到要删除节点的前后节点，如果用单向链表，必要遍历才华找到他前面的，如果用双向链表就方便了
  
• 可以加入虚拟头和虚拟尾，这样就不必要对头结点和尾节点做特殊处理了
  

综上，必要利用map和双向链表完成
详细要怎么做：
数据存储方式：map内里存放key和node，全部的node组成一个双向链表，node是双向链表的节点，node内里存放他的前后节点，以及key、value这两个值，一样平常来说node内里只必要存放value就行，但是这里也要放key，因为后面会用到。
对于新增：要把key和node放入map内里；先看一下map内里有没有这个key，有的话就更新原有node的value值；没有的话就加到map内里，同时，node加入双向链表的最前面，新增后还要看链表的长度是否已经凌驾容量，凌驾的话就把末了一个node删除，注意也要把map内里的key删除，这个key在node内里有（这就是为什么node内里也要存key）。
对于获取：先看一下map内里有没有这个key，有的话返回这个node，并把这个node放到链表最前面
实当代码：

• 
  

1. class LRUCache {
3.     class Dulinked{
4.         Dulinked prev;
5.         Dulinked next;
6.         int key;
7.         int value;
8.         public Dulinked(){};
9.         public Dulinked(int _key,int _value){
10.             key = _key;
11.             value = _value;
12.         }
13.     }
16.     private int size;
17.     private Map<Integer,Dulinked> table = new HashMap<Integer,Dulinked>();
18.     private int capacity;
19.     private Dulinked head,end;
21.     public LRUCache(int capacity) {
22.         this.size = 0;
23.         this.capacity = capacity;
24.         head = new Dulinked();
25.         end = new Dulinked();
26.         head.next = end;
27.         end.prev = head;
28.     }
29.    
30.     public int get(int key) {
31.         Dulinked node = table.get(key);
32.         if(node == null){
33.             return -1;
34.         }
35.         moveToHead(node);
36.         return node.value;
38.     }
39.    
40.     public void put(int key, int value) {
41.         Dulinked node = table.get(key);
42.         if(node == null){
43.             Dulinked newNode = new Dulinked(key,value);
44.             table.put(key,newNode);
45.             addToHead(newNode);
46.             size++;
47.             if(size > capacity){
48.                 Dulinked end = removeEnd();
49.                 table.remove(end.key);
50.                 size--;
51.             }
52.         }
53.         else{
54.             node.value = value;
55.             moveToHead(node);
56.         }
57.     }
59.     private void removeNode(Dulinked node){
60.         node.prev.next = node.next;
61.         node.next.prev = node.prev;
62.     }
64.     private void addToHead(Dulinked node){
65.         head.next.prev = node;
66.         node.next = head.next;
67.         node.prev = head;
68.         head.next = node;
70.     }
71.    
72.     private void moveToHead(Dulinked node){
73.         removeNode(node);
74.         addToHead(node);
75.     }
77.     private Dulinked removeEnd(){
78.         Dulinked res = end.prev;
79.         removeNode(res);
80.         return res;
81.     }
83. }
85. /**
86. * Your LRUCache object will be instantiated and called as such:
87. * LRUCache obj = new LRUCache(capacity);
88. * int param_1 = obj.get(key);
89. * obj.put(key,value);
90. */

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。