题解 | #设计LRU缓存结构#

int cap;
int used = 0;
typedef struct {
// write code here
    int key;
    int value;
} Solution;

Solution* SolutionCreate(int capacity) {
// write code here
    Solution* obj = (Solution*)malloc(sizeof(Solution) * capacity);
    cap = capacity;
    return obj;
}

int SolutionGet(Solution* obj, int key) {
// write code here
    for(int i = 0; i < used; i++) {
        if(obj[i].key == key) {
            int tempvalue = obj[i].value;
            for(int j = i; j < used - 1; j++) {
                obj[j] = obj[j + 1];
            }
            obj[used - 1].key = key;
            obj[used - 1].value = tempvalue;
            return tempvalue;
        }
    }
    return -1;
}

void SolutionPut(Solution* obj, int key, int value) {
// write code here
    bool found = false;
// 首先判断是否已经存在
    for (int i = 0; i < used; i++) {
        //如果存在，将值更新
        if (obj[i].key == key) {
            found = true;
            for (int j = i; j < used - 1; j++) {
                obj[j] = obj[j + 1];
            }
            obj[used - 1].key = key;
            obj[used - 1].value = value;
            printf("update key %d value %d\n", key, value);
        }
    }
    //如果没有
    if (!found) {
// 如果还有剩余空间
        if (used < cap) {
            Solution new;
            new.key = key;
            new.value = value;
            obj[used] = new;
            used++;
            printf("(1)set key %d value %d\n", key, value);
        } else { // 如果没有剩余空间
            printf("delete key %d value %d\n", obj[0].key, obj[0].value);
            int i = 0;
            for(; i < used - 1; i++) {
                obj[i] = obj[i + 1];
            }
            obj[i].key = key;
            obj[i].value = value;
            printf("(2)set key %d value %d\n", key, value);
        }
    }

}

void SolutionFree(Solution* obj) {
// write code here
    free(obj);
}
/**
 * Your Solution struct will be instantiated and called as such:
 * Solution* obj = SolutionCreate(capacity);
 * int param_1 = SolutionGet(obj, key);
 * SolutionPut(obj, key, value);
 * SolutionFree(obj);
*/