首页 > 试题广场 >

设计LRU缓存结构

[编程题]设计LRU缓存结构

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

设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 k ，操作次数是 n ，并有如下两个功能

1. set(key, value)：将记录(key, value)插入该结构

2. get(key)：返回key对应的value值

提示:

1.某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的，然后都会刷新缓存。

2.当缓存的大小超过k时，移除最不经常使用的记录。

3.输入一个二维数组与k，二维数组每一维有2个或者3个数字，第1个数字为opt，第2，3个数字为key，value

若opt=1，接下来两个整数key, value，表示set(key, value)
若opt=2，接下来一个整数key，表示get(key)，若key未出现过或已被移除，则返回-1
对于每个opt=2，输出一个答案

4.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹

要求：set和get操作复杂度均为 $O(1)$

数据范围： $1 \le k \le n \le 10^5 \$ ， $|key|,|val| \le 2\times 10^9 \$

示例1

输入

[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3

输出

[1,-1]

说明

[1,1,1]，第一个1表示opt=1，要set(1,1)，即将(1,1)插入缓存，缓存是{"1"=1}
[1,2,2]，第一个1表示opt=1，要set(2,2)，即将(2,2)插入缓存，缓存是{"1"=1,"2"=2}
[1,3,2]，第一个1表示opt=1，要set(3,2)，即将(3,2)插入缓存，缓存是{"1"=1,"2"=2,"3"=2}
[2,1]，第一个2表示opt=2，要get(1)，返回是[1]，因为get(1)操作，缓存更新，缓存是{"2"=2,"3"=2,"1"=1}
[1,4,4]，第一个1表示opt=1，要set(4,4)，即将(4,4)插入缓存，但是缓存已经达到最大容量3，移除最不经常使用的{"2"=2}，插入{"4"=4}，缓存是{"3"=2,"1"=1,"4"=4}
[2,2]，第一个2表示opt=2，要get(2)，查找不到，返回是[1,-1]

示例2

输入

[[1,1,1],[1,2,2],[2,1],[1,3,3],[2,2],[1,4,4],[2,1],[2,3],[2,4]],2

输出

[1,-1,-1,3,4]

算法知识视频讲解

映日飞云

通过的代码中，python区，排名第一的

用了list的remove(key)操作，时间复杂度是O(n)吧，为啥可以过？

我用自己leetcode官方答案，自己实现的双向链表，却超时？

https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/

还是leetcode好使

发表于 2021-01-30 13:37:00 回复(3)

dr4Utopia

LRU = Least Recently Used （最近最少使用）

本题提示了可供操作的两种方法get和set，而数据类型是key-value模式的，自然想到Map类型去实现；

其次，对最近读取的值(题目要求保存到数组返回)，和最近set的值，都是LRU值，那么关键点有两个：

1.在于当map容量达到k值的时候，如果set，需要删除最初保存的值同时put进去最新的值

2.get获取LRU的map里的值，如果没有，返回-1，存在则返回key对应value，同时要删除key之前在map里面的位置，使用put放入这对key-value

根据LinkedHashMap的特性，知道他的key是按照顺序存放的，这样删除第一个放进去的值(最不常用的值)很方便

把上述过程转化为代码就是

import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        // write code here
        LinkedHashMap<Integer,Integer> lruMap = new LinkedHashMap<Integer,Integer>();
        ArrayList<Integer> result = new ArrayList();
        
        for(int[] opat:operators){
            int key = opat[1];
            switch(opat[0]){
                case 1:
                    int value = opat[2];
                    if(lruMap.size()<k){
                        lruMap.put(key,value);
                    }else{
                        Iterator ot = lruMap.keySet().iterator();
                        lruMap.remove(ot.next());
                        lruMap.put(key,value);
                    }
                    break;
                case 2:
                    if(lruMap.containsKey(key)){
                        int val = lruMap.get(key);
                        result.add(val);
                        lruMap.remove(key);
                        lruMap.put(key,val);
                    }else{
                        result.add(-1);
                    }
                    break;
                default:
            }
        }
        int[] resultArr = new int[result.size()];
            int i=0;
            for(int a:result){
                resultArr[i++]=a;
            }
        return resultArr;
    }
}

编辑于 2020-09-16 09:34:38 回复(9)

羊羊羊~

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    // 记录key和value，同时记录当前key在content中的地址
    unordered_map<int, pair<int, list<int>::iterator>> store_list;
    // 和unordered_map同时变动，存放key，用于协助unordered_map删除最旧的元素
    list<int> content;
    int capacity=0;
    
    int get(int key) {
        int value = -1;
        auto iter = store_list.find(key);
        if (iter != store_list.end()) {
            value = iter->second.first;
            set(key, value);
        }
        return value;
    }
    void set(int key, int value) {
        auto iter = store_list.find(key);
        // 已存在，删除，后面有统一的insert
        if (iter != store_list.end()) {
            content.erase(iter->second.second);
            store_list.erase(iter);
        } else if (content.size() == capacity) {
            // 删除最旧的元素
            store_list.erase(store_list.find(content.back()));
            content.pop_back();
        }
        content.push_front(key);
        store_list[key] = make_pair(value, content.begin());
    }
    
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        capacity = k;
        vector<int> rt;
        for (vector<int>& tmp: operators){
            if (tmp.size() == 2) {
                rt.push_back(get(tmp[1]));
            } else {
                set(tmp[1], tmp[2]);
            }
        }
        return rt;
    }
};

发表于 2021-07-11 21:31:01 回复(0)

RyuAsuka

# 使用栈 + 哈希表的方式存储
class Solution:
    def LRU(self, operators, k):
        stack = []
        kv_pair = {}
        ans = []
        for op in operators:
            if op[0] == 1:
                if len(stack) < k:
                    stack.append((op[1], op[2]))
                    kv_pair[op[1]] = op[2]
                else:
                    key, value = stack.pop(0)
                    kv_pair.pop(key)
                    stack.append((op[1], op[2]))
                    kv_pair[op[1]] = op[2]
            elif op[0] == 2:
                if op[1] not in kv_pair:
                    ans.append(-1)
                else:
                    record = kv_pair[op[1]]
                    ans.append(record)
                    stack.remove((op[1], kv_pair[op[1]]))
                    stack.append((op[1], record))
        return ans

发表于 2020-09-23 11:30:28 回复(4)

Python3

牛客352198672号

class Solution:
    def LRU(self, operators, k):
        lru = []
        lrud = {}
        result=[]
        for i in operators:
            if i[0] == 1:
                lrud[i[1]] = i[2]
                if len(lru) == k and i[1] not in lru:
                    lru.pop(0)
                else:
                    if i[1] in lru:
                        lru.remove(i[1])
                lru.append(i[1])
            if i[0] == 2:
                if i[1] in lru:
                    lru.remove(i[1])
                    lru.append(i[1])
                    result.append(lrud[i[1]])
                else:
                    result.append(-1)
        return result

发表于 2021-07-29 21:09:14 回复(1)

JavaScript

小乌龟慢慢爬

为什么一样的代码,我就超时

发表于 2020-12-14 18:37:40 回复(3)

Java

HW柯可

import java.util.*;

public class Solution {
    
    public int[] LRU (int[][] operators, int k) {
        //true 表示让 linkedHashMap 按照访问顺序来进行排序，最近访问的放在尾部，最老访问的放在头部。
        LinkedHashMap<Integer, Integer> urlMap = new LinkedHashMap<Integer, Integer>((int)Math.ceil(k/0.75)+1, 0.75f, true);
        ArrayList<Integer> list = new ArrayList<>();
        for(int[] op: operators){
            if(op[0] == 1){
                if(urlMap.size() >= k){
                    urlMap.remove(urlMap.keySet().iterator().next());
                }
                urlMap.put(op[1], op[2]);
            }
            else if(op[0] == 2){
                if(urlMap.get(op[1]) == null){
                    list.add(-1);
                }else {
                    list.add(urlMap.get(op[1]));
                }
            }
        }
        int[] res = new int[list.size()];
        int index = 0;
        for(int i : list){
            res[index++] = i;
        }
        return res;
    }
}

编辑于 2020-09-13 11:42:27 回复(12)

Java

飘走的风

import java.util.*;

/*方法一
public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    /*public int[] LRU (int[][] operators, int k) {
        // write code here
        LinkedHashMap<Integer,Integer> map=new LinkedHashMap<>();
        ArrayList<Integer> list=new ArrayList<>();
        for(int i=0;i<operators.length;i++){
            Integer opt=operators[i][0],key=operators[i][1];
            if(opt==1){//set
                if(map.containsKey(key)){
                    map.remove(key);
                }else{
                     if(map.size()==k) map.remove(map.keySet().toArray()[0]);//超过限制移除
                }
                map.put(key,operators[i][2]);
               
            }else if(opt==2){
                if(map.containsKey(key)){//不要忘记get后也是要把key设为最新
                    int val=map.remove(key);
                    map.put(key,val);
                    list.add(map.get(key));
                }else{
                    
                    list.add(-1);
                }
            }
        }
        int[] arr=new int[list.size()];
        for(int i=0;i<arr.length;i++) arr[i]=list.get(i);
        return arr;
    }
}*/



//方法二
public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    
    HashMap<Integer,Integer> map=new HashMap<>();//存map
    LinkedList<Integer> keyList =new LinkedList<Integer>();//存key队列
    public int[] LRU (int[][] operators, int k) {
        // write code here
        
        ArrayList<Integer> list=new ArrayList<>();
        for(int i=0;i<operators.length;i++){
                int opt=operators[i][0],key=operators[i][1];
                if(keyList.contains(key)) keyList.remove(new Integer(key));
                keyList.addFirst(key);
                if(opt==1){//set
                    int value=operators[i][2];
                    if(map.size()==k){//超过缓存限制
                      if(map.get(key)==null){//map中没有key,必须移除最近最少使用key
                          int k1=keyList.removeLast();
                          map.remove(k1,map.get(k1));
                          map.put(key,value);
                      }else{
                          map.put(key,value);
                      }
                    }else{//没超过缓存限制
                        map.put(key,value);
                    }
                }else if(opt==2){//get，不要忘记get后也要将key设为最新
                    if(map.get(key)==null){
                        list.add(-1);
                    }else{
                        list.add(map.get(key));
                    }
                }
            if(!map.containsKey(key)) keyList.removeFirst();//判断结束后map有没有把key,v加入map,没有就没有这个key,要移除
        }
         int [] res=new int[list.size()];
         for(int i=0;i<res.length;i++){
             res[i]=list.get(i);
         }
          map.clear();
          keyList.clear();
         return res;
    }
}

编辑于 2020-08-25 13:17:36 回复(13)

一般市民Young

求大佬解释为什么用C手写双链表+哈希会发生段错误啊，明明leetcode上可以AC，牛客是***啊！

程序如下：

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param operatorsRowLen int operators数组行数
 * @param operatorsColLen int* operators数组列数
 * @param k int整型 the k
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */

#define Nothingness -1

struct myLNode{
    int key;
    int val;
    struct myLNode *pre;
    struct myLNode *next;
};

struct myHash{
    struct myHash *next; //拉链法解决哈希冲突
    struct myLNode *node;
};

typedef struct{
    int count;
    int k;
    // 维护哈希表，其本质是一个单向链表，拉链法解决哈希冲突
    struct myHash *table; 
    // 维护一个双向链表，用来实现LRU
    struct myLNode *head; // 创建伪头节点，后继指向最久远的键值对
    struct myLNode *tail; // 创建伪尾节点，前驱指向最常用的键值对
}lRUCache;

struct myHash *myHashMap(struct myHash *table, int key, int k){
    int add = key % k;
    
    return &table[add];
}
void updateList(struct myLNode *tail, struct myLNode *node){
    // 节点不在链表中
    if(node->pre == NULL && node->next == NULL){
        //用尾插法插入
        node->pre = tail->pre;
        node->next = tail;
        tail->pre->next = node;
        tail->pre = node;
    }
    else{//节点在链表中
        struct myLNode *last = tail->pre; //记录当前最常用的节点last
        if(node != last){ //将node节点插入last和tail之间
            node->next->pre = node->pre;
            node->pre->next = node->next;
            node->next = tail;
            node->pre = last;
            last->pre = node;
            last->next = node;
        }
    }
}

int myLRUGet(lRUCache *obj, int key){
    struct myHash *add = myHashMap(obj->table, key, obj->k);
    add = add->next;
    if(add == NULL)
        return Nothingness;
    while(add->next != NULL && add->node->key != key)
        add = add->next;
    if(add->node->key == key){
        updateList(obj->tail, add->node);
        return add->node->val;
    }
    return Nothingness;
}

void myLRUSet(lRUCache *obj, int key, int value){
    struct myHash *add = myHashMap(obj->table, key, obj->k);
    if(myLRUGet(obj, key) == Nothingness){ //键key不在链表中
        if(obj->count >= obj->k){ //达到存储上限
            struct myLNode *last = obj->head->next;
            struct myHash *del = myHashMap(obj->table, last->key, obj->k);
            struct myHash *tmp = del;
            del = del->next;
            //在拉链上寻找最久远的key
            while(del->node->key != last->key){
                tmp = del;
                del = del->next;
            }
            tmp->next = del->next; //从哈希表中删除该key对应的节点
            del->next = NULL;
            del->node =NULL;
            free(del);
            struct myHash *new_node = (struct myHash*)malloc(sizeof(struct myHash));
            new_node->next = add->next;
            add->next = new_node;
            last->key = key;
            last->val = value;
            new_node->node = last;
            updateList(obj->tail, last);
        }
        else{//未达到存储上限
            struct myHash *new_node = (struct myHash*)malloc(sizeof(struct myHash));
            new_node->node = (struct myLNode*)malloc(sizeof(struct myLNode));
            new_node->next = add->next; //创建新节点加入哈希表中
            add->next =new_node;
            new_node->node->key = key;
            new_node->node->val = value;
            new_node->node->pre = NULL; //初始化该节点的前驱和后继表明该节点未加入链表中
            new_node->node->next = NULL;
            updateList(obj->tail, new_node->node);
            (obj->count)++;
            
        }
    }
    else
        obj->tail->pre->val = value;
}

int* LRU(int** operators, int operatorsRowLen, int* operatorsColLen, int k, int* returnSize ) {
    // write code here
    lRUCache *obj = (lRUCache*)malloc(sizeof(lRUCache));
    obj->count = 0;
    obj->k = k;
    obj->head = (struct myLNode*)malloc(sizeof(struct myLNode));
    obj->tail = (struct myLNode*)malloc(sizeof(struct myLNode));
    obj->table = (struct myHash*)malloc(k*sizeof(struct myHash));
    memset(obj->table, 0, sizeof(struct myHash)*k);
    
    int i, j = 0;
    int *res = (int*)malloc(operatorsRowLen*sizeof(int));
    for(i=0; i<operatorsRowLen; i++){
        if(operators[i][0] == 1){
            myLRUSet(obj, operators[i][1], operators[i][2]);
        }
        
        else if(operators[i][0] == 2)
        {
            printf("%d\n", operators[i][1]);
            res[j] = myLRUGet(obj, operators[i][1]);
            j++;
        }
    }
    
    *returnSize = j - 1;
    
    return res;
}

发表于 2020-12-22 16:03:12 回复(0)

C++

丸子球球

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        //打印
        vector<int> nums;
        //缓存
        unordered_map<int,int> map;
        //LRU结构
        list<int> keys;
        //流程
        for(auto op:operators){
            //读写判断
            switch(op[0]){
                case 1:{
                    //写时缓存判断并获取空间
                    if(keys.size()==k){
                        map.erase(keys.back());
                        keys.pop_back();
                    }
                    //更新数据活跃状态
                    keys.remove(op[1]);
                    keys.push_front(op[1]);
                    //将数据存放或更新进缓存
                    auto search = map.find(op[1]);
                    if (search == map.end()) {
                        map.insert({op[1],op[2]});
                    }else{
                        search->second=op[2];
                    }
                }break;
                //读时
                case 2:{
                    //判断数据是否在缓存中并将数据打印
                    auto search = map.find(op[1]);
                    if (search == map.end()) {
                        nums.push_back(-1);
                    }else{
                        keys.remove(op[1]);
                        keys.push_front(op[1]);
                        nums.push_back(search->second);
                    }
                }break;
            }
        }
        return nums;
    }
};

发表于 2021-12-27 09:56:32 回复(0)

Java

不会真有人不僵硬吧

Java | 手写双向链表 + HashMap 实现 LRU

运行时间：834ms 超过78.26% 用Java提交的代码
占用内存：108044KB 超过94.95% 用Java提交的代码

import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        // write code here
        // 初始化 LRU
        LRUcache lrucache = new LRUcache(k);
        List<Integer> list = new ArrayList<>();
        for(int i=0; i<operators.length; i++){
            // 为 1 时，添加
            if(operators[i][0] == 1){
                lrucache.put(operators[i][1], operators[i][2]);
            }else{
                // 为 2 时，获取
                list.add(lrucache.get(operators[i][1]));
            }
        }
        
        // 输出答案
        int[] ans = new int[list.size()];
        for(int i=0; i<list.size(); i++){
            ans[i] = list.get(i);
        } 
        return ans;
    }
}

// 手写 LRU 缓存
class LRUcache{
    // 双向链表
    class Node{
        int key, value;
        Node pre, next;
        public Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
    // HashMap 和 大小记录
    Map<Integer, Node> map = new HashMap<>();
    int size = 0;
    
    // 定义双向链表头尾节点
    Node head = new Node(-1, -1);
    Node tail = new Node(-1, -1);
    
    // 定义 LRU 容量
    int capacity;
    
    // 外部接口，根据 key 获取 value
    public int get(int key){
        Node node = map.get(key);
        if(node == null){
            return -1;
        }
        moveToHead(node);
        return node.value;
    }
    
    // 外部接口，加入 key，value 到 LRU 缓存
    public void put(int key, int value){
        Node node = map.get(key);
        if(node == null){
            Node iNode = new Node(key, value);
            if(size < capacity){
                insertNode(iNode);
            }else{
                deleteNode(tail.pre);
                insertNode(iNode);
            }
        }else{
            node.value = value;
            moveToHead(node);
        }
    }
    
    // 内部方法，将当前节点更新到链表首端
    private void moveToHead(Node node){
        deleteNode(node);
        insertNode(node);
    }
    
    // 内部方法，将当前节点从链表中删除
    private void deleteNode(Node node){
        map.remove(node.key);
        node.pre.next = node.next;
        node.next.pre = node.pre;
        size--;
    }
        
    // 内部方法，将当前节点加入链表，放于首端
    private void insertNode(Node node){
        map.put(node.key, node);
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
        node.pre = head;
        size++;
    }
    
    // 构造方法，初始化 LRU
    public LRUcache(int capacity){
        this.capacity = capacity;
        head.next = tail;
        tail.pre = head;
        tail.next = null;
    }
}

发表于 2021-06-15 10:53:54 回复(1)

我的过去常常追赶着我

 public int[] LRU (int[][] operators, int k) {
            // write code here
            int length = 0;
            int index = 0;
            for(int i =0;i<operators.length;i++){
                if(operators[i][0]==2){
                    length++;
                }

            }
            int [] result = new int [length];
            Map<Integer,Integer> map = new HashMap();
            List<Integer> list = new ArrayList();
            for(int i =0;i<operators.length;i++){
                if(operators[i][0]==1){
                    int key = operators[i][1];
                    int value = operators[i][2];
                    if(map.size()<k){
                        map.put(key,value);
                        if(list.contains(key)){
                            list.remove((Integer)key);
                        }
                        list.add(key);

                    }else{
                        if(list.contains(key)){
                            list.remove((Integer)key);
                            list.add(key);
                        }else{
                            int get_key = list.remove(0);
                            map.remove(get_key);
                            list.add(key);
                            map.put(key,value);
                        }
                    }
                }else if(operators[i][0]==2){
                    int check_key = operators[i][1];
                    if(!map.containsKey(check_key)){
                        result[index] = -1;
                    }else{
                        result[index] = map.get(check_key);
                        list.remove((Integer)check_key);
                        list.add(check_key);
                    }
                    index++;
                }
            }
            return  result;
        }

以前大二在学校里写过，现在突然再写居然还花了点功夫

发表于 2020-08-25 15:10:36 回复(8)

JavaScript Node

稚子归途误

利用ES6 Map的迭代顺序就是set插入的顺序

function LRU( operators, k ) {
    const map = new Map()
    const res = []
    for (let opt of operators) {
        // get操作：
        if (opt[0] == 2) {
            let key = opt[1]
            if (map.has(key)) {
                // 让该key成为最新访问
                let value = map.get(key)
                map.delete(key)
                map.set(key, value)
                res.push(map.get(key))
            } else {
                res.push(-1)
            }
        }
        
        // set操作：
        if (opt[0] == 1) {
            let key = opt[1], value = opt[2]
            map.set(key, value) // 该键值对会自动放在map的最后
            // 如果溢出，则删除map第一个元素（最近既没有被get，也没有被set）
            if (map.size > k) {
                map.delete(map.keys().next().value)
            }
        }
    }
    return res
}

发表于 2021-09-02 12:20:05 回复(1)

C/C++

VVILL

#include <unordered_map>
#include <list>

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        vector<int> result;
        cap=k;
        result.reserve(operators.size());
        if(k!=0) {
            for(const vector<int>& opt:operators) {
                if(opt[0]==1) set(opt[1],opt[2]);
                else if(opt[0]==2) result.push_back(get(opt[1]));
            }
        }
        return result;
    }
    
    int get(int key) {
        auto it=m.find(key);
        if(it==m.end()) return -1;
        l.splice(l.begin(),l,it->second);
        return it->second->second;
    }
    
    void set(int key,int value) {
        auto it=m.find(key);
        if(it!=m.end()) l.erase(it->second);
        l.push_front(make_pair(key,value));
        m[key]=l.begin();
        if(m.size()>cap) {
            int k=l.rbegin()->first;
            l.pop_back();
            m.erase(k);
        }
    }
   
private:
    int cap;
    list<pair<int,int> > l;
    unordered_map<int,list<pair<int,int> >::iterator> m;
};

发表于 2020-08-29 14:31:06 回复(0)

Java

hhffgukih

顺便写个通用LRU工具类

import java.util.*;

public class Solution {
    
    public int[] LRU (int[][] operators, int k) {
        LRUCache<Integer, Integer> lruCache = new LRUCache<>(k);
        int len = (int)Arrays.stream(operators).filter(x -> x[0] == 2).count();
        // 存储返回结果
        int[] res = new int[len];
        for(int i = 0, j = 0; i < operators.length; i++) {
            if(operators[i][0] == 1) {
                lruCache.set(operators[i][1], operators[i][2]);
            } else {
                res[j++] = lruCache.get(operators[i][1]) == null? -1: lruCache.get(operators[i][1]);
            }
        }
        return res;
    }

}

class LRUCache<K, V> {
    private final ListNode<K, V> head = new ListNode<>(null, null);
    private final ListNode<K, V> tail = new ListNode<>(null, null);

    private final Map<K, ListNode<K, V>> map = new HashMap<>();
    int lruMaxSize;

    public LRUCache(int size){
        head.next = tail;
        tail.pre = head;
        this.lruMaxSize = size;
    }

    public void set(K key, V val){
        if(map.get(key) != null){
            map.get(key).val = val;
        }else {
            if(map.size() >= lruMaxSize){
                K lastKey = tail.pre.key;
                map.remove(lastKey);
                tail.pre.pre.next = tail;
                tail.pre = tail.pre.pre;
            }
            ListNode<K, V> node = new ListNode<>(key, val);
            map.put(key, node);
            moveToHead(node);
        }
    }

    private void moveToHead(ListNode<K,V> node) {
        head.next.pre = node;
        node.next = head.next;
        head.next = node;
        node.pre = head;
    }

    public V get(K key){
        if(map.get(key) != null){
            ListNode<K, V> node = map.get(key);
            node.pre.next = node.next;
            node.next.pre = node.pre;
            moveToHead(node);
            return node.val;
        }else {
            return null;
        }
    }
    
    static class ListNode<K, V>{
        K key;
        V val;
        ListNode<K, V> next;
        ListNode<K, V> pre;
        public ListNode(K key, V val){
            this.key = key;
            this.val = val;
        }
    }
}

发表于 2022-01-15 15:04:29 回复(0)

Python 3

牛客296529746号

#
class Solution:
    def LRU(self , operators: List[List[int]], k: int) -> List[int]:
        # write code here
        result=[]
        lrud={}
        for i in operators:
            if i[0]==1:
                lrud[i[1]]=i[2]
                if len(lrud) > k:
                    lrud.pop(list(lrud)[0])
            else:
                if i[1] in list(lrud):
                    result.append(lrud[i[1]])
                    lrud[i[1]]=lrud.pop(i[1])
                else:
                    result.append(-1)
        return result

发表于 2021-12-19 19:15:11 回复(0)

哎哟喂12138

go 中没有对应的结构，需要自己定义相关数据结构，完整代码如下：

package main

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
*/
func LRU( operators [][]int ,  k int ) []int {
    // write code here
    res := make([]int,0)
    cache := newCache(k)
    for  i := range operators {
        if operators[i][0] == 1 {
            // set
            cache.Put(operators[i][1],operators[i][2])
        } else {
            val := cache.Get(operators[i][1])
            res = append(res,val)

        }
    }
    return res
}

type Node struct {
    Pre,Next *Node
    Key,Val int
}

func newNode(key,val int) *Node{
    return &Node{Key: key,Val: val}
} 

type LRUCache struct{
    Map map[int]*Node
    Head,Tail *Node
    Size int
    Cap int
}

func newCache(cap int) *LRUCache {
    cache := &LRUCache{
        Map: make(map[int]*Node,cap),
        Head: newNode(0,0),
        Tail: newNode(0,0),
        Size:0,
        Cap: cap,
    }

    cache.Head.Next = cache.Tail
    cache.Tail.Pre = cache.Head
    return cache
}

func (m *LRUCache)RemoveNode(node *Node) {
    node.Next.Pre = node.Pre
    node.Pre.Next = node.Next

}


func (m *LRUCache) RemoveTail() *Node {
    node := m.Tail.Pre
    m.RemoveNode(node)
    return node
}

func (m *LRUCache) MoveToHead(node *Node) {
    m.RemoveNode(node)
    m.AddToFront(node)
}

func (m *LRUCache) AddToFront(node *Node) {
    node.Next = m.Head.Next
    node.Pre = m.Head

    m.Head.Next.Pre = node
    m.Head.Next = node
}


func (m *LRUCache) Get(key int) int{
    if node,ok := m.Map[key];ok {
       m.MoveToHead(node)
        return node.Val
    } 
    return -1
}

func (m *LRUCache) Put(key,val int){
    if node,ok := m.Map[key];ok {
        node.Val = val
        m.MoveToHead(node)
        return
    } else {
        newNode := newNode(key,val)
        m.Map[key] = newNode
        m.AddToFront(newNode)
        m.Size++
        if m.Size > m.Cap {
            tail := m.RemoveTail()
            delete(m.Map,tail.Key)
            m.Size--
        }

    }
}

发表于 2021-12-01 23:06:03 回复(0)

C++

M3stark

struct DoubleList {
    int key, value;
    DoubleList *prev, *next;
    DoubleList() : key(0), value(0), prev(nullptr), next(nullptr) {}
    DoubleList(int key, int value) : key(key), value(value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    int capacity;
    DoubleList *head, *tail;
    unordered_map<int, DoubleList*> cache;
public:
    LRUCache(int _capacity) : capacity(_capacity) {
        head = new DoubleList();
        tail = new DoubleList();
        head->next = tail;
        tail->prev = head;
    }
    
    void add(DoubleList* node) {
        tail->prev->next = node;
        node->prev = tail->prev;
        node->next = tail;
        tail->prev = node;
    }
    
    void remove(DoubleList* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    
    int get(int _key) {
        if (cache.find(_key) == cache.end()) {
            return -1;
        }
        DoubleList* node = cache[_key];
        remove(node);
        add(node);
        return node->value;
    }
    
    void put(int _key, int _val) {
        if (cache.find(_key) != cache.end()) {
            DoubleList* node = cache[_key];
            remove(node);
            node->value = _val;
            add(node);
            return;
        }
        if (cache.size() == capacity) {
            int removed = head->next->key;
            remove(head->next);
            cache.erase(removed);
        }
        DoubleList* node = new DoubleList(_key, _val);
        add(node);
        cache[_key] = node;
    }
};

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        vector<int> res;
        LRUCache* lru = new LRUCache(k);
        for (auto op : operators) {
            if (op[0] == 1) {
                lru->put(op[1], op[2]);
            } else if (op[0] == 2) {
                res.push_back(lru->get(op[1]));
            }
        }
        return res;
    }
};

发表于 2021-10-16 10:53:08 回复(0)

Python3

JimPanda

class Solution:
    def LRU(self , operators , k ):
        # write code here
        stack = []
        kv_pair = {}
        ans = []
        for op in operators:
            if(op[0]==1):
                if(len(stack)>=k):
                    del kv_pair[stack.pop(0)]
                if(op[1] in kv_pair):
                    stack.pop(stack.index(op[1]))    
                stack.append(op[1])
                kv_pair[op[1]] = op[2]
            elif(op[0]==2):
                if(op[1] not in kv_pair):
                    ans.append(-1)
                else:
                    ans.append(kv_pair[op[1]])
                    stack.append(stack.pop(stack.index(op[1])))
        return ans

发表于 2021-10-14 10:01:21 回复(0)

C++

月落ol

最后一组过不去，哭了

class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
    map<int, int> cacheMap;//用来存k-v值，方便查找
    queue<int> cacheQueue;//用来存map中存在的k值，同时控制容量
    vector<int> rs;//存储结果
    int n=operators.size();
    for(int i=0;i<n;i++){
        if(operators[i][0]==1){//set操作
            if(cacheMap.find(operators[i][1])!=cacheMap.end()){//要存入的key已存在
                cacheQueue.pop();
                cacheQueue.push(operators[i][1]);//key存入队列
                cacheMap.erase(operators[i][1]);
                cacheMap.insert(pair<int,int>(operators[i][1],operators[i][2]));
            }
            else{//key在map中不存在，直接加
                cacheQueue.push(operators[i][1]);//key存入队列
                cacheMap.insert(pair<int,int>(operators[i][1],operators[i][2]));
            }
            if(cacheQueue.size()>k){//达到最大容量
                cacheMap.erase(cacheQueue.front());//删除map中和queque头对应的数据
                cacheQueue.pop();//queue删除头元素
            }
        }
        else if(operators[i][0]==2){//get操作
            if(cacheMap.find(operators[i][1])!=cacheMap.end()){//map中查得到
                int result=cacheMap.find(operators[i][1])->second;//取key的value
                cacheQueue.pop();//删除头元素
                cacheQueue.push(operators[i][1]);//加入尾部
                rs.push_back(result);//存入结果集
            }
            else{
                rs.push_back(-1);//map中查不到
            }
        }
    }
    return rs;
    }
};

发表于 2021-10-02 20:23:35 回复(1)