设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。第一行输入缓存容量,包含一个整数N,1≤N≤10。
接下来,每一行是一个put或者get的操作。若输入一个get + 一个数字,则代表get操作和指定的key;若输入一个put + 两个数字,则代表put操作后面为key和value,进行put操作。读到文件结束
输出多行,每一行两个数字表示 缓存中的key 和value。按照访问时间或者插入时间,越早的越先输出。
2 put 1 1 put 2 2 get 1 put 3 3 get 1
3 3 1 1
#include <vector>
#include <iostream>
#include <list>
#include <unordered_map>
using namespace std;
class LRUCache{
struct Node{
int key;
int value;
Node(int k, int v):key(k), value(v){};
};
public:
LRUCache(int c): capacity(c){};
LRUCache(){};
void put(int key, int value)
{
if(m.find(key)==m.end())
{
if(cachelist.size()>=capacity)
{
m.erase(cachelist.back().key);
cachelist.pop_back();
}
cachelist.push_front(Node(key, value));
m[key] = cachelist.begin();
}
else
{
m[key]->value = value;
cachelist.splice(cachelist.begin(), cachelist, m[key]);
m[key] = cachelist.begin();
}
}
int get(int key)
{
if(m.find(key)!=m.end())
{
int res = m[key]->value;
cachelist.splice(cachelist.begin(), cachelist, m[key]);
m[key] = cachelist.begin();
return res;
}
else
{
return -1;
}
}
list<Node> cachelist;
private:
int capacity;
unordered_map<int, list<Node>::iterator> m;
};
int main()
{
int N;
cin >> N;
LRUCache* lru = new LRUCache(N);
string s;
int a;
int b;
while(cin>>s)
{
if(s=="put")
{
cin >> a >> b;
lru->put(a, b);
}
else if(s=="get")
{
cin >> a;
lru->get(a);
}
}
while(!lru->cachelist.empty())
{
cout << lru->cachelist.back().key << " "<< lru->cachelist.back().value << endl;
lru->cachelist.pop_back();
}
return 0;
}
import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int capatity = sc.nextInt(); LRUCache lru = new LRUCache(capatity); while(sc.hasNextLine()){ String[] ss = sc.nextLine().split(" "); if(ss.length == 3){ int key = Integer.parseInt(ss[1]); int value = Integer.parseInt(ss[2]); lru.put(key,value); } else if(ss.length == 2) { int key = Integer.parseInt(ss[1]); lru.get(key); } } lru.print(); } } class LRUCache { private Map<Integer,Node> map; private Node head; private Node tail; private final int capacity; public LRUCache(int capacity){ this.capacity = capacity; map = new HashMap<>(); } public void put(int key, int value){ Node node = map.get(key); if(node != null){ node.value = value; remove(node); } else { node = new Node(key, value); if(map.size() >= capacity) remove(tail); } addToHead(node); } private void remove(Node node) { if(node == head) head = head.next; if(node == tail) tail = tail.pre; if(node.next != null) node.next.pre = node.pre; if(node.pre != null) node.pre.next = node.next; node.next = null; node.pre = null; map.remove(node.key); } private void addToHead(Node node) { if(head == null) head = tail = node; else { node.next = head; head.pre = node; head = node; } map.put(node.key,node); } public int get(int key){ Node node = map.get(key); if(node == null) return -1; remove(node); addToHead(node); return node.value; } public void print(){ Node p = tail; while(p != null){ System.out.println(p.key + " " + p.value); p = p.pre; } } private class Node{ int key; int value; Node pre; Node next; Node(int key,int value){ this.key = key; this.value = value; } } }
#include<bits/stdc++.h> using namespace std; void get(int key,unordered_map<int,int>&hash,list<int>&l){ if(hash.find(key)==hash.end())return ; for(auto it=l.begin();it!=l.end();it++){ if(*it==key){ l.erase(it); break; } } l.push_back(key); //return hash[key]; } void put(int key,int value,unordered_map<int,int>&hash,list<int>&l,int N){ if(hash.find(key)!=hash.end()){ for(auto it=l.begin();it!=l.end();it++){ if(*it==key){ l.erase(it); break; } } } l.push_back(key); hash[key]=value; if(l.size()>N){ hash.erase(*l.begin()); l.pop_front(); } } int main(){ int N; cin>>N; unordered_map<int,int>hash; list<int>l; string s; int a,b; while(cin>>s){ if(s=="put"){ cin>>a>>b; put(a,b,hash,l,N); }else if(s=="get"){ cin>>a; get(a,hash,l); } } for(auto it=l.begin();it!=l.end();it++){ cout<<(*it)<<" "<<hash[(*it)]<<endl; } return 0; }