Pure C code solution...


  • 1
    V

    // Fixed a bug and now accepted.
    // I guess this code should be very native as it it in C, not much people use C here.

    struct kvlist {
    int key;
    int val;
    struct kvlist *knext;
    struct kvlist *rprev;
    struct kvlist *rnext;
    };

    struct {
    int kf;
    int sz;
    int idx;
    struct kvlist **kp;
    struct kvlist *buff;
    struct kvlist *head;
    struct kvlist *tail;
    } hash;

    void lruCacheInit(int capacity) {
    int i;

    hash.kf = 1024 * 10;
    hash.kp = calloc(hash.kf, sizeof(struct kvlist *));
    hash.sz = capacity;
    hash.buff = calloc(hash.sz, sizeof(struct kvlist));
    hash.idx = 0;
    
    hash.head = &hash.buff[0];
    hash.tail = &hash.buff[hash.sz - 1];
    hash.head->rprev = hash.tail;
    hash.tail->rnext = hash.head;
    i = 0;
    while (i < hash.sz) {
        if (i != 0) {
            hash.buff[i].rprev = &hash.buff[i - 1];
        }
        if (i != hash.sz - 1) {
            hash.buff[i].rnext = &hash.buff[i + 1];
        }
        i ++;
    }
    

    }

    void lruCacheFree() {
    free(hash.kp);
    free(hash.buff);
    }

    struct kvlist *lookup(int key) {
    struct kvlist *l;

    l = hash.kp[key % hash.kf];
    while (l && l->key != key) {
        l = l->knext;
    }
    
    return l;
    

    }

    void move2tail(struct kvlist *l) {
    l->rprev->rnext = l->rnext;
    l->rnext->rprev = l->rprev;
    if (hash.head == l) hash.head = l->rnext;
    if (hash.tail == l) hash.tail = l->rprev;
    hash.head->rprev = l;
    hash.tail->rnext = l;
    l->rprev = hash.tail;
    l->rnext = hash.head;
    hash.tail = l;
    }

    int lruCacheGet(int key) {
    int val;
    struct kvlist *l;

    l = lookup(key);
    
    if (!l) return -1;
    
    val = l->val;
    
    move2tail(l);
    
    return val;
    

    }

    void lruCacheSet(int key, int value) {
    int i;
    struct kvlist *l, **pp;

    l = lookup(key);
    if (!l) {
        l = hash.head;
        i = l->key % hash.kf;
        pp = &hash.kp[i];
        while (*pp && *pp != l) {
            pp = &(*pp)->knext;
        }
        if (*pp) *pp = l->knext;
        else hash.kp[i] = NULL;
        
        l->key = key;
        i = key % hash.kf;
        l->knext = hash.kp[i];
        hash.kp[i] = l;
    }
    
    l->val = value;
    
    move2tail(l);
    

    }


  • 0
    V

    @vli02
    Runtime 26 ms, beats 86.67% in c submission.
    Is it cool?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.