LRU缓存机制

[编程题]LRU缓存机制

热度指数：320 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

设计和实现一个 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。按照访问时间或者插入时间，越早的越先输出。

示例1

输入

2
put 1 1
put 2 2
get 1
put 3 3
get 1

输出

3 3
1 1

算法知识视频讲解

王答

使用链表存储数据，每次get数据时，将key移到链表表头。

发表于 2020-06-27 23:07:03 回复(1)

Java

菲尼克斯弗兰克

读取未知行数的时候，不是回车结尾会出现错误，使用br的ready方法在就绪后计算时间的差值跳出读取的循环才行

发表于 2022-08-18 12:21:51 回复(0)

快手-主站技术部

#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;
}

发表于 2020-06-22 11:48:35 回复(0)

ADPX丶

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;
        }
    }
}

发表于 2020-05-30 00:24:13 回复(0)

已注销

发表于 2020-05-07 11:48:45 回复(0)

C/C++

WindedMan

#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;
}

发表于 2020-05-04 11:30:07 回复(0)