【每日打卡】[leetcode]460-LFU缓存

马谦马谦马谦

615
文章

17
评论

2020年4月5日17:00:11数据结构和算法评论3241字数 848阅读2分49秒阅读模式

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/lfu-cache

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get和put。

get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。

进阶：

你是否可以在 O(1) 时间复杂度内执行两项操作？

示例：

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

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1
cache.put(3, 3);    // 去除 key 2
cache.get(2);       // 返回 -1 (未找到key 2)
cache.get(3);       // 返回 3
cache.put(4, 4);    // 去除 key 1
cache.get(1);       // 返回 -1 (未找到 key 1)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

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

cache.put(1, 1);

cache.put(2, 2);

cache.get(1); // 返回 1

cache.put(3, 3); // 去除 key 2

cache.get(2); // 返回 -1 (未找到key 2)

cache.get(3); // 返回 3

cache.put(4, 4); // 去除 key 1

cache.get(1); // 返回 -1 (未找到 key 1)

cache.get(3); // 返回 3

cache.get(4); // 返回 4

二、题目解析

LFU算法是LRU算法的改进版本，LRU算法强调最近最少使用，逐步淘汰掉很久没有使用的缓存。而LFU在LRU的基础上引入了使用频率限制，优先使用频率来淘汰缓存。在频率同等的情况下，再通过LRU淘汰较久没有使用的。

虽然只是增加了一个维度的判断，但是在逻辑和编码上，多出来的麻烦就不止一个档次了。因为题目要求在O(1)的时间复杂度内完成两项操作。对于get操作而言，如果使用哈希表来保存所有的缓存节点，可以在O(1)的时间复杂度完成。但是对于put操作来说，想要把它在O(1)的时间复杂度内插入，就不简单了，必须要有合适的数据结构来支撑才行，因为除了保存频次以外还有记录节点的使用时间。如果像LRU一样使用链表来存，每个缓存节点都要先找到合适的位置才能插入，时间复杂度是O(n)。

这里可以采取的方式是使用两个哈希表来保存所有的节点，其中一个以缓存的key值作为哈希表的key，另外一个以缓存出现的频率作为哈希表的key。假设保存所有缓存节点的哈希表为cache，保存频率的哈希表为freq，那么它的操作逻辑为：

【每日打卡】[leetcode]460-LFU缓存

三、代码

// 缓存节点
struct cacheNode {
    int key, val, freq; // 键
};

class LFUCache {
private:
    unordered_map<int, list<cacheNode *>> freq; // 保存所有频次的节点
    unordered_map<int, cacheNode *> cache; // 保存所有的缓存节点
    int min; // 出现最小的频次
    int capacity; // 容量
    int size; // 大小

    void incrFreq(unordered_map<int, cacheNode *>::iterator &itCache) {
        cacheNode *node;
        unordered_map<int, list<cacheNode *> >::iterator itFreq;

        node = itCache->second;

        // 找到对应频率的链表
        itFreq = freq.find(node->freq);
        if (itFreq == freq.end())
            throw logic_error("unexpect error: cannot file list in freq map");

        // 从当前链表移除
        itFreq->second.remove(node);
        if (itFreq->second.empty()) {
            freq.erase(node->freq);
            // 当前删除的节点是最小频率节点
            if (node->freq == min)
                min++;
        }

        // 增加频率
        node->freq++;
        itFreq = freq.find(node->freq);
        if (itFreq == freq.end()) {
            freq.insert(pair<int, list<cacheNode *>>(node->freq, list<cacheNode *>()));
            itFreq = freq.find(node->freq);
        }

        itFreq->second.push_front(node);
    }

    // 添加新节点
    void putNewNode(int key, int value) {
        cacheNode *node, *p;
        unordered_map<int, cacheNode *>::iterator itCache;
        unordered_map<int, list<cacheNode *> >::iterator itFreq;

        if (this->size == this->capacity) {
            // 缓存容量上限了，到使用频率最低的删除最近最少使用
            itFreq = freq.find(min);
            if(itFreq == freq.end()) // 这里必须要有节点，否则异常
                throw logic_error("unexpect error: cannot find list in min freq map");

            if (itFreq->second.empty()) // 链表的节点数量不为0
                throw logic_error("unexpect error: min freq list is empty");

            node = itFreq->second.back();
            // 弹出最近最少使用的，先清除缓存列表中的
            cache.erase(node->key);
            // 然后清除频率表中的
            itFreq->second.pop_back();
            if (itFreq->second.empty()) {
                // 如果列表中的元素删完了，完全移除key
                freq.erase(min);
            }
            this->size--;
        } else {
            node = new cacheNode;
        }
        // 给node节点赋值
        min = node->freq = 1;
        node->key = key;
        node->val = value;
        // 先插入到以频率为key的哈希表
        itFreq = freq.find(min);
        if(itFreq == freq.end()) { // 这里可能是不存在对应节点的，如果不存在，创建一个节点
            freq.insert(pair<int, list<cacheNode *>>(min, list<cacheNode *>()));
            itFreq = freq.find(min);
        }
        itFreq->second.push_front(node);
        // 然后插入到缓存哈希表
        cache.insert(pair<int, cacheNode*>(key, node));
        this->size++;
    }

    // 插入已经存在的节点
    void putExistNode(int key, int value, unordered_map<int, cacheNode *>::iterator &itCache) {
        cacheNode *node;
        unordered_map<int, list<cacheNode *> >::iterator itFreq;

        // 找到了对应的缓存，更新缓存的value，然后把频率加一
        node = itCache->second;
        node->val = value;

        incrFreq(itCache);
    }
public:
    LFUCache(int capacity) {
        this->size = 0;
        this->min = 0;
        this->capacity = capacity;
    }

    int get(int key) {
        cacheNode *node;
        unordered_map<int, cacheNode *>::iterator itCache;
        unordered_map<int, list<cacheNode *> >::iterator itFreq;

        if (capacity == 0)
            return -1;

        itCache = cache.find(key);
        if (itCache == cache.end()) // 没有找到对应的cache，直接返回
            return -1;

        incrFreq(itCache);
        return itCache->second->val;
    }

    void put(int key, int value) {
        cacheNode *node;
        unordered_map<int, cacheNode *>::iterator itCache;
        unordered_map<int, list<cacheNode *> >::iterator itFreq;

        if (capacity == 0)
            return;

        itCache = cache.find(key);
        if (itCache == cache.end()) {
            // 插入新值
            putNewNode(key, value);
        } else {
            // 更新旧值
            putExistNode(key, value, itCache);
        }
    }
};

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

// 缓存节点

struct cacheNode {

int key, val, freq; // 键

};

class LFUCache {

private:

unordered_map<int, list<cacheNode *>> freq; // 保存所有频次的节点

unordered_map<int, cacheNode *> cache; // 保存所有的缓存节点

int min; // 出现最小的频次

int capacity; // 容量

int size; // 大小

void incrFreq(unordered_map<int, cacheNode *>::iterator &itCache) {

cacheNode *node;

unordered_map<int, list<cacheNode *> >::iterator itFreq;

node = itCache->second;

// 找到对应频率的链表

itFreq = freq.find(node->freq);

if (itFreq == freq.end())

throw logic_error("unexpect error: cannot file list in freq map");

// 从当前链表移除

itFreq->second.remove(node);

if (itFreq->second.empty()) {

freq.erase(node->freq);

// 当前删除的节点是最小频率节点

if (node->freq == min)

min++;

}

// 增加频率

node->freq++;

itFreq = freq.find(node->freq);

if (itFreq == freq.end()) {

freq.insert(pair<int, list<cacheNode *>>(node->freq, list<cacheNode *>()));

itFreq = freq.find(node->freq);

}

itFreq->second.push_front(node);

}

// 添加新节点

void putNewNode(int key, int value) {

cacheNode *node, *p;

unordered_map<int, cacheNode *>::iterator itCache;

unordered_map<int, list<cacheNode *> >::iterator itFreq;

if (this->size == this->capacity) {

// 缓存容量上限了，到使用频率最低的删除最近最少使用

itFreq = freq.find(min);

if(itFreq == freq.end()) // 这里必须要有节点，否则异常

throw logic_error("unexpect error: cannot find list in min freq map");

if (itFreq->second.empty()) // 链表的节点数量不为0

throw logic_error("unexpect error: min freq list is empty");

node = itFreq->second.back();

// 弹出最近最少使用的，先清除缓存列表中的

cache.erase(node->key);

// 然后清除频率表中的

itFreq->second.pop_back();

if (itFreq->second.empty()) {

// 如果列表中的元素删完了，完全移除key

freq.erase(min);

}

this->size--;

} else {

node = new cacheNode;

}

// 给node节点赋值

min = node->freq = 1;

node->key = key;

node->val = value;

// 先插入到以频率为key的哈希表

itFreq = freq.find(min);

if(itFreq == freq.end()) { // 这里可能是不存在对应节点的，如果不存在，创建一个节点

freq.insert(pair<int, list<cacheNode *>>(min, list<cacheNode *>()));

itFreq = freq.find(min);

}

itFreq->second.push_front(node);

// 然后插入到缓存哈希表

cache.insert(pair<int, cacheNode*>(key, node));

this->size++;

}

// 插入已经存在的节点

void putExistNode(int key, int value, unordered_map<int, cacheNode *>::iterator &itCache) {

cacheNode *node;

unordered_map<int, list<cacheNode *> >::iterator itFreq;

// 找到了对应的缓存，更新缓存的value，然后把频率加一

node = itCache->second;

node->val = value;

incrFreq(itCache);

}

public:

LFUCache(int capacity) {

this->size = 0;

this->min = 0;

this->capacity = capacity;

}

int get(int key) {

cacheNode *node;

unordered_map<int, cacheNode *>::iterator itCache;

unordered_map<int, list<cacheNode *> >::iterator itFreq;

if (capacity == 0)

return -1;

itCache = cache.find(key);

if (itCache == cache.end()) // 没有找到对应的cache，直接返回

return -1;

incrFreq(itCache);

return itCache->second->val;

}

void put(int key, int value) {

cacheNode *node;

unordered_map<int, cacheNode *>::iterator itCache;

unordered_map<int, list<cacheNode *> >::iterator itFreq;

if (capacity == 0)

return;

itCache = cache.find(key);

if (itCache == cache.end()) {

// 插入新值

putNewNode(key, value);

} else {

// 更新旧值

putExistNode(key, value, itCache);

}

};

【每日打卡】[leetcode]460-LFU缓存

一、题目描述

二、题目解析

三、代码

[leetcode]226-翻转二叉树

[leetcode]887-鸡蛋掉落

【每日打卡】[leetcode]695-岛屿的最大面积

105-从前序与中序遍历序列构造二叉树

POJ1220-NUMBER BASE CONVERSION（任意进制转换）

[leetcode]199-二叉树的右视图

【每日打卡】[leetcode]72-编辑距离

[leetcode]125-验证回文串

【每日打卡】[程序员面试宝典]17.16-按摩师

【每日打卡】[leetcode]876-链表的中间节点

【每日打卡】[剑指offer]面试题40-最小的k个数

【每日打卡】[leetcode]-409最长回文子串

【每日打卡】[leetcode]面试题1.6-字符串压缩

【每日打卡】[leetcode]695-岛屿的最大面积

加载中...

发表评论

热门搜索

一、题目描述

二、题目解析

三、代码

发表评论