//运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
//
// 获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
//写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在
//写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
//
//
//
// 进阶:
//
// 你是否可以在 O(1) 时间复杂度内完成这两种操作？
//
//
//
// 示例:
//
// LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
//
//cache.put(1, 1);
//cache.put(2, 2);
//cache.get(1); // 返回 1
//cache.put(3, 3); // 该操作会使得关键字 2 作废
//cache.get(2); // 返回 -1 (未找到)
//cache.put(4, 4); // 该操作会使得关键字 1 作废
//cache.get(1); // 返回 -1 (未找到)
//cache.get(3); // 返回 3
//cache.get(4); // 返回 4
//
// Related Topics 设计
import java.util.HashMap;
import java.util.Map;
//leetcode submit region begin(Prohibit modification and deletion)
class LRUCache {
//定义一个类
class Node{
int key;
int value;
Node pre;
Node next;
public Node(int key,int value){
this.key=key;
this.value=value;
}
}
//定义基本信息
Node head;
Node tail;
Map<Integer,Node> map;
//当前大小
int size=0;
//容量
int capacity;
public LRUCache(int capacity) {
head=new Node(0,0);
tail=new Node(0,0);
head.next=tail;
tail.pre=head;
map=new HashMap<>();
size=0;
this.capacity=capacity;
}
//取值操作
//1:有值，删除老key，更新新key
//2:无值：返回-1
public int get(int key) {
if(map.containsKey(key)){
Node node=map.get(key);
remove(key);
addHead(key,node.value);
return node.value;
}
else{
return -1;
}
}
//存值操作
//1:不存在 :直接队首
//2：存在：删除key，对应值更新到队首
public void put(int key, int value) {
if(map.containsKey(key)){
remove(key);
addHead(key,value);
}else{
addHead(key,value);
}
}
//根据key删除对应的节点
private void remove(int key){
Node node=map.get(key);
Node next=node.next;
Node pre=node.pre;
pre.next=next;
next.pre=pre;
map.remove(key);
size--;
}
//在head后加一个node
private void addHead(int key,int value){
Node node=new Node(key,value);
Node next=head.next;
head.next=node;
node.next=next;
next.pre=node;
node.pre=head;
size++;
map.put(key,node);
if(size>capacity){
Node preTail=tail.pre;
remove(preTail.key);
}
}
}
/**
* 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);
*/
//leetcode submit region end(Prohibit modification and deletion)
