請你設(shè)計(jì)并實(shí)現(xiàn)一個滿足??LRU (最近最少使用) 緩存?約束的數(shù)據(jù)結(jié)構(gòu)。

實(shí)現(xiàn)?LRUCache?類：

• LRUCache(int capacity)?以?正整數(shù)?作為容量?capacity?初始化 LRU 緩存
• int get(int key)?如果關(guān)鍵字?key?存在于緩存中，則返回關(guān)鍵字的值，否則返回?-1?。
• void put(int key, int value)?如果關(guān)鍵字?key?已經(jīng)存在，則變更其數(shù)據(jù)值?value?；如果不存在，則向緩存中插入該組?key-value?。如果插入操作導(dǎo)致關(guān)鍵字?jǐn)?shù)量超過?capacity?，則應(yīng)該?逐出?最久未使用的關(guān)鍵字。

函數(shù)?get?和?put?必須以?O(1)?的平均時間復(fù)雜度運(yùn)行。

思路一：雙向鏈表

c語言解法

struct LRUInfo{
    int val;
    int value;
    struct LRUInfo* pre;
    struct LRUInfo* next;
};

typedef struct {
    int top;
    int total;
    struct LRUInfo * head;
    struct LRUInfo * rear;
    struct LRUInfo lruinfo[10001];
} LRUCache;

LRUCache* lRUCacheCreate(int capacity) {
    LRUCache* obj = calloc(1, sizeof(LRUCache));
    obj->total = capacity;
    obj->head = calloc(1, sizeof(struct LRUInfo));
    obj->rear = calloc(1, sizeof(struct LRUInfo));
    obj->head->next = obj->rear;
    obj->rear->pre = obj->head;
    return obj;
}

int lRUCacheGet(LRUCache* obj, int key) {
    if (obj->lruinfo[key].val == 1) {
        obj->lruinfo[key].pre->next = obj->lruinfo[key].next;
        obj->lruinfo[key].next->pre = obj->lruinfo[key].pre;
        obj->rear->pre->next = obj->lruinfo + key;
        obj->lruinfo[key].pre = obj->rear->pre;
        obj->lruinfo[key].next = obj->rear;
        obj->rear->pre = obj->lruinfo + key;
        return obj->lruinfo[key].value;
    }
    return -1;
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    if (obj->lruinfo[key].val == 0 && obj->top < obj->total) {
        (obj->top)++;
        obj->rear->pre->next = obj->lruinfo + key;
        obj->lruinfo[key].pre = obj->rear->pre;
        obj->lruinfo[key].next = obj->rear;
        obj->lruinfo[key].val = 1;
        obj->lruinfo[key].value = value;
        obj->rear->pre = obj->lruinfo + key;
    } else if (obj->lruinfo[key].val == 1){
        obj->lruinfo[key].pre->next = obj->lruinfo[key].next;
        obj->lruinfo[key].next->pre = obj->lruinfo[key].pre;
        obj->rear->pre->next = obj->lruinfo + key;
        obj->lruinfo[key].pre = obj->rear->pre;
        obj->lruinfo[key].next = obj->rear;
        obj->lruinfo[key].value = value;
        obj->rear->pre = obj->lruinfo + key;
    } else if (obj->lruinfo[key].val == 0 && obj->top >= obj->total && obj->head->next != NULL) {
        obj->lruinfo[key].val = 1;
        obj->lruinfo[key].value = value;
        obj->rear->pre->next = obj->lruinfo + key;
        obj->lruinfo[key].pre = obj->rear->pre;
        obj->lruinfo[key].next = obj->rear;
        obj->rear->pre = obj->lruinfo + key;
        obj->head->next->val = 0;
        obj->head->next = obj->head->next->next;
        obj->head->next->pre = obj->head;       
    }
    return;
}

void lRUCacheFree(LRUCache* obj) {
    free(obj);
}

/**
 * Your LRUCache struct will be instantiated and called as such:
 * LRUCache* obj = lRUCacheCreate(capacity);
 * int param_1 = lRUCacheGet(obj, key);
 
 * lRUCachePut(obj, key, value);
 
 * lRUCacheFree(obj);
*/

分析：

本題要實(shí)現(xiàn)LRU緩存實(shí)現(xiàn)雙向鏈表的各個操作后即可解決，刪除方法利用前驅(qū)節(jié)點(diǎn)的指針才能滿足O(1)的時間復(fù)雜度，get方法利用前驅(qū)節(jié)點(diǎn)達(dá)到O(1)的時間復(fù)雜度

總結(jié)：

本題考察對LRU緩存的實(shí)現(xiàn)，考慮到各個方法的實(shí)現(xiàn)的時間復(fù)雜度要求在O(1)，所以采用雙向鏈表保證時間復(fù)雜度，最后實(shí)現(xiàn)各個方法即可解決文章來源地址http://www.zghlxwxcb.cn/news/detail-730682.html

到了這里，關(guān)于leetcode做題筆記146. LRU 緩存的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！