public class LRUCache {
private class Node{
Node prev;
Node next;
int key;
int value;
public Node(int key, int value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
private int capacity;
private HashMap<Integer, Node> hs = new HashMap<Integer, Node>();
private Node head = new Node(-1, -1);
private Node tail = new Node(-1, -1);
public LRUCache(int capacity) {
this.capacity = capacity;
tail.prev = head;
head.next = tail;
}
public int get(int key) {
if( !hs.containsKey(key)) {
return -1;
}
// remove current
Node current = hs.get(key);
current.prev.next = current.next;
current.next.prev = current.prev;
// move current to tail
move_to_tail(current);
return hs.get(key).value;
}
public void set(int key, int value) {
// this internal `get` method will update the key's position in the linked list.
if (get(key) != -1) {
hs.get(key).value = value;
return;
}
if (hs.size() == capacity) {
hs.remove(head.next.key);
head.next = head.next.next;
head.next.prev = head;
}
Node insert = new Node(key, value);
hs.put(key, insert);
move_to_tail(insert);
}
private void move_to_tail(Node current) {
current.prev = tail.prev;
tail.prev = current;
current.prev.next = current;
current.next = tail;
}
}146 LRU cache
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- Design and implement a data structure for Least Recently ...
- 在做项目的时候往往会出现多图上传的功能,而恰巧服务器可能只支持单张上传，所以你要遍历请求，而全部上传完成后可能还要...
- 这是一篇主要以我的随机种族随机团队 2v2/3v3 经验为基础，面向中级玩家（大致黄金组排名靠前到钻石组排名靠后实...
