【C语言刷LeetCode】146. LRU 缓存(M)

【

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类： LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4]

解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4

提示：

1 <= capacity <= 3000 0 <= key <= 10000 0 <= value <= 105 最多调用 2 * 105 次 get 和 put

】

UTHASH上场，直接抛开obj不用，来个全局变量hash

任何操作都把时间更新一下，然后存入或更新时间。

当发现存入的节点达到最大值，则用HASH_ITER遍历哈希表，找到时间最小的，然后再遍历哈希找到这个节点，并HASH_DEL删除它，最后把最新的节点存入。

这道题用到了HASH_FIND_INT，HASH_ADD_INT，HASH_ITER，HASH_DEL，HASH_CLEAR。

typedef struct {
    int key;
    int val;
    int time;
    UT_hash_handle hh;
} LRUCache;

int cap;
int num;
int ntime;
LRUCache* myhash;

LRUCache* lRUCacheCreate(int capacity) {
    myhash = NULL;
    cap = capacity;
    num = 0;
    ntime = 0;
    return myhash;
}

int lRUCacheGet(LRUCache* obj, int key) {
    LRUCache* find = NULL;
    ntime++;
    HASH_FIND_INT(myhash, &key, find);
    if (find == NULL) {
        printf("h0,get:key=%d
",key);
        return -1;
    } else {
        find->time = ntime;
        printf("h1,get:key=%d,val=%d
",key,find->val);
        return find->val;
    }
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    LRUCache* find = NULL;
    ntime++;
    HASH_FIND_INT(myhash, &key, find);
    if (find != NULL) {
        find->val = value;
        find->time = ntime;
        printf("h1,put:(%d:%d)
",key, value);
        return;
    }

    LRUCache* new = (LRUCache* )malloc(sizeof(LRUCache));
    new->key = key;
    new->val = value;
    new->time = ntime;
    if (num < cap) {
        HASH_ADD_INT(myhash, key, new);
        num++;
        printf("h2,put:(%d:%d)
",key, value);
    } else {
        LRUCache *cur, *tmp;
        int mint = INT_MAX;
        HASH_ITER(hh, myhash, cur, tmp) {
            mint = fmin(cur->time, mint);
        }

        HASH_ITER(hh, myhash, cur, tmp) {
            if (cur->time == mint) {
                HASH_DEL(myhash, cur);
                break;
            }
        }
        HASH_ADD_INT(myhash, key, new);
    }
}

void lRUCacheFree(LRUCache* obj) {
    HASH_CLEAR(hh, myhash);
}

/*
注意点：
1. 用了全局遍历 myhash，后面都基于myhash操作，原因是因为用obj，get时候总是找不到。
2. 用到了 HASH_ITER 遍历
3. 用到了 HASH_DEL(hh, cur)删除节点

*/