0146 - LRU Cache

題目

LeetCode: 146. LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

想法

1. 基本上就是操作 linked list
2. 在存取 key 時就把 key 的 node 移動到 head
3. 要把東西丟掉就從尾巴
4. stl 有 std::list 可以使用
   1. 不過在移動 node 時，由於 c++ ref 上並沒有寫明假如在同一個 list 上是否可以 splice，所以這裡是先刪除再加入

Ptr Code

struct Node {
    Node* prev = nullptr;
    Node* next = nullptr;
    
    int data = 0;
    
    Node(int data = 0): data(data) {}
};

// linkNode link a->b
inline void linkNode(Node* a, Node* b) {
    a->next = b;
    b->prev = a;
}

// linkNode link a->b->c
inline void linkNode(Node* a, Node* b, Node* c) {
    linkNode(a, b);
    linkNode(b, c);
}

class LinkList {
private:
    // init: head -> tail
    Node* head_;
    Node* tail_;
    
    int size_ = 0;
public:
    
    // Remove copy operation
    LinkList(const LinkList&) = delete;
    LinkList& operator=(const LinkList&) = delete;

    LinkList(): head_(new Node()), tail_(new Node()){
        head_->next = tail_;
        tail_->prev = head_;
    }
    
    ~LinkList() {
        auto cur = head_;
        while (cur != nullptr) {
            auto tmp = cur;
            cur = cur->next;
            delete tmp;
        }
    }
    
    Node* pushHead(int data) {
        // before: head->n1
        // after: head->n0->n1
        auto n0 = new Node(data);
        
        linkNode(head_, n0, head_->next);
        ++size_;
        
        return n0;
    }
    
    void nodeToHead(Node* n) {
        // before: ..n1->n->n0..
        // after: head->n->h0..
        
        linkNode(n->prev, n->next);
        linkNode(head_, n, head_->next);
    }
    
    int popTail() {
        // before: n1->n0->tail
        // after: n1->tail;
        auto n = tail_->prev;
        linkNode(n->prev, n->next);
        --size_;
        int tmp = n->data;
        delete n;
        
        return tmp;
    }
    
    int size() const {
        return size_;
    }
};

class LRUCache {
public:
    LRUCache(int capacity): sizeLimit_(capacity), cache_(1e4 + 2) {
    }
    
    int get(int key) {
        auto& pack = cache_[key];
        if (pack.node == nullptr) {
            return -1;
        }
        
        queue_.nodeToHead(pack.node);
        return pack.value;
    }
    
    void put(int key, int value) {
        auto& pack = cache_[key];
        if (pack.node != nullptr) {
            queue_.nodeToHead(pack.node);
            pack.value = value;
            return;
        }

        pack.node = queue_.pushHead(key);
        pack.value = value;
        
        if (queue_.size() > sizeLimit_) {
            int removeKey = queue_.popTail();
            cache_[removeKey].node = nullptr;
        }
    }

private:
    int sizeLimit_;
    LinkList queue_;
    
    struct Pack {
        Node* node = nullptr;
        int value;
    };
    
    vector<Pack> cache_;
};

std::list

class LRUCache {
public:
    LRUCache(int capacity) : sizeLimit_(capacity), cache_(1e4 + 2) {
    }

    int get(int key) {
        auto& pack = cache_[key];
        if (pack.null) {
            return -1;
        }

        // move node to front
        queue_.erase(pack.node);
        queue_.push_front(key);
        pack.node = queue_.begin();

        return pack.value;
    }

    void put(int key, int value) {
        auto& pack = cache_[key];
        if (!pack.null) {
            // move node to front
            queue_.erase(pack.node);
            queue_.push_front(key);
            pack.node = queue_.begin();

            pack.value = value;
            return;
        }

        queue_.push_front(key);
        pack.node = queue_.begin();
        pack.value = value;
        pack.null = false;

        if (queue_.size() > sizeLimit_) {
            int removeKey = queue_.back();
            queue_.pop_back();
            cache_[removeKey].null = true;
        }
    }

private:
    int sizeLimit_;
    list<int> queue_;

    struct Pack {
        bool null = true;
        list<int>::iterator node;
        int value;
    };

    vector<Pack> cache_;
};

Changelog

Last edited about 1 month ago

View full history

1096e02-Add oj solving