Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
2.4 kB
3
Indexable
Never
struct Node {
    int key;
    int value;
    Node* next;
    Node(int key_, int value_) {
        key = key_;
        value = value_;
        next = nullptr;
    }
};

class LRUCache {
public:
    int capacity;
    int length;
    Node* head;
    Node* tail;

    LRUCache(int capacity) {
        this->capacity = capacity;
        this->length = 0;
        this->head = nullptr;
        this->tail = nullptr;
    }
    
    int get(int key) {
        if (!this->head) return -1;

        if (key == this->tail->key) {
            return this->tail->value;
        }

        if (key == this->head->key) {
            int value = this->head->value;
            Node* temp = this->head->next;
            this->head->next = nullptr;
            this->tail->next = this->head;
            this->tail = this->tail->next;
            this->head = temp;
            return value;
        }

        Node* cur = this->head;
        while (cur->next) {
            if (cur->next->key == key) {
                int value = cur->next->value;
                Node* temp = cur->next->next;
                cur->next->next = nullptr;
                this->tail->next = cur->next;
                this->tail = this->tail->next;
                cur->next = temp;
                return value;
            }
            cur = cur->next;
        }

        return -1;
    }
    
    void put(int key, int value) {
        if (this->get(key)) {
            Node* cur = this->head;
            while (cur) {
                if (cur->key == key) {
                    cur->value = value;
                    return;
                }
                cur = cur->next;
            }
        }

        Node* node = new Node(key, value);
        if (this->length == 0) {
            this->head = node;
            this->tail = node;
        } else if (this->length < this->capacity) {
            this->tail->next = node;
            this->tail = this->tail->next;
        } else {
            this->tail->next = node;
            this->tail = this->tail->next;
            this->head = this->head->next;;
        }
        this->length++;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */
Leave a Comment