Leetcode-146. LRU Cache
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity) Initialize the LRU cache with positive size capacity. int get(int key) Return the value of the key if the key exists, otherwise return -1. void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key. The functions get and put must each run in O(1) average time complexity.
Example 1:
Input [“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] Output [null, null, null, 1, null, -1, null, -1, 3, 4]
Explanation LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // cache is {1=1} lRUCache.put(2, 2); // cache is {1=1, 2=2} lRUCache.get(1); // return 1 lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3} lRUCache.get(2); // returns -1 (not found) lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3} lRUCache.get(1); // return -1 (not found) lRUCache.get(3); // return 3 lRUCache.get(4); // return 4
<解題>
class LRUCache {
class Node {
int key;
int value;
Node pre;
Node next;
public Node(int key, int value){
this.key = key;
this.value = value;
}
}
private HashMap<Integer, Node> map = new HashMap<>();
private int capacity;
//頭部->最老的元素
private Node head;
//尾部->最新的元素
private Node tail;
public LRUCache(int capacity) {
this.capacity = capacity;
head = null;
tail = null;
}
public int get(int key) {
Node node = map.get(key);
if(node == null){
return -1;
}
//如果node是最新元素，直接返回
if(node != tail) {
//如果node是head，需要把它移到末尾
if(node == head){
head = head.next;
} else {
node.pre.next = node.next;
node.next.pre = node.pre;
}
//把取出的node放到最後
tail.next = node;
node.pre = tail;
node.next = null;
tail = node;
}
return node.value;
}
public void put(int key, int value) {
Node node = map.get(key);
//已經存在這個node，只需要更新node的值
if(node != null){
node.value = value;
if(node != tail){
if(node == head){
head = head.next;
} else {
node.pre.next = node.next;
node.next.pre = node.pre;
}
tail.next = node;
node.pre = tail;
node.next = null;
tail = node;
}
} else {
//需要插入新的節點
Node newNode = new Node(key, value);
if(capacity == 0){
Node temp = head;
//把舊的head刪掉
head = head.next;
//如果刪除後鏈表為空，也要更新tail
if (head == null) {
tail = null;
}
//map中也要刪除
map.remove(temp.key);
capacity++;
}
//如果是鏈表中的第一個點
if(head == null && tail == null){
head = newNode;
} else {
tail.next = newNode;
newNode.pre = tail;
newNode.next = null;
}
tail = newNode;
map.put(key, newNode);
//減少一個容量
capacity--;
}
}
}
/**
* 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);
*/
Time: O(1) Space: O(n)