Leetcode LRU缓存,数组+结构体实现

一、算法思路

LRUCache类有以下函数和变量:

  • LRUCache(int capacity): capacity是当前对象能够存储的键值对(key,value)最大个数。
  • int get(int key): 根据指定的key寻找value值,若没有找到key就返回-1
  • void put(int key, int value): 存储一个新的键值对(key,value),如果key已经存在,就更新value,如果当前已达最大容量,就将最近最少使用的键值对替换。
  • void show(): 查看当前所有键值对信息。(题目并没有要求书写这个函数,只是为了方便调试)。
  • int size: 当前所存储的键值对个数。
  • int max_size: 最大键值对个数(对应构造函数的capacity)。
  • Node *list:键值对数组。

Node结构体的定义:

typedef struct LRUCacheNode {
    int key;
    int value;
    int count;
} Node;

其中key,value构成了键值对(key,value),count表示已有多久没有使用。当一个键值对节点(Node)被第一次插入、查询或是修改,其count都会被置零,而其他节点的count自增。已达到最大存储量后,插入节点会修改所有节点中count最大的,修改完毕(也就是value值被更新后),count会被置零,而其他节点的count依然会自增。

二、代码演示

LRUCache(int capacity) {
        max_size = capacity;
        size = 0;
        list = new Node[max_size];
}

LRUCache的构造函数仅仅初始化max_size,size和list。三者的定义如下:

private:
    int size;
    int max_size;
    Node *list;

接下来是get函数,比较简单,依次遍历list并寻找符合要求的节点,不要忘记将符合要求的节点的count置零,以及将其他节点的count自增:

int get(int key) {
        int value = -1;
        for (int i = 0; i < size; ++i) {
            Node *tmp = &list[i];
            if (tmp->key == key) {
                tmp->count = 0;
                value = tmp->value;
            } else {
                tmp->count++;
            }
        }
        return value;
}

接下来说重点——put函数:

void put(int key, int value) {
        bool contains = false;
        for (int i = 0; i < size; ++i) {
            Node *tmp = &list[i];
            if (tmp->key == key) {
                tmp->count = 0;
                tmp->value = value;
                contains = true;
            } else {
                tmp->count++;
            }
        }

        if (contains) { return; }

        if (size >= max_size) {
            int max_count = -1;
            Node *max_node;
            for (int i = 0; i < size; ++i) {
                Node *tmp = &list[i];
                if (tmp->count > max_count) {
                    max_count = tmp->count;
                    max_node = tmp;
                }
            }
            max_node->key = key;
            max_node->value = value;
            max_node->count = 0;
        } else {
            Node n;
            n.key = key;
            n.value = value;
            n.count = 0;
            list[size++] = n;
        }
}

 put函数首先在list中寻找(key,value)是否存在,是则仅更新节点并返回。如果没有找到节点,接下来判断list是否已满:如果没有满,就将(key,value)存储到list数组;如果已经满了,首先根据count大小,寻找出count最大的节点,将其修改(此步并不需要将其他节点count自增,因为在第一步寻找(key,value)是否存在是已经自增过了)。

接下来是show函数,可以自行调整样式:

void show() {
        for (int i = 0; i < size; ++i) {
            Node *tmp = &list[i];
            cout << tmp->key << "\t" << tmp->value << "\t" << tmp->count << "\n";
        }
}

main函数调试:

int main() {
    LRUCache cache = LRUCache(2 /* 缓存容量 */ );
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << "\n";       // 返回  1
    cache.put(3, 3);    // 该操作会使得密钥 2 作废
    cout << cache.get(2) << "\n";       // 返回 -1 (未找到)
    cache.put(4, 4);    // 该操作会使得密钥 1 作废
    cout << cache.get(1) << "\n";       // 返回 -1 (未找到)
    cout << cache.get(3) << "\n";       // 返回  3
    cout << cache.get(4) << "\n";       // 返回  4

    return 0;
}

main函数输出:

1
-1
-1
3
4

三、提交结果

Leetcode LRU缓存,数组+结构体实现

 

 执行用时并不理想,有待优化。

发表评论

相关文章