LRU 缓存(LRU Cache)

设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。

它应该支持以下操作：获取数据 get 和写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

示例:

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

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

自己实现一个简单的缓存

struct Entry{
    int key;
    int value;
    int priority;
};

typedef struct {
    struct Entry* entries;
    int capacity;
    // 越大代表越新
    int currentPriority;
} LRUCache;


LRUCache* lRUCacheCreate(int capacity) {
    LRUCache* obj = malloc(sizeof(LRUCache));
    obj->entries = calloc(capacity, sizeof(struct Entry));
    obj->capacity = capacity;
    obj->currentPriority = 0;
    for(int i = 0;i <capacity; i++){
        obj->entries[i].key = -1;
    }
    return obj;
}

int lRUCacheGet(LRUCache* obj, int key) {
    for(int i =0;i < obj->capacity;i++){
        if(obj->entries[i].key == key){
            obj->currentPriority++;
            obj->entries[i].priority = obj->currentPriority;
            return obj->entries[i].value;;
        }
    }
    return -1;
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    // 存在 key
    for(int i =0;i< obj->capacity; i++){
        if(obj->entries[i].key == key) {
            obj->entries[i].value = value;

            obj->currentPriority++;
            obj->entries[i].priority = obj->currentPriority;
            return;
        }
    }

    // 不存在这个key 且不满
    for(int i =0;i<obj->capacity;i++){
        if(obj->entries[i].key == -1){
            obj->entries[i].key = key;
            obj->entries[i].value = value;

            obj->currentPriority++;
            obj->entries[i].priority = obj->currentPriority;
            return;
        }
    }

    // 不存在这个key，且缓存满了
    int minIndex = 0;
    for(int i =1;i < obj->capacity; i++){
        if(obj->entries[i].priority < obj->entries[minIndex].priority){
            minIndex = i;
        }
    }

    obj->entries[minIndex].key = key;
    obj->entries[minIndex].value = value;

    obj->currentPriority++;
    obj->entries[minIndex].priority = obj->currentPriority;
    return;

}

void lRUCacheFree(LRUCache* obj) {
    free(obj->entries);
    free(obj);
}

/**
 * Your LRUCache struct will be instantiated and called as such:
 * LRUCache* obj = lRUCacheCreate(capacity);
 * int param_1 = lRUCacheGet(obj, key);
 
 * lRUCachePut(obj, key, value);
 
 * lRUCacheFree(obj);
*/

key初始化为-1不能省，给的key 有可能是0….

也可以用队列实现，从对头取出，取出后再塞回队尾，妙