lc.146.lru缓存

​

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

提示：

1
2
3

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105

最多调用 2 * 105 次 get 和 put

解题代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

struct Node {
    int key,value;
    Node *pre,*next;
};
void printNode(Node*x) {
    if(x) {
        while(x) {
            printf("Node {k=%d,v = %d}-> ",x->key,x->value);
            x=x->next;
        }
    }
}
class LRUCache {
public:
Node* root,*lastNode;
int cap;
int size;
unordered_map<int,Node*>mp;
bool debug  = false;
    LRUCache(int capacity) {
        root = new Node();
        root->key = root->value = 0;
        root->pre  = NULL;
        cap = capacity;
        size = 0;
        lastNode = new Node();
        lastNode->pre = root;
        lastNode ->next = NULL;
        root->next = lastNode;
    }
    void _addFirst(Node *x) {
        _removeNode(x);
        x->next = root->next;
        root->next ->pre =x;

        root->next = x;
        x->pre  = root;
    }
    void _removeNode(Node *x) {
        if(!x) return;
        Node *pre = x->pre,*next = x->next;
        if(pre) {
            pre->next = x->next;
        }
        if(next ) {
            next->pre = pre;
        }
        x->next = NULL;
        x->pre = NULL;
    }
    int get(int key) {
        if(!mp[key]) return -1;
        Node *x = mp[key];
        _addFirst(x);
        if(debug) printNode(root->next); printf("=> get %d\n",key);
        return x->value;
    }
    Node* _removeLast() {
        if(lastNode->pre == root) {return NULL;}
        Node* x= lastNode -> pre;
       _removeNode(x);

        return x;
    }
    void put(int key, int value) {
        if(get(key) != -1) {
            // get(key);
            root->next->value = value;
            if(debug) {
                printNode(root->next);
                printf(" put %d,%d \n",key,value);
            }
           
            return;

        } 
        
        if(size >=  cap   ) {
            Node *x = _removeLast();
            // printf("%d--%d\n",key,x->value);
            //todo:校验
             
            if(x) mp.erase(x->key),size--;
            else printf("error\n");
        }
         
        //size< cap
        
        size++;
        Node *x = new Node();
        x->key = key;
        x->value = value;
        x->pre = root;
        x->next = root->next;
        if(root->next) {
            root->next->pre = x;
        }
        root->next = x;
        mp[key] = x;
             
        if(debug) {
            printNode(root->next);
            printf(" put %d,%d \n",key,value);
        }
       

    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

debug演示

1
2
3
4
5
6

Node {k=2,v = 1}-> Node {k=0,v = 0}->  put 2,1 
Node {k=2,v = 1}-> Node {k=0,v = 0}-> => get 2
Node {k=2,v = 2}-> Node {k=0,v = 0}->  put 2,2 
Node {k=2,v = 2}-> Node {k=0,v = 0}-> => get 2
Node {k=1,v = 1}-> Node {k=2,v = 2}-> Node {k=0,v = 0}->  put 1,1 
Node {k=4,v = 1}-> Node {k=1,v = 1}-> Node {k=0,v = 0}->  put 4,1