請你設計并實現一個滿足??LRU (最近最少使用) 緩存?約束的數據結構。
實現?LRUCache?類：
LRUCache(int capacity)?以?正整數?作為容量?capacity?初始化 LRU 緩存int get(int key)?如果關鍵字?key?存在于緩存中，則返回關鍵字的值，否則返回?-1?。void put(int key, int value)?如果關鍵字?key?已經存在，則變更其數據值?value?；如果不存在，則向緩存中插入該組?key-value?。如果插入操作導致關鍵字數量超過?capacity?，則應該?逐出?最久未使用的關鍵字。
函數?get?和?put?必須以?O(1)?的平均時間復雜度運行。
示例：
輸入 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 輸出 [null, null, null, 1, null, -1, null, -1, 3, 4]解釋 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 緩存是 {1=1} lRUCache.put(2, 2); // 緩存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 該操作會使得關鍵字 2 作廢，緩存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 該操作會使得關鍵字 1 作廢，緩存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4
思路：這道題的難點在于記錄最近最少使用，使用map可以滿足get的O(1)，但是無法記錄最近最少使用的數據；如果使用數組，刪除/增加的時間復雜度則是O(n)，也不滿足。
使用哈希表 + 雙向鏈表可以滿足刪除/增加的時間復雜度為O(1)。
這個圖太形象了。
（1）雙向鏈表按照被使用的順序存儲了這些鍵值對，靠近頭部的鍵值對是最近使用的，而靠近尾部的鍵值對是最久未使用的。
（2）哈希表即為普通的哈希映射（HashMap），通過緩存數據的鍵映射到其在雙向鏈表中的位置。
（3）對于 get 操作，首先判斷 key 是否存在：
????????（a）如果 key 不存在，則返回 ?1；
????????（b）如果 key 存在，則 key 對應的節點是最近被使用的節點。通過哈希表定位到該節點在雙向鏈表中的位置，并將其移動到雙向鏈表的頭部，最后返回該節點的值。
（3）對于 put 操作，首先判斷 key 是否存在：
????????（a）如果 key 不存在，使用 key 和 value 創建一個新的節點，在雙向鏈表的頭部添加該節點，并將 key 和該節點添加進哈希表中。然后判斷雙向鏈表的節點數是否超出容量，如果超出容量，則刪除雙向鏈表的尾部節點，并刪除哈希表中對應的項；
????????（b）如果 key 存在，則與 get 操作類似，先通過哈希表定位，再將對應的節點的值更新為 value，并將該節點移到雙向鏈表的頭部。
思路很清晰
class LRUCache {
public:LRUCache(int capacity) {}int get(int key) {}void put(int key, int value) {}
};/*** 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);*/一步步實現：
（1）定義雙鏈表
struct DLinkedNode {int key, value; // k-vDLinkedNode* prev; // 前向指針DLinkedNode* next; // 后向指針// 兩個構造函數DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};（2）在LRUCache類中添加成員屬性：哈希表+雙向鏈表
class LRUCache {
public:// 新加的unordered_map<int, DLinkedNode*> cache;DLinkedNode* head; // 偽頭節點，不存數據DLinkedNode* tail; // 偽尾節點，不存數據int size; // 當前存儲的數量，當size==capacity時，要移出數據了int capacity; // 容量// 實現構造函數LRUCache(int _capacity): capacity(_capacity), size(0) {// 使用偽頭節點和偽尾節點，不存數據head = new DLinkedNode();tail = new DLinkedNode();// 開始時一個數據都沒有head->next = tail;tail->prev = head;}int get(int key) {}void put(int key, int value) {}
};（3）實現雙向鏈表中的【在頭部添加數據】、【任意位置刪除數據】、【數據移動到頭部】、【從尾部刪除數據】
在頭部添加數據
// 在頭部添加數據void addToHead(DLinkedNode* node) {node->prev = head;node->next = head->next;head->next->prev = node;head->next = node;}
任意位置刪除數據
// 任意位置刪除數據void removeNode(DLinkedNode* node) {node->prev->next = node->next;node->next->prev = node->prev;}
數據移動到頭部
// 移動數據到頭部void moveToHead(DLinkedNode* node) {removeNode(node);addToHead(node);}從尾部刪除數據
// 從尾部刪除數據DLinkedNode* reoveTail() {DLinkedNode* node = tail->prev;removeNode(node);return node;}（4）實現get函數
如果不存在直接返回-1，存在的話，先通過哈希表定位，再移動到頭部
int get(int key) {// 不存在if (cache.count(key) == 0) {return -1;}// 通過哈希找到，移動到頭部DLinkedNode* node = cache[key];moveToHead(node);return node->value;}（5）實現put函數
如果key不存在，則創建一個節點，注意size==capacity的情況，此時刪除隊尾數據
靠近頭部的鍵值對是最近使用的，而靠近尾部的鍵值對是最久未使用的。
如果存在，修改value，再將該節點移動到隊頭
void put(int key, int value) {// 不存在if (cache.count(key) == 0) {DLinkedNode* node = new DLinkedNode(key, value);cache[key] = node; // 添加到哈希表中addToHead(node); // 移動到隊頭size++;if (size > capacity) {DLinkedNode* removeNode = reoveTail(); // 刪除尾部數據cache.erase(removeNode->key); // 刪除哈希中的數據delete removeNode;size--; }} else {DLinkedNode* node = cache[key];node->value = value;moveToHead(node); // 移到隊頭}}全部代碼實現
struct DLinkedNode {int key, value; // k-vDLinkedNode* prev; // 前向指針DLinkedNode* next; // 后向指針// 兩個構造函數DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};class LRUCache {
public:unordered_map<int, DLinkedNode*> cache;DLinkedNode* head;DLinkedNode* tail;int size;int capacity;LRUCache(int _capacity): capacity(_capacity), size(0) {// 使用偽頭節點和偽偽節點，不存數據head = new DLinkedNode();tail = new DLinkedNode();// 開始時一個數據都沒有head->next = tail;tail->prev = head;}int get(int key) {// 不存在if (cache.count(key) == 0) {return -1;}// 通過哈希找到，移動到頭部DLinkedNode* node = cache[key];moveToHead(node);return node->value;}void put(int key, int value) {// 不存在if (cache.count(key) == 0) {DLinkedNode* node = new DLinkedNode(key, value);cache[key] = node; // 添加到哈希表中addToHead(node); // 移動到隊頭size++;if (size > capacity) {DLinkedNode* removeNode = reoveTail(); // 刪除尾部數據cache.erase(removeNode->key); // 刪除哈希中的數據delete removeNode;size--; }} else {DLinkedNode* node = cache[key];node->value = value;moveToHead(node); // 移到隊頭}}// 在頭部添加數據void addToHead(DLinkedNode* node) {node->prev = head;node->next = head->next;head->next->prev = node;head->next = node;}// 任意位置刪除數據void removeNode(DLinkedNode* node) {node->prev->next = node->next;node->next->prev = node->prev;}// 移動數據到頭部void moveToHead(DLinkedNode* node) {removeNode(node);addToHead(node);}// 從尾部刪除數據DLinkedNode* reoveTail() {DLinkedNode* node = tail->prev;removeNode(node);return node;}};/*** 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);*/參考：【字節一面】 LRU Cache 實現剖析_嗶哩嗶哩_bilibili
鏈接：. - 力扣（LeetCode）
利用Spring的jdbc實現學生管理系統的用戶登錄功能)
)
