首页 > 试题广场 >

LRU缓存

[编程题]LRU缓存
  • 热度指数：399 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：
获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回-1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
要求get和put都为O(1)的时间复杂度。

输入描述:
第一行是两个整数N,M。代表共有N次操作，缓存容量为M，用空格分隔。

第2~n+1行是n次操作，格式为"PUT x y"或"GET x"。x和y为题面所要求的数字。


输出描述:
对于每个GET操作，输出一行数字作为结果。
示例1

输入

9 2
PUT 1 1
PUT 2 2
GET 1
PUT 3 3
GET 2
PUT 4 4
GET 1
GET 3
GET 4

输出

1
-1
-1
3
4

说明

PUT 1 1
PUT 2 2
GET 1        // 输出1
PUT 3 3     // 密钥2失效
GET 2        // 未找到
PUT 4 4     // 密钥1失效
GET 1        // 未找到
GET 3        // 输出3
GET 4        // 输出4

备注:
x和y都是正整数，1<=n<=1e5，1<=m<=1e5
算法知识视频讲解
添加回答
21CenturyBoy头像 21CenturyBoy 
//双向链表加map，中间很多链表操作可以抽取出来成一个方法，机试可以直接用java 的linkedHashmap

import java.util.*;
 
public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int capcity = input.nextInt();
        input.nextLine();
        LRU lru = new LRU(capcity);
        String[] ans =new String[n];
        for(int i=0;i<n;i++){
            ans[i] = input.nextLine();
        }
        for(String s:ans){
            String[] strings = s.split(" ");
            if(strings.length==2){
                System.out.println(lru.get(Integer.valueOf(strings[1])));
            }else {
                lru.put(Integer.valueOf(strings[1]),Integer.valueOf(strings[2]));
            }
        }
    }
}
class LRU{
    Node head;
    Node tail;
    HashMap<Integer,Node> map;
    int size;
    int count;
    public LRU(int capcity){
        map = new HashMap<>();
        head = new Node(-1,0);
        tail = new Node(-2,0);
        head.next = tail;
        tail.pre = head;
        size = capcity;
        count = 0;
    }
    public int get(int key){
        if(!map.containsKey(key))return -1;
        Node node = map.get(key);
        int value = node.val;
        Node pre = node.pre;
        Node next = node.next;
        pre.next = next;
        next.pre = pre;
        Node h = head.next;
        head.next = node;
        node.pre = head;
        node.next = h;
        h.pre = node;
        return value;
    }
    public void put(int key,int value){
        if(map.containsKey(key)){
            Node node = map.get(key);
            node.val = value;
            Node pre = node.pre;
            Node next = node.next;
            pre.next = next;
            next.pre = pre;
            Node h = head.next;
            head.next = node;
            node.pre = head;
            node.next = h;
            h.pre = node;
        }else {
            Node node = new Node(key,value);
            map.put(key,node);
            Node h = head.next;
            head.next = node;
            node.pre = head;
            node.next = h;
            h.pre = node;
            count++;
            if(count>size){
                removeLast();
                count--;
            }
        }
    }
    public void removeLast(){
        Node last = tail.pre;
        map.remove(last.key);
        Node pre = last.pre;
        pre.next = tail;
        tail.pre = pre;
 
    }
    static class Node{
        int key;
        int val;
        Node pre;
        Node next;
        public Node(int k,int v){
            val = v;
            key = k;
        }
    }
}

发表于 2020-06-21 18:56:26 回复(0)
Java
空山新雨_后头像 空山新雨_后 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int capacity = scanner.nextInt();
        String[] commands = new String[n];
        LRUCache lru = new LRUCache(capacity);
        //因为第一行输入的命令和第二行输入的命令是换行的
        //所以我们要多加一个nextLine()去吸收那个空格
        scanner.nextLine();
        for(int i = 0; i < n; i++){
            commands[i] = scanner.nextLine();
        }
        
        for(String command : commands){
            String[] s = command.split(" ");
            if(s.length == 2){
                System.out.println(lru.get(Integer.parseInt(s[1])));
            }
            else{
                lru.put(Integer.parseInt(s[1]),Integer.parseInt(s[2]));
            }
        }                
    }
}

class LRUCache{
    
    static class BinaryListNode{
        int key;
        int val;
        BinaryListNode next;
        BinaryListNode prev;
        BinaryListNode(){}
        BinaryListNode(int key, int val){this.key = key; this.val = val;}
    }
    
    private int size;
    private int capacity;
    private BinaryListNode dummyHead;
    private BinaryListNode dummyTail;
    private Map<Integer, BinaryListNode> cache = new HashMap<>();
    
    public LRUCache(int capacity){
        this.size = 0;
        this.capacity = capacity;
        dummyHead = new BinaryListNode();
        dummyTail = new BinaryListNode();
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }
    
    public int get(int key){
        if(!cache.containsKey(key)){
            return -1;
        }
        BinaryListNode node = cache.get(key);
        removeToHead(node);
        return node.val;
    }
    
    public void put(int key, int value){
        if(!cache.containsKey(key)){
            BinaryListNode newNode = new BinaryListNode(key,value);
            cache.put(key,newNode);
            addToHead(newNode);
            size++;
            if(size > capacity){
                BinaryListNode node = removeTail();
                cache.remove(node.key);
                size--;
            }
        }
        else{
            BinaryListNode node = cache.get(key);
            node.val = value;
            removeToHead(node);
        }
    }
    
    public void addToHead(BinaryListNode node){
        node.next = dummyHead.next;
        node.prev = dummyHead;
        dummyHead.next.prev = node;
        dummyHead.next = node;
    }
    
    public void removeNode(BinaryListNode node){
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }
    
    public void removeToHead(BinaryListNode node){
        removeNode(node);
        addToHead(node);
    }
    
    public BinaryListNode removeTail(){
        BinaryListNode tail = dummyTail.prev;
        removeNode(tail);
        return tail;
    }    
}

编辑于 2021-07-23 14:21:20 回复(0)
求个offer阿头像 求个offer阿
#include<iostream>
#include<unordered_map>
#include<list>
using namespace std;
struct Node
{
    int value;
    list<int>::iterator iter;
    Node(int v,list<int>::iterator it):value(v),iter(it){}
};
class LRU{
   private :
    int LRU_m;
    list<int> m_l;
    unordered_map<int,Node> m_hash;
    public:
    LRU(int m)
    {
        LRU_m=m;
        //cout<<"LRU栈大小为："<<m<<endl;
    }    
    int GET(int key)
    {
        unordered_map<int,Node>::iterator iter=m_hash.find(key);
        if(iter!=m_hash.end())
        {
            m_l.splice(m_l.begin(),m_l,iter->second.iter);
            return iter->second.value;
        }
        return -1;
    }
    void PUT(int key,int value)
    {
        unordered_map<int,Node>::iterator iter=m_hash.find(key);
        if(iter!=m_hash.end())
        {
            m_l.splice(m_l.begin(),m_l,iter->second.iter);
            iter->second.value=value;
        }
        else{
            if(m_hash.size()==LRU_m)
            {
                m_hash.erase(m_l.back());
                m_l.pop_back();
            }
            m_l.insert(m_l.begin(),key);
            Node n(value,m_l.begin());
            m_hash.insert(pair<int,Node>(key,n));
        }
        
    }
};
int main()
{
    int n,m;
    cin>>n>>m;
    LRU l=LRU(m);
    
    int key,value;
    for(int i=0;i<n;i++)
    {
        string c;
        cin>>c;
        if(c=="GET")
        {
            cin>>key;
            cout<<l.GET(key)<<endl;
        }
       else if(c=="PUT")
        {
            cin>>key>>value;
             l.PUT(key, value);
        }
    }
    return 0;
}
发表于 2020-06-29 16:51:34 回复(0)
Java
是瑶瑶公主呀头像 是瑶瑶公主呀 
import java.util.*;
public class Main {

    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        String line = input.nextLine();
        String[] nums = line.split(" ");
        int N=Integer.parseInt(nums[0]);
        int M=Integer.parseInt(nums[1]);
        LRUCache cache = new LRUCache(M);
        for(int i=0;i<N;i++){
            String str=input.nextLine();
            String[] s = str.split(" ");
            if(str.startsWith("PUT")){
                cache.put(Integer.parseInt(s[1]),Integer.parseInt(s[2]));
            }else {
                System.out.println(cache.get(Integer.parseInt(s[1])));
            }
        }
    }

    static class LRUCache extends LinkedHashMap<Integer,Integer>{
        private int capacity;

        public LRUCache(int capacity) {
            //第三个参数代表可以按访问元素的顺序排序
            super(capacity,0.75F,true);
            this.capacity=capacity;
        }


        public int get(int key) {
            return super.getOrDefault(key,-1);
        }


        public void put(int key, int value) {
            super.put(key,value);
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > capacity;
        }
    }

}
发表于 2020-03-21 13:42:12 回复(0)
提交观点

问题信息

第四范式 2020 Java工程师
上传者：小小
难度：
4条回答 2942浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号