[146] LRU Cache (TBC)

神秘！！！
竟然又過了!!!
當然效能並不是太好
但似先這樣就好XD
我這個人最不強求了！！！
（問題是別人要求呀哭哭XD）

設計一個 LRU Cache
讓先被insert進去的會最先被取代
如果它有被touch過, 則時間要更新
另外key可以改掉value , 也就是key 1 可以先設個2 , 再 key 1 設個 3,
這時get key 1會得到3而不是2 (感覺很像廢話 XD）
TBC here~ 大概要弄個 first in first out的 queue
讓時間最前面的在head (或linked list）
降子拿掉的時候只要 O(1)
不過時間更新的時候需要重排(麻煩XD)
又似乎需要弄個hash again
（假裝沒看見題目上寫的: Could you do both operations in O(1) time complexity?)
反正今天先這樣XD 收工!

LRU Cache
typedef struct {
    int key;
    int value;
    int time;
} LRUCache;
static unsigned int size = 0;
static unsigned long time = 0;
LRUCache* lRUCacheCreate(int capacity) {
    size = capacity;
    LRUCache* myCache = malloc (sizeof (LRUCache) * capacity);
    for(int i=0;i<size;i++)
    {
        myCache[i].key = -1;
    }
    return myCache;
}

int lRUCacheGet(LRUCache* obj, int key) {
    for(int i=0;i<size;i++)
    {
        if(obj[i].key == key)
        {
            obj[i].time = time++;
            return obj[i].value;
        }
    }
    return -1;
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    int time_min = INT_MAX;
    int drop_index = -1;
    for(int i=0;i<size;i++)
    {
        if(obj[i].key < 0 || obj[i].key == key)
        {
            obj[i].key = key;
            obj[i].value = value;
            obj[i].time = time++;
            return;
        }
        else if (time_min > obj[i].time)
        {
            time_min = obj[i].time;
            drop_index = i;
        }
    }

    obj[drop_index].key = key;
    obj[drop_index].value = value;
    obj[drop_index].time = time++;
 
}

void lRUCacheFree(LRUCache* obj) {
    free(obj);
}

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