Qmonster吃喝玩樂大事記: 2024

#define MAX_KEYS 10001

struct myNode{
    int key;
    int val;
    struct myNode *next;
    struct myNode *pre;
};

typedef struct {
    struct myNode *head;
    struct myNode *tail;
    int size;
    int count;
    struct myNode *queue[MAX_KEYS];
} LRUCache;

void debugPrint(LRUCache* obj)
{
printf("===debugPrint===\n");
    struct myNode *ptr= obj->head;
    while (ptr != NULL)
    {
        printf("key %d val %d\n",ptr->key, ptr->val);
        ptr = ptr->next;
    }
printf("===End debugPrint===\n");
}

LRUCache* lRUCacheCreate(int capacity) {
    LRUCache* LRU = calloc (1, sizeof (LRUCache));
    LRU-> size= capacity;
    LRU-> count = 0;
    LRU->head = NULL;
    LRU->tail = NULL;
    return LRU;
}

void addqueue(LRUCache* obj, int key, int value) {
    obj->queue[key] = calloc (1 , sizeof (struct myNode));
    obj->queue[key]-> pre = obj->tail;
    obj->queue[key]-> next = NULL;
    if (obj->tail != NULL)
        obj->tail->next = obj->queue[key];
    obj->tail = obj->queue[key];
    obj->queue[key]->val = value;
    obj->queue[key]->key = key;
    if (obj->head == NULL)
        obj->head = obj->queue[key];
    obj->count ++;

}

void removequeue(LRUCache* obj, int key) {
    struct myNode *ptr= obj->queue[key];
    struct myNode *ptr_pre = obj->queue[key]->pre;
    struct myNode *ptr_next = obj->queue[key]->next;
    if (ptr_pre == NULL)//head
    {
        obj->head = ptr_next;
        if (ptr_next != NULL)
            ptr_next->pre = NULL;
    }
    else
        ptr_pre->next = ptr_next;
    
    if (ptr_next == NULL) // tail
    {
        obj->tail = ptr_pre;
        if (ptr_pre != NULL)
            ptr_pre->next = NULL;
    }
    else
        ptr_next->pre = ptr->pre;

    ptr_pre=NULL;
    ptr_next = NULL;
    obj->queue[key] = NULL;
    free (obj->queue[key]);
    obj->count --;
}

int lRUCacheGet(LRUCache* obj, int key) {
    if (obj->queue[key] == NULL)
        return -1;

    int value = obj->queue[key]->val;
    removequeue(obj,key);
    addqueue(obj,key, value);
    return obj->queue[key]->val;
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    if (obj->queue[key]!= NULL)
        removequeue(obj,key);
    else if (obj->count == obj-> size)
        removequeue(obj,obj->head->key);

    addqueue(obj,key, value);
//debugPrint(obj);
}

void lRUCacheFree(LRUCache* obj) {
    for (int i=0; i< MAX_KEYS; i++)
        free(obj->queue[i]);
    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);
*/

2024年2月19日 星期一

2024年2月18日 星期日

2024年2月16日 星期五

2024年2月7日 星期三

2024年2月2日 星期五

2024年1月29日 星期一

2024年1月28日 星期日

2024年1月27日 星期六

2024年1月17日 星期三

2024年1月15日 星期一

2024年2月19日星期一

2024年2月18日星期日

2024年2月16日星期五

2024年2月7日星期三

2024年2月2日星期五

2024年1月29日星期一

2024年1月28日星期日

2024年1月27日星期六

2024年1月17日星期三

2024年1月15日星期一