LeetCode 146 - LRU Cache

作者 QIFAN 日期 2017-02-15
LeetCode 146 - LRU Cache

原题链接: 146. LRU Cache


题干

设计一个数据结构来存储最近使用的缓存。有如下操作:getput
get(key) 若缓存中存在,则返回值,否则返回 -1 。
put(key, value) 存入键值对,若已经容量已满,则删除最久前使用的键值对。

Follow up:
能否用 $O(1)$ 的时间复杂度实现同时实现两种操作?

思路

get $O(1)$ 想到 map 。
按照使用时间排序有一种线性结构的感觉,再加上移动是 $O(1)$ 那就是链表了。
能够将使用过的移到最新,原本最新的变成第二新(next),满的时候将最后使用的删除,第二旧的 (pre) 变成最旧,那就可以是一个双向链表。然后一头一尾,链表不仅需要 head 还需要 tail 。大概结构就出来了。

分解操作:
get(String key)

- map `get` ,不存在返回 -1
- 存在,获取节点,将节点从原位置删除(linkedlist delete),再移动到 head

put(String key, int value)

- get(String key) (此时作用就是移动缓存,若存在更新就 value)
- 不存在
    - check map size ,大于容量,删除 tail 
    - 新建节点 node ,put 到 map ,并将 node 作为 head 加入链表

代码:

public class LRUCache {
private Map<Integer, Node> map;
private Node head;
private Node tail;
private int capacity;
public LRUCache(int capacity) {
this.map = new HashMap<>();
this.head = null;
this.tail = null;
this.capacity = capacity;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
Node node = map.get(key);
deleteNode(node);
addFirst(node);
return node.value;
}
public void put(int key, int value) {
if (get(key) != -1) {
map.get(key).value = value;
} else {
if (map.size() == capacity) {
map.remove(deleteLast());
}
Node node = new Node(key, value);
map.put(key, node);
addFirst(node);
}
}
class Node {
private int key;
private int value;
private Node pre;
private Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
this.pre = null;
this.next = null;
}
}
private void addFirst(Node node) {
if (head == null) {
head = node;
tail = node;
} else {
head.pre = node;
node.next = head;
head = node;
}
}
private void deleteFirst() {
if (head == null) {
return;
}
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
head.pre.next = null;
head.pre = null;
}
}
private int deleteLast() {
if (tail == null) {
return -1;
}
int lastKey = tail.key;
if (head == tail) {
deleteFirst();
} else {
tail = tail.pre;
tail.next.pre = null;
tail.next = null;
}
return lastKey;
}
private void deleteNode(Node node) {
if (node == head) {
deleteFirst();
} else if (node == tail) {
deleteLast();
} else {
node.pre.next = node.next;
node.next.pre = node.pre;
node.pre = null;
node.next = null;
}
}
}