设计并实现一个满足 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) 的平均时间复杂度运行。

代码

class LRUCache {
public:
    LRUCache(int capacity) {
        q.size = capacity;
        f.clear();
    }
    
    int get(int key) {
        if (f.count(key)) {
            CacheNode *node = f[key];
            q.remove(node);
            q.push_front(node);
            return node->val;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if (f.count(key)) {
            CacheNode *node = f[key];
            node->val = value;
            q.remove(node);
            q.push_front(node);
        } else {
            CacheNode *node = new CacheNode(key, value);
            if (q.size == 0) {
                q.push_front(node);
                f.erase(q.tail->prev->key);
                q.pop_back();
                f[key] = node;
            } else {
                q.push_front(node);
                --q.size;
                f[key] = node;
            }
        }
    }
private:
    struct CacheNode {
        int key, val;
        CacheNode *prev;
        CacheNode *next;
        CacheNode() {}
        CacheNode(int key, int val):key(key), val(val), prev(NULL), next(NULL) {}
    };
    
    struct CacheList {
        CacheNode *head = new CacheNode(0, 0);
        CacheNode *tail = new CacheNode(0, 0);
        int size;
        
        CacheList() {
            head->next = tail;
            tail->prev = head;
        }

        void push_front(CacheNode *node) {
            node->prev = head;
            node->next = head->next;
            head->next->prev = node;
            head->next = node;
        }
        
        void remove(CacheNode *node) {
            node->prev->next = node->next;
            node->next->prev = node->prev;
        }
        
        void pop_back() {
            CacheNode *node = tail->prev;
            remove(node);
            delete(node);
        }
    };
    
    CacheList q{};
    unordered_map<int, CacheNode*> f;
};

/**
 * 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);
 */

MojoのBlog

LeetCode 146.LRU缓存

代码