运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。实现 LRUCache 类
https://leetcode-cn.com/problems/lru-cache/
- LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
- int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
- void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。
- 当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例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
提示：
1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <= 104
最多调用 3 * 10^4 次 get 和 put
Java解法
思路：
最简单的想法就是利用双端队列进行存储存入顺序，利用hashMap进行缓存存储
在存放时，key从栈顶入栈，如存在，更新位置；如溢出，利用队列移除队尾
在取出时：如存在，更新位置；调试修改之后是可用工作的，但效率不高超时了，用来复习下栈、队列操作
static class LRUCache { private final int size; HashMap<Integer, Integer> mMap; Deque<Integer> mDeque; public LRUCache(int capacity) { size = capacity; mMap = new HashMap<>(); mDeque = new ArrayDeque<>(); } public int get(int key) { if (mDeque.contains(key)) { refreshKeyOrder(key); } Integer integer = mMap.getOrDefault(key, -1); System.out.println("结果=="+integer); return integer; } public void put(int key, int value) { mMap.put(key, value); refreshKeyOrder(key); log(); } private void refreshKeyOrder(int key) { if (mDeque.contains(key)) { //栈：头部进入，头部取出 //更新使用栈的方法更新 Stack<Integer> stack = new Stack<>(); while (!mDeque.isEmpty()) { Integer pop = mDeque.pop(); if (pop != null) { if (pop == key) { while (!stack.isEmpty()) { mDeque.push(stack.pop()); } mDeque.push(pop); break; } else { stack.push(pop); } } } } else { if (mDeque.size() >= size) { //队列：队尾插入，队头取出 //溢出使用队列的方法取出队尾 Integer pop = mDeque.pollLast();//移除，也就是队尾 mMap.remove(pop); } mDeque.push(key); } } public void log() { Deque<Integer> integerDeque = new ArrayDeque<>(); while (!mDeque.isEmpty()) { Integer poll = mDeque.poll(); System.out.print(poll + "=" + mMap.getOrDefault(poll, -1)+";"); integerDeque.offer(poll); } System.out.println(); mDeque = integerDeque; } }优化计算，直接用链表存储顺序，并迁移
package sj.shimmer.algorithm.m4_2021;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
/**
* Created by SJ on 2021/4/8.
*/
class D71 {
public static void main(String[] args) {
// LRUCache lRUCache = new LRUCache(2);
// lRUCache.put(1, 1); // 缓存是 {1=1}
// lRUCache.log();
// lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
// lRUCache.log();
// lRUCache.get(1); // 返回 1
// lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
// lRUCache.log();
// lRUCache.get(2); // 返回 -1 (未找到)
// lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
// lRUCache.log();
// lRUCache.get(1); // 返回 -1 (未找到)
// lRUCache.get(3); // 返回 3
// lRUCache.get(4); // 返回 4
String[] operation = { "LRUCache", "put", "put", "put", "put", "put", "get", "put", "get", "get", "put", "get", "put", "put", "put", "get", "put", "get", "get", "get", "get", "put", "put", "get", "get", "get", "put", "put", "get", "put", "get", "put", "get", "get", "get", "put", "put", "put", "get", "put", "get", "get", "put", "put", "get", "put", "put", "put", "put", "get", "put", "put", "get", "put", "put", "get", "put", "put", "put", "put", "put", "get", "put", "put", "get", "put", "get", "get", "get", "put", "get", "get", "put", "put", "put", "put", "get", "put", "put", "put", "put", "get", "get", "get", "put", "put", "put", "get", "put", "put", "put", "get", "put", "put", "put", "get", "get", "get", "put", "put", "put", "put", "get", "put", "put", "put", "put", "put", "put", "put" } ;
int[][] num = new int[][]{{10}, {10, 13}, {3, 17}, {6, 11}, {10, 5}, {9, 10}, {13}, {2, 19}, {2}, {3}, {5, 25}, {8}, {9, 22}, {5, 5}, {1, 30}, {11}, {9, 12}, {7}, {5}, {8}, {9}, {4, 30}, {9, 3}, {9}, {10}, {10}, {6, 14}, {3, 1}, {3}, {10, 11}, {8}, {2, 14}, {1}, {5}, {4}, {11, 4}, {12, 24}, {5, 18}, {13}, {7, 23}, {8}, {12}, {3, 27}, {2, 12}, {5}, {2, 9}, {13, 4}, {8, 18}, {1, 7}, {6}, {9, 29}, {8, 21}, {5}, {6, 30}, {1, 12}, {10}, {4, 15}, {7, 22}, {11, 26}, {8, 17}, {9, 29}, {5}, {3, 4}, {11, 30}, {12}, {4, 29}, {3}, {9}, {6}, {3, 4}, {1}, {10}, {3, 29}, {10, 28}, {1, 20}, {11, 13}, {3}, {3, 12}, {3, 8}, {10, 9}, {3, 26}, {8}, {7}, {5}, {13, 17}, {2, 27}, {11, 15}, {12}, {9, 19}, {2, 15}, {3, 16}, {1}, {12, 17}, {9, 1}, {6, 19}, {4}, {5}, {5}, {8, 1}, {11, 7}, {5, 2}, {9, 28}, {1}, {2, 2}, {7, 4}, {4, 22}, {7, 24}, {9, 26}, {13, 28}, {11, 26}};
createLru(operation, num);
}
private static void createLru(String[] operation, int[][] num) {
LRUCache lRUCache = new LRUCache(1);
for (int i = 0; i < operation.length; i++) {
switch (operation[i]){
case "LRUCache" :
lRUCache = new LRUCache(num[i][0]);
break;
case "put":
lRUCache.put(num[i][0],num[i][1]);
break;
case "get":
lRUCache.get(num[i][0]);
break;
default:
break;
}
}
}
static class LRUCache {
private final int size;
HashMap<Integer, Integer> mMap;
List<Integer> orderList;
public LRUCache(int capacity) {
size = capacity;
mMap = new HashMap<>();
orderList = new ArrayList<>();
}
public int get(int key) {
if (orderList.indexOf(key)!=-1) {
refreshKeyOrder(key);
}
return mMap.getOrDefault(key, -1);
}
public void put(int key, int value) {
mMap.put(key, value);
refreshKeyOrder(key);
}
private void refreshKeyOrder(int key) {
int index = orderList.indexOf(key);
if (index ==-1) {
if (orderList.size()>=size) {
Integer remove = orderList.remove(size - 1);
mMap.remove(remove);
}
}else {
orderList.remove(index);
}
orderList.add(0, key);
}
}
}
image
官方解
https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/
-
哈希表 + 双向链表
提交解用了链表，没有在链表这块进行查找优化，直接用了系统API的indexof，实际上就是O(n)的遍历
官方解O(1)时间是通过哈希表来完成的，hash计算能快速定位位置，但不是绝对的O(1)
put和get的操作通过哈希表能快速定位，但双向链表不支持随机访问的，定位到实际上还是需要时间的
认识不够，只觉得这个解法好优秀、但不是很满足O(1)要求
时间复杂度：O(1)
空间复杂度：O(capacity)
