LeetCode 146 LRU Cache

Tag: 设计数据结构 LeetCode Posted on 2022-02-10 12:39:48 Edited on 2022-02-10 14:42:48 Views: 180

概述

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);
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/