力扣——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
题目描述：
https://i-blog.csdnimg.cn/direct/c70d52d94ccf4f3ca880c28f020f2a46.png
思路：
[*]提到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放到链表最前面
实当代码：
[*]
class LRUCache {
class Dulinked{
Dulinked prev;
Dulinked next;
int key;
int value;
public Dulinked(){};
public Dulinked(int _key,int _value){
key = _key;
value = _value;
}
}
private int size;
private Map<Integer,Dulinked> table = new HashMap<Integer,Dulinked>();
private int capacity;
private Dulinked head,end;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new Dulinked();
end = new Dulinked();
head.next = end;
end.prev = head;
}
public int get(int key) {
Dulinked node = table.get(key);
if(node == null){
return -1;
}
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Dulinked node = table.get(key);
if(node == null){
Dulinked newNode = new Dulinked(key,value);
table.put(key,newNode);
addToHead(newNode);
size++;
if(size > capacity){
Dulinked end = removeEnd();
table.remove(end.key);
size--;
}
}
else{
node.value = value;
moveToHead(node);
}
}
private void removeNode(Dulinked node){
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addToHead(Dulinked node){
head.next.prev = node;
node.next = head.next;
node.prev = head;
head.next = node;
}
private void moveToHead(Dulinked node){
removeNode(node);
addToHead(node);
}
private Dulinked removeEnd(){
Dulinked res = end.prev;
removeNode(res);
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);
*/
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]