LeetCode 146 LRU Cache

    
        标签：
        
            设计数据结构
        
            LeetCode
        
    发布于：2022-02-10 12:39:48
    编辑于：2022-02-10 14:42:48
    浏览量：804

概述

https://leetcode.com/problems/lru-cache/

get 和 put 操作要求 O(1) 的平均时间复杂度。

注意是 Least Recently Used，而非 Least Frequency Used。

直接法

一个 map 存键值对，一个双向列表存 key 的访问顺序，另一个 map 存键与列表中元素节点的迭代器的对应关系。

记得 put 更新值时也要更新 key 的访问顺序。

下面这个 TLE 了，解决方法是 evit 操作中不要新建变量就好了，即：

void evict() {
    cache.erase(keyList.back());
    pointer.erase(keyList.back());
    keyList.pop_back();
}

class LRUCache {
public:
    int capacity;
    list<int> lru;
    unordered_map<int, int> cache;
    unordered_map<int, list<int>::iterator> pointer;
    LRUCache(int capacity) {
        this->capacity = capacity;
    }
    
    int get(int key) {
        if (cache.count(key) == 0) return -1;
        promote(key);
        return cache[key];
    }
    
    void put(int key, int value) {
        // First check if we have this key already.
        if (cache.count(key) == 0) {  // We don't have this key
            // So we have to put a new key here.
            // Check if we have enough space:
            if (lru.size() == capacity) {  // Don't have space now
                // Remove the least used item
                evict();
            }  
            // Have available space
            cache[key] = value;
            lru.push_front(key);
            pointer[key] = lru.begin();
        } else {  // We have this key
            cache[key] = value;
            promote(key);
        }
    }
    
    void promote(int key) {
        // Move this item to front
        lru.erase(pointer[key]);  // Step 1: delete it from the list
        lru.push_front(key);  // Step 2: put it back to the front
        pointer[key] = lru.begin();  // Step 3: update pointer
    }
    
    void evict() {
        auto key = lru.back();
        lru.pop_back();
        cache.erase(key);
        pointer.erase(key);
    }
};

Links: leetcode-146-lru-cache