Untitled
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