原题链接
解题思路
总体思路:采用散列表(HashMap)和自写的双向链表Node
get:
如果不在散列表中,直接返回-1;
在散列表中,则在双向链表中删除键为key的节点,再将该节点加入双向链表尾部,返回节点value值。
put:
-
如果不在散列表中:
将put的节点值加入散列表,同时加入双向链表尾部。
如果之前已达到最大容量,则需要先删去双向链表的头结点,同时删散列表中头节点对应的值;
-
否则:
在双向链表中删除键为key的节点,更改其对应的value值,再将待put节点加入双向链表尾部。
代码
import java.util.HashMap;
class LRUCache {
HashMap<Integer, Node> map;
Node head;
Node tail;
int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
head = new Node();
tail = new Node();
head.next = tail;
tail.pre = head;
map = new HashMap<>();
}
public int get(int key) {
// System.out.printf("%s %d\n", "put", key);
// print();
Node node = map.get(key);
if (node == null)
return -1;
delete(node);
append(node);
return node.value;
}
public void put(int key, int value) {
// System.out.printf("%s %d %d\n", "put", key, value);
// print();
Node node = map.get(key);
if (node == null) {
if (capacity == map.size()) {
map.remove(head.next.key);
delete(head.next);
}
Node node1 = new Node(key, value);
append(node1);
map.put(key, node1);
} else {
delete(node);
node.value = value;
append(node);
}
}
// 从链表中删除节点 node
void delete(Node node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
// 将节点 node 添加到双向链表末尾
void append(Node node) {
node.pre = tail.pre;
tail.pre.next = node;
node.next = tail;
tail.pre = node;
}
void print() {
Node node = this.head.next;
while (node != tail) {
System.out.printf("%d:%d ", node.key, node.value);
node = node.next;
}
System.out.println();
}
}
class Node {
int key;
int value;
Node pre;
Node next;
public Node() {
}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
/**
* 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);
*/