1、題目
image.png
2填硕、分析
使用雙向鏈表來存儲(chǔ)緩存節(jié)點(diǎn)麦萤。方便按照使用順序來排序。
使用hashmap來存key和緩存節(jié)點(diǎn)扁眯，方便快速檢索壮莹。
3、代碼
class LRUCache {
class CacheNode {
public int key;
public int value;
public CacheNode prev;
public CacheNode next;
public CacheNode(int k, int v){
this.key = k;
this.value = v;
}
}
private CacheNode head, tail;
private int cap;
private HashMap<Integer, CacheNode> map = new HashMap<>();
public LRUCache(int capacity) {
cap = capacity;
head = new CacheNode(0, 0);
tail = new CacheNode(0, 0);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if(!map.containsKey(key)){
return -1;
}
CacheNode node = map.get(key);
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
if(!map.containsKey(key)){
if(cap == map.size()){
removeLast();
}
CacheNode node = new CacheNode(key, value);
addToHead(node);
map.put(key, node);
}else{
CacheNode node = map.get(key);
node.value = value;
moveToHead(node);
}
return;
}
//后面的這三個(gè)方法是抽象出來的姻檀。方便重復(fù)調(diào)用
public void addToHead(CacheNode node){
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
public void moveToHead(CacheNode node){
node.prev.next = node.next;
node.next.prev = node.prev;
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
public void removeLast(){
map.remove(tail.prev.key);
tail.prev = tail.prev.prev;
tail.prev.next = tail;
}
}
/**
* 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);
*/
