Skip to content

[面试题] 16.25. LRU 缓存 #96

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
frdmu opened this issue Sep 7, 2021 · 0 comments
Open

[面试题] 16.25. LRU 缓存 #96

frdmu opened this issue Sep 7, 2021 · 0 comments

Comments

@frdmu
Copy link
Owner

frdmu commented Sep 7, 2021

设计和构建一个“最近最少使用”缓存,该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值),并在初始化时指定最大容量。当缓存被填满时,它应该删除最近最少使用的项目。

它应该支持以下操作: 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

解法:
双向链表+Hash Table。
双向链表首尾设置哑结点,表头放置最近处理过的key,表尾放置很久以前处理过的key。
代码如下:

class LRUCache {
public:
    struct Node{
        int val;
        Node* pre;
        Node* next;
        Node(): val(-1), pre(nullptr), next(nullptr) {}
        Node(int x): val(x), pre(nullptr), next(nullptr) {}
    };

    int c;
    Node* head = new Node();
    Node* tail = new Node();
    int len = 0; 
    map<int, int> mp;
    
    LRUCache(int capacity) {
        c = capacity;
        head->next = tail;
        tail->pre = head;
    }

    void updatePositoin(int key) {
        Node* p = head;
        // find
        while (p->next != tail) {
            if (p->next->val == key)
                break;
            p = p->next;    
        }
        // delete
        Node* target = p->next;
        p->next = target->next;
        target->next->pre = p;
        // insert target into head
        target->next = head->next;
        target->pre = head;
        head->next = target;
        target->next->pre = target;
    }

    int deleteTail() {
        int res = tail->pre->val;
        // delete old tail
        Node* tmp = tail->pre;
        tmp->pre->next = tail;
        tail->pre = tmp->pre;

        return res;    
    }

    void append(int key) {
        Node* target = new Node(key);
        
        // insert target into head
        target->next = head->next;
        target->pre = head;
        head->next = target;
        target->next->pre = target;
    }

    int get(int key) {
        if (mp.find(key) != mp.end()) {
            updatePositoin(key);
            return mp[key];    
        } 

        return -1;
    }
    
    void put(int key, int value) {
        if (mp.find(key) != mp.end()) { // update
            updatePositoin(key); 
        } else { // append
            len++; 
            if (len > c) {
                int tmp = deleteTail();
                mp.erase(tmp);
            }
            append(key);
        }

        mp[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);
 */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant