设计LRU缓存结构,该结构在构造时确定大小,假设大小为K,并有如下两个功能
- set(key, value):将记录(key, value)插入该结构
- get(key):返回key对应的value值
- set和get方法的时间复杂度为O(1)
- 某个key的set或get操作一旦发生,认为这个key的记录成了最常使用的。
- 当缓存的大小超过K时,移除最不经常使用的记录,即set或get最久远的。
第一行两个个整数N, K,表示操作数量以及缓存结构大小
接下来N行,第一行一个整数opt表示操作类型。
若opt=1,接下来两个整数x, y,表示set(x, y)
若opt=2,接下来一个整数x,表示get(x),若x未出现过或已被移除,则返回-1
对于每个操作2,输出一个答案
6 3 1 1 1 1 2 2 1 3 2 2 1 1 4 4 2 2
1 -1
第一次操作后:最常使用的记录为("1", 1)
第二次操作后:最常使用的记录为("2", 2),("1", 1)变为最不常用的
第三次操作后:最常使用的记录为("3", 2),("1", 1)还是最不常用的
第四次操作后:最常用的记录为("1", 1),("2", 2)变为最不常用的
第五次操作后:大小超过了3,所以移除此时最不常使用的记录("2", 2),加入记录("4", 4),并且为最常使用的记录,然后("3", 2)变为最不常使用的记录
#include <bits/stdc++.h> using namespace std; struct P{ int k, v; }; class LRU{ public: int K; list<P> cache; unordered_map<int, list<P>::iterator> M; LRU(int k){ K = k; } int get(int k){ if(M.find(k) == M.end()) return -1; P p = *M[k]; cache.erase(M[k]); cache.push_front(p); return p.v; } void put(int k, int v){ if(M.find(k) == M.end()){ if(cache.size() == K){ P p = cache.back(); M.erase(p.k); cache.pop_back(); } cache.push_front(P{k,v}); M[k] = cache.begin(); }else{ cache.erase(M[k]); cache.push_front(P{k,v}); M[k] = cache.begin(); } } }; int main(){ int n, k, opt, x, y; scanf("%d%d", &n, &k); LRU lru(k); for(int i=0;i<n;i++){ scanf("%d", &opt); if(opt==1){ scanf("%d%d", &x, &y); lru.put(x, y); }else if(opt==2){ scanf("%d", &x); printf("%d\n", lru.get(x)); } } return 0; }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.LinkedHashMap; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] params = br.readLine().split(" "); int n = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]); LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(); StringBuilder sb = new StringBuilder(); for(int i = 0; i < n; i++){ params = br.readLine().split(" "); int opt = Integer.parseInt(params[0]), x = Integer.parseInt(params[1]); if(opt == 1){ int y = Integer.parseInt(params[2]); if(map.size() < k){ if(map.containsKey(x)) map.remove(x); // 重新设置过,也要将设置的key在链表中调到末尾 }else{ // 把最老的key删除 int firstKey = map.keySet().iterator().next(); map.remove(firstKey); } map.put(x, y); }else{ if(!map.containsKey(x)){ sb.append(-1 + "\n"); }else{ sb.append(map.get(x) + "\n"); // 将这个键值对改为最新使用,追加到链表的最后 int y = map.get(x); map.remove(x); map.put(x, y); } } } System.out.println(sb.toString().trim()); } }
如果有新的元素加入,则往双向链表的尾节点中插入;
如果删除最近最少的节点,则删除双向链表的头节点。
为了方便操作双向链表,我们设置了2个头尾的哑节点dummyHead和dummyTail。
import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { private int capacity; // LRU最大容量 private Map<Integer, Node> map = new HashMap<>(); // 映射表用于获取元素 private Node dummyHead = new Node(0, 0); // 哑节点(头) private Node dummyTail = new Node(0, 0); // 哑节点(尾) /** * LRU的节点是一个双向链表中的一个节点 */ class Node { int key; int value; Node prev; Node next; public Node(int key, int value) { this.key = key; this.value = value; } } /** * 初始化最大容量 * @param capacity LRU最大容量 */ public Main(int capacity) { this.capacity = capacity; dummyHead.next = dummyTail; dummyTail.prev = dummyHead; } /** * 往LRU中添加元素 * @param key * @param value */ public void set(int key, int value) { // 如果映射表已包含该key,则要从中删除 if (map.containsKey(key)) { remove(map.get(key)); } // 如果当前元素数量已经达到最大值,要删除LRU的头节点 if (map.size() == capacity) { remove(dummyHead.next); } Node node = new Node(key, value); add(node); } /** * 从LRU中查数据 * @param key * @return */ public int get(int key) { // 如果映射表中包含该key,则要先从LRU中删除该节点,再将该节点插入到LRU尾部 if (map.containsKey(key)) { Node node = map.get(key); remove(node); add(node); return node.value; } return -1; } /** * 删除一个节点 * @param node */ public void remove(Node node) { map.remove(node.key); node.next.prev = node.prev; node.prev.next = node.next; } /** * 添加一个节点 * @param node */ public void add(Node node) { map.put(node.key, node); node.next = dummyTail; node.prev = dummyTail.prev; dummyTail.prev = node; node.prev.next = node; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); Main lruCache = new Main(k); while (n-- > 0) { int operation = sc.nextInt(); if (operation == 1) { int key = sc.nextInt(); int value = sc.nextInt(); lruCache.set(key, value); } else if (operation == 2) { int value = sc.nextInt(); System.out.println(lruCache.get(value)); } } } }