首页 > 试题广场 >

设计LRU缓存结构

[编程题]设计LRU缓存结构
  • 热度指数：31671 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 capacity ，操作次数是 n ，并有如下功能:
1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
2. get(key)：如果关键字 key 存在于缓存中，则返回key对应的value值，否则返回 -1 。
3. set(key, value)：将记录(key, value)插入该结构，如果关键字 key 已经存在，则变更其数据值 value，如果不存在，则向缓存中插入该组 key-value ，如果key-value的数量超过capacity，弹出最久未使用的key-value

提示:
1.某个key的set或get操作一旦发生，则认为这个key的记录成了最常使用的，然后都会刷新缓存。
2.当缓存的大小超过capacity时，移除最不经常使用的记录。
3.返回的value都以字符串形式表达，如果是set，则会输出"null"来表示(不需要用户返回，系统会自动输出)，方便观察
4.函数set和get必须以O(1)的方式运行
5.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹
数据范围:




示例1

输入

["set","set","get","set","get","set","get","get","get"],[[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]],2

输出

["null","null","1","null","-1","null","-1","3","4"]

说明

我们将缓存看成一个队列，最后一个参数为2代表capacity，所以
Solution s = new Solution(2);
s.set(1,1); //将(1,1)插入缓存，缓存是{"1"=1}，set操作返回"null"
s.set(2,2); //将(2,2)插入缓存，缓存是{"2"=2，"1"=1}，set操作返回"null"
output=s.get(1);// 因为get(1)操作，缓存更新，缓存是{"1"=1，"2"=2}，get操作返回"1"
s.set(3,3); //将(3,3)插入缓存，缓存容量是2，故去掉某尾的key-value，缓存是{"3"=3，"1"=1}，set操作返回"null" 
output=s.get(2);// 因为get(2)操作，不存在对应的key，故get操作返回"-1"
s.set(4,4); //将(4,4)插入缓存，缓存容量是2，故去掉某尾的key-value，缓存是{"4"=4，"3"=3}，set操作返回"null" 
output=s.get(1);// 因为get(1)操作，不存在对应的key，故get操作返回"-1"
output=s.get(3);//因为get(3)操作，缓存更新，缓存是{"3"=3，"4"=4}，get操作返回"3"
output=s.get(4);//因为get(4)操作，缓存更新，缓存是{"4"=4，"3"=3}，get操作返回"4"
算法知识视频讲解
添加回答
C
一个优雅的程序猿头像 一个优雅的程序猿
o(1)，数据又要搞那么大，十的九次方，有必要？C语言怎么建哈希表？只想着JAVA/C+那些。 
#include <stdio.h>
#include <string.h>
struct ListTable{
    int key;
    unsigned long value;
    struct ListTable *last;
    struct ListTable *next;
};
typedef struct List{
    unsigned long  capacity;
    unsigned long  NodeNum;
    //struct ListTable *HashTable[2000001];//2000000001
    struct ListTable *head,*end;
} Solution;

struct ListTable* searchNode(Solution* obj, int key) {
    struct ListTable* p = obj->head;
    while(p!=NULL) {
        if(p->key == key)
            return p;
        p = p->next;
    }
    return NULL;
}

void SubNode(Solution* obj, int key, struct ListTable* HashTable) {
    if(HashTable==obj->head){
        obj->head = obj->head->next;
        obj->head->last = NULL;
    }
    else {
        HashTable->last->next = HashTable->next;
        HashTable->next->last = HashTable->last;
    }
    HashTable->next = NULL;
    HashTable->last = NULL;
}

void AddEndNode(Solution* obj, int key, int value, struct ListTable* HashTable) {
    obj->end->next = HashTable;
    HashTable->last = obj->end;
    HashTable->next = NULL;
    obj->end = HashTable;
    HashTable->key = key;
    HashTable->value = value;
}

Solution* SolutionCreate(int capacity) {
    int i;
    Solution *res;
    res = (Solution*)malloc(sizeof(Solution));
    res->capacity = capacity;
    res->NodeNum = 0;
    //for(i=0; i<sizeof(res->HashTable)/sizeof(res->HashTable[0]); i++) 
    //    res->HashTable[i] = NULL;
    res->head = NULL;
    res->end = NULL;
    return res;
}

int SolutionGet(Solution* obj, int key) {
    struct ListTable* HashTable = searchNode(obj, key);
    if(HashTable == NULL) 
        return -1;
    if(HashTable!=obj->end) {
        SubNode(obj, key, HashTable);
        AddEndNode(obj, key, HashTable->value, HashTable);
    }
    return HashTable->value; 
}

void SolutionPut(Solution* obj, int key, int value) {
    struct ListTable* HashTable = searchNode(obj, key);
    if(obj->head == NULL) {
        obj->head = (struct ListTable*)malloc(sizeof(struct ListTable));
        obj->end = obj->head;
        obj->head->key = key;
        obj->head->value = value;
        obj->head->last = NULL;
        obj->head->next = NULL;
        //obj->HashTable[key] = obj->head;
        obj->NodeNum = 1;
    }
    else {
        if(HashTable == NULL) {
            struct ListTable* NewNode;
            NewNode = (struct ListTable*)malloc(sizeof(struct ListTable));
            HashTable = NewNode;
            obj->NodeNum++;
            AddEndNode(obj, key, value, HashTable);
        }   
        else {
            if(HashTable == obj->end){
                HashTable->value = value;
            }
            else {
                SubNode(obj, key, HashTable);
                AddEndNode(obj, key, value, HashTable);
            }
        }
            
        if(obj->NodeNum > obj->capacity) {
            struct ListTable* p = obj->head;
            SubNode(obj, obj->head->key, obj->head);
            //if(p!=NULL) obj->HashTable[p->key] = NULL;
            free(p);
            obj->NodeNum--;
        }
    }
}

void SolutionFree(Solution* obj) {
    int i;
    struct ListTable* p = obj->head;
    for(i=0; i<obj->NodeNum-1; i++) {
        struct ListTable* last=p;
        p = p->next;
        free(last);
    }
    free(obj);
}
/**
 * Your Solution struct will be instantiated and called as such:
 * Solution* obj = SolutionCreate(capacity);
 * int param_1 = SolutionGet(obj, key);
 * SolutionPut(obj, key, value);
 * SolutionFree(obj);
*/

编辑于 2024-03-29 20:24:28 回复(1)
C
牛客538374717号头像 牛客538374717号
//用C语言数组实现，有编译错误，有大牛能告知原因吗 谢谢
typedef struct {
    int key;
    int value;
} ITEM_S;

typedef struct {
    // write code here
    int capacity;
    ITEM_S *pstItem;
} Solution;

Solution* SolutionCreate(int capacity) {
     // write code here
    Solution* obj = NULL;
    int len = sizeof(Solution) + sizeof(ITEM_S)*capacity;
    obj = malloc(len);
    memset(obj,0,len);

    return obj;
}

int SolutionGet(Solution* obj, int key) {
     // write code here
    int i,j;
    int value = -1;
    ITEM_S tmp;
    ITEM_S *pstItem = obj->pstItem;

    for(i=0; i<obj->capacity; i++)
    {
        if (key == pstItem[i].key)
        {
            value = pstItem[i].value;

            for(j=i-1; j>=0; j--)
            {
                memcpy(&tmp,&pstItem[i],sizeof(ITEM_S));
                memcpy(&pstItem[i],&pstItem[j],sizeof(ITEM_S));
                memcpy(&pstItem[j],&tmp,sizeof(ITEM_S));
            }
        }
    }
    return value;
}

void SolutionSet(Solution* obj, int key, int value) {
     // write code here
    int j;
    ITEM_S *pstItem = obj->pstItem;

    for(j=obj->capacity-1; j<=1; j--)
    {
        memcpy(&pstItem[j],&pstItem[j-1],sizeof(ITEM_S));
    }
    pstItem->key = key;
    pstItem->value = value;

    return;     
}

void SolutionFree(Solution* obj) {
     // write code here
    if (NULL != obj)
    {
        free (obj);
    }
    return;
}

发表于 2022-10-01 16:08:15 回复(1)
提交观点

问题信息

模拟 链表 哈希
上传者：牛客301499号
难度：
5条回答 2986浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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