146.LRU缓存

题目：

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

LCR 031. LRU 缓存 - 力扣（LeetCode）

题解：

思路：

用一个哈希表和一个双端队列，队列里面存储key，哈希存value。get时把对应的key删除，放在队首。put时有旧的则删掉，size够了把队列的最后一个删掉。然后加入，并且覆盖哈希表里面的值。

代码：

java">class LRUCache {private int capacity;private Map<Integer,Integer> cache;private Deque<Integer> queue;public LRUCache(int capacity) {this.capacity=capacity;this.cache=new HashMap<>();this.queue=new LinkedList<>();}public int get(int key) {if(cache.containsKey(key)){queue.remove(key);queue.offerFirst(key);return cache.get(key);}return -1;}public void put(int y, int value) {if(cache.containsKey(y)){queue.remove(y);}if(queue.size()==capacity){Integer oldKey=queue.pollLast();cache.remove(oldKey);}cache.put(y,value);queue.offerFirst(y);}
}

java">class Node {int data;Node next;Node prev;Node(int data) {this.data = data;}
}class MyDeque {private Node front;private Node rear;private int size;public MyDeque() {front = null;rear = null;size = 0;}// 向队列前端添加元素public void offerFirst(int data) {Node newNode = new Node(data);if (isEmpty()) {front = newNode;rear = newNode;} else {newNode.next = front;front.prev = newNode;front = newNode;}size++;}// 移除指定元素public void remove(int key) {Node current = front;while (current != null) {if (current.data == key) {if (current == front) {pollFirst();} else if (current == rear) {pollLast();} else {current.prev.next = current.next;current.next.prev = current.prev;size--;}return;}current = current.next;}return;}// 从队列尾部移除元素public int pollLast() {if (isEmpty()) {return -1;}int removedData = rear.data;if (size == 1) {front = null;rear = null;} else {rear = rear.prev;rear.next = null;}size--;return removedData;}// 从队列前端移除元素public int pollFirst() {if (isEmpty()) {return -1;}int removedData = front.data;if (size == 1) {front = null;rear = null;} else {front = front.next;front.prev = null;}size--;return removedData;}// 判断队列是否为空public boolean isEmpty() {return size == 0;}// 获取队列大小public int size() {return size;}}

完整的双端队列：

java">class Node {int data;Node next;Node prev;Node(int data) {this.data = data;}
}public class MyDeque {private Node front;private Node rear;private int size;public MyDeque() {front = null;rear = null;size = 0;}// 向队列前端添加元素public void addFirst(int data) {Node newNode = new Node(data);if (isEmpty()) {front = newNode;rear = newNode;} else {newNode.next = front;front.prev = newNode;front = newNode;}size++;}// 向队列尾部添加元素public void addLast(int data) {Node newNode = new Node(data);if (isEmpty()) {front = newNode;rear = newNode;} else {rear.next = newNode;newNode.prev = rear;rear = newNode;}size++;}// 从队列前端移除元素public int removeFirst() {if (isEmpty()) {throw new IllegalStateException("队列为空");}int removedData = front.data;if (size == 1) {front = null;rear = null;} else {front = front.next;front.prev = null;}size--;return removedData;}// 从队列尾部移除元素public int removeLast() {if (isEmpty()) {throw new IllegalStateException("队列为空");}int removedData = rear.data;if (size == 1) {front = null;rear = null;} else {rear = rear.prev;rear.next = null;}size--;return removedData;}// 移除指定元素public void remove(int key) {Node current = front;while (current != null) {if (current.data == key) {if (current == front) {removeFirst();} else if (current == rear) {removeLast();} else {current.prev.next = current.next;current.next.prev = current.prev;size--;}return;}current = current.next;}throw new IllegalArgumentException("队列中没有该元素");}// 获取队列前端元素public int getFirst() {if (isEmpty()) {throw new IllegalStateException("队列为空");}return front.data;}// 获取队列尾部元素public int getLast() {if (isEmpty()) {throw new IllegalStateException("队列为空");}return rear.data;}// 判断队列是否为空public boolean isEmpty() {return size == 0;}// 获取队列大小public int size() {return size;}}