题解 | #设计LRU缓存结构(非 o(1) 查找)#

整体思路是：

1. 使用双向链表数据结构来存储 LRU，结构如下：

   typedef struct LRU_LIST_NODE {
    int key, value;
    struct LRU_LIST_NODE *prev, *next;
   } LRU_LIST_NODE_t;

   typedef struct {
    LRU_LIST_NODE_t *head;   /* point to the oldest node */
    LRU_LIST_NODE_t *tail;   /* point to the latest node */
    int node_cnt;            /* node count */
    int max_node_num;        /* k */
   } LRU_LIST;

   head 的 next 指针指向 oldest 节点，即每次淘汰的时候，淘汰 head->next;
   tail 的 prev 指针指向 latest 节点，即每次更新操作后，将更新的节点放到 tail->prev

2. 分别定义如下的 API：

   void LRU_INIT(LRU_LIST *list, int k);                      /* 初始化 cache list */ 
   LRU_LIST_NODE_t* LRU_SEARCH(LRU_LIST *list, int key);      /* 查找 key 对应的 ndoe */
   void LRU_UPDATE(LRU_LIST *list, LRU_LIST_NODE_t *node);    /* 更新 node 到最新 */
   int LRU_SET(LRU_LIST* list, int key, int value);           /* 插入 key, value */
   int LRU_GET(LRU_LIST* list, int key);                      /* 获取 key 对应的 value */                 

下面是项目代码, 有些变量在牛客网下面如果编译不通过，修改下即可

typedef struct LRU_LIST_NODE {
    int key, value;
    struct LRU_LIST_NODE *prev, *next;
} LRU_LIST_NODE_t;


typedef struct {
    LRU_LIST_NODE_t *head;   /* point the oldest node */
    LRU_LIST_NODE_t *tail;   /* point the latest node */
    int node_cnt;            /* node count */
    int max_node_num;        /* k */
} LRU_LIST;


LRU_LIST_NODE_t* LRU_SEARCH(LRU_LIST *list, int key) {
    LRU_LIST_NODE_t *h = list->head->next;
    while (h != list->tail) {
        if (h->key == key) {
            return h;
        }

        h = h->next;
    }

    return NULL;
}


/* adjust the node to the tail */
void LRU_UPDATE(LRU_LIST *list, LRU_LIST_NODE_t *node) {
    if (list->node_cnt == 1) {
        return;
    }

    /* remove this node first */
    LRU_LIST_NODE_t *p = node->prev;
    p->next = node->next;
    node->next->prev = p;

    /* then, insert to the tail */
    LRU_LIST_NODE_t *ori_latest_node = list->tail->prev;
    ori_latest_node->next = node;

    node->prev = ori_latest_node;
    node->next = list->tail;
    list->tail->prev = node;
}


int LRU_SET(LRU_LIST* list, int key, int value) {
    LRU_LIST_NODE_t *node = LRU_SEARCH(list, key);
    if (node != NULL) {
        node->value = value;
        /* update */
        LRU_UPDATE(list, node);

        return 0;
    }

    /* insert */
    if (list->node_cnt == list->max_node_num) {
        /* delete the oldest if list is full */
        LRU_LIST_NODE_t *oldest_node = list->head->next;
        list->head->next = oldest_node->next;
        oldest_node->next->prev = list->head;
        free(oldest_node);
    }

    LRU_LIST_NODE_t *new_node = (LRU_LIST_NODE_t *)malloc(sizeof(LRU_LIST_NODE_t));
    if (new_node == NULL) {
        return -1;
    }

    new_node->key = key;
    new_node->value = value;

    /* insert to the latest */
    LRU_LIST_NODE_t *ori_latest = list->tail->prev;
    ori_latest->next = new_node;
    list->tail->prev = new_node;
    new_node->next = list->tail;
    new_node->prev = ori_latest;

    /* 坑 1 */
    if (list->node_cnt != list->max_node_num) {
        list->node_cnt++;
    }

    return 0;
}


int LRU_GET(LRU_LIST* list, int key) {
    LRU_LIST_NODE_t *node = LRU_SEARCH(list, key);
    if (node == NULL) {
        return -1;
    }

    LRU_UPDATE(list, node);

    return node->value;
}


void LRU_INIT(LRU_LIST *list, int k) {
    list->max_node_num = k;
    list->head = (LRU_LIST_NODE_t *)malloc(sizeof(LRU_LIST_NODE_t));
    list->tail = (LRU_LIST_NODE_t *) malloc (sizeof(LRU_LIST_NODE_t));

    list->head ->next = list->tail;
    list->head->prev = NULL;

    list->tail->next = NULL;
    list->tail->prev = list->head;

    list->node_cnt = 0;
}


/* parse operator */
int judgeOps(int *operator, int operatorCplen) {
    if (operator[0] == 1 && operatorCplen == 3) {
        return 0;
    }

    if (operator[0] == 2 && operatorCplen == 2) {
        return 0;
    }

    return -1;
}


LRU_LIST list;
int LRU_RES[102400];

int* LRU(int** operators, int operatorsRowLen, int* operatorsColLen, int k, int* returnSize) {
    // write code here

    if (list.max_node_num != k) {
        LRU_INIT(&list, k);
    }

    *returnSize = 0;

    for (int i = 0; i < operatorsRowLen; i++) {
        int *ope = operators[i];
        int opeLen = operatorsColLen[i];

        if (judgeOps(ope,  opeLen) != 0) {
            return LRU_RES;
        }

        if (ope[0] == 1) {
            LRU_SET(&list, ope[1], ope[2]);
        } else {
            LRU_RES[*returnSize] = LRU_GET(&list, ope[1]);
            (*returnSize)++;
        }
    }

    return LRU_RES;
}