运用所掌握的数据结构,设计和实现一个 LRU (Least Recently Used,最近最少使用) 缓存机制 。
实现 LRUCache 类:
示例:
输入
["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
提示:
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put
进阶:是否可以在 O(1) 时间复杂度内完成这两种操作?
为什么使用双向链表?因为如果使用数组,最近使用的节点移到头部,时间复杂度为O(N);而使用链表,可以降到O(1)
为什么使用哈希表?因为链表的查找时间复杂度为O(N),使用哈希表,在不发生哈希冲突的情况下可以降到O(1)
- class LRUCache {
-
- //自定义双向链表
- class Entry {
- int key;
- int value;
- Entry prev;
- Entry next;
- public Entry() {}
- public Entry(int key, int value){
- this.key = key;
- this.value = value;
- }
- }
-
- Entry head, tair; //头、尾结点
- int capacity; //容量
- int size; //当前大小
- Map
cache; //HashMap -
- public LRUCache(int capacity) {
- this.capacity = capacity;
- //初始化双向链表
- initLinkedList();
- size = 0;
- cache = new HashMap<>(capacity+2);
- }
-
- /**
- 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1
- */
- public int get(int key) {
- Entry node = cache.get(key);
- if(node == null) {
- return -1;
- }
- moveToHead(node);
- return node.value;
- }
-
- /**
- 如果key存在,替换掉,再移到最前面
- 如果key不存在,
- 如果缓存容量达到上限,先删尾结点,再头插
- 如果缓存容量未达上限,头插
- */
- public void put(int key, int value) {
- Entry node = cache.get(key);
- //如果key位置上存在节点
- if(node != null) {
- node.value = value;
- moveToHead(node);
- return;
- }
-
- //如果不存在
- //如果entry已满,删除最后一个节点
- if(size == capacity) {
- Entry lastNode = tair.prev;
- deleteNode(lastNode);
- cache.remove(lastNode.key);
- size--;
- }
-
- //把当前节点头插
- Entry newNode = new Entry();
- newNode.key = key;
- newNode.value = value;
- addNode(newNode);
- cache.put(key, newNode);
- size++;
- }
-
- /**
- 初始化双向链表
- */
- private void initLinkedList() {
- head = new Entry();
- tair = new Entry();
- head.next = tair;
- tair.prev = head;
- }
-
- /**
- 将当前节点移到最前面(头结点之后)
- */
- private void moveToHead(Entry node) {
- //首先删除原来节点关系
- deleteNode(node);
- addNode(node);
- }
-
- /**
- 删除当前节点
- */
- private void deleteNode(Entry node) {
- node.prev.next = node.next;
- node.next.prev = node.prev;
- }
-
- /**
- 头插
- */
- private void addNode(Entry node) {
- head.next.prev = node;
- node.next = head.next;
-
- node.prev = head;
- head.next = node;
- }
- }
-
- /**
- * 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);
- */