目錄
- 大概思路
- 時間空間復雜度分析
- 指針操作具體細節
- 代碼
- 雙向鏈表設計
- 私有成員變量設計:
- 構造函數和析構函數設計：
- get與put具體設計
- 雙向指針的具體細節
- 添加到頭節點函數
- 刪除尾節點函數
- 刪除節點函數
- 刪除節點函數
- 感想
今天面試考到LRU，太緊張了，完全傻了。。。趕緊做個記錄
LRU是Least Recently Used的縮寫，即最近最少使用，是一種常用的頁面置換算法，選擇最近最久未使用的頁面予以淘汰。
LRU 緩存：
設計和構建一個“最近最少使用”緩存，該緩存會刪除最近最少使用的項目。緩存應該從鍵映射到值(允許你插入和檢索特定鍵對應的值)，并在初始化時指定最大容量。當緩存被填滿時，它應該刪除最近最少使用的項目。
它應該支持以下操作： 獲取數據 get 和 寫入數據 put 。
獲取數據 get(key) - 如果密鑰 (key) 存在于緩存中，則獲取密鑰的值（總是正數），否則返回 -1。
寫入數據 put(key, value) - 如果密鑰不存在，則寫入其數據值。當緩存容量達到上限時，它應該在寫入新數據之前刪除最近最少使用的數據值，從而為新的數據值留出空間。
示例:
LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 該操作會使得密鑰 2 作廢
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 該操作會使得密鑰 1 作廢
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
大概思路
這一題面試官說用到雙向鏈表和哈希map。
雙向鏈表按照被使用的順序存儲了這些鍵值對，靠近頭部的鍵值對是最近使用的，而靠近尾部的鍵值對是最久未使用的。
哈希表，通過緩存數據的鍵映射到其在雙向鏈表中的位置。
注意雙向鏈表中存儲的元素是key, value;
哈希表中存儲的是key和雙向鏈表節點。
太緊張了，導致一開始都不知道map的value具體含義，還以為是頻率計數用的。。。其實并無特殊含義，僅僅是一個值。
get操作：
1、判斷key是否存在，不存在返回-1
2、如果存在，返回該節點值并且將對應的節點移動到雙向鏈表的頭部。
put操作：
1、判斷key是否存在
2、key不存在，使用key和value創建一個新的節點，然后在雙向鏈表頭部插入這個鍵值對。
3、將 key 和該節點添加進哈希表中。
4、判斷雙向鏈表的節點數是否超出容量，如果超出容量，則刪除雙向鏈表的尾部節點，并刪除哈希表中對應的項；
5、key存在。先通過哈希表定位，再將對應的節點的值更新為 value，并將該節點移到雙向鏈表的頭部。
時間空間復雜度分析
訪問哈希表的時間復雜度為 O(1）
在雙向鏈表頭和尾部增減節點時間復雜度也是O(1)
指針操作具體細節
將一個節點移動到頭部可以分為：
1、刪除該節點
2、在頭節點前插入一個相同的節點
還有就是虛擬頭節點和虛擬尾節點是使用：
添加節點和刪除節點的時候就就比較方便了，這個在單向鏈表的設計中也有涉及：
707. 設計鏈表
下面給出具體的代碼：
代碼
雙向鏈表設計
關于雙向鏈表節點的定義
class DLinkedNode {//存儲鍵、值int key, value;//定義兩個指針，一個指向前一個節點，一個指向下一個節點DLinkedNode* 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) {}
};關于LRUCache類的設計：
私有成員變量設計:
private://哈希表unordered_map<int, DLinkedNode*> cache;//虛擬頭指針和虛擬尾指針DLinkedNode* head;DLinkedNode* tail;//當前LRUCache中元素(鍵值對)個數int size;//LRUCache最多能容納多少鍵值對int capacity;
構造函數和析構函數設計：
構造函數：
這里給出最大容量，我們還需要初始化size的大小和主動添加虛擬頭指針和虛擬尾指針，并將兩者鏈接起來
LRUCache(int capacity) {_capacity = capacity;_size = 0;dummyhead = new DLinkedNode();dummytail = new DLinkedNode();dummyhead->next = dummytail;dummytail->prev = dummyhead;}
析構函數：
主要是將兩個虛擬頭節點和虛擬尾節點釋放掉
~LRUCache() {delete head;delete tail;}
get與put具體設計
get函數：
int get(int key)
{//如果找不到，返回-1if(chache.find(key) == chache.end()){return -1;}//如果key存在//哈希定位DLinkedNode* node = chache[key];//將該節點添加到雙向鏈表頭部moveHead(node);//返回該節點值return node->value;
}
put函數：
void put(int key, int value)
{//如果key不存在，創建一個新節點if(cache.find(key) == cache.end()){//如果預計超出容量，刪除雙向鏈表尾部節點if(size + 1 > capacity){//刪除雙向鏈表尾部節點DLinkedNode* deleted_node = deleteTail();//刪除哈希表中對應部分cache.erase(deleted_node->key);delete deleted_node;size--;}DLinkedNode* node = new DLinkedNode(key,value);chache[key] = node;//將該節點添加到雙向鏈表頭部addHead(node);size++;}//如果key存在，通過哈希定位，修改value，移動到頭部else{DLinkedNode* node = chache[key];node->value = value;moveHead}
}
雙向指針的具體細節
添加到頭節點函數
void addHead(DLinkedNode* node)
{//雙向指針操作 + 虛擬頭節點node->prev = head;node->next = head->next;head->next->prev = node;head->next = node;
}
刪除尾節點函數
DLinkedNode* deleteTail()
{//尾節點是虛擬tail前面一個。DLinkedNode* node = tail->prev;deleteNode(node);return node;
}
刪除節點函數
指針繞來繞去。。。面試沒寫出來。。。
void deleteNode(DLinkedNode* node)
{node->prev->next = node->next;node->next->prev = node->prev;
}
刪除節點函數
void moveHead(DLinkedNode* node)
{//先刪除當前節點deleteNode(node);//然后將它加入頭部addHead(node);
}
感想
第一次面試，還是太緊張了，說話都說不利索。
關鍵還是指針鏈表操作的繁瑣。。。沒想到面試會考這題。。
這一題和實際應用關聯較大，而且是設計題，比較考研綜合能力。
構造函數和雙向鏈表的定義都得自己寫，雙向鏈表我平時用到的不是很多，還得多加練習。
為了面試，晚飯都沒吃。。。
面試官聲音好聽，態度也很溫和，像個鄰家大哥哥，面完我還要再去面下一個，一個人一個小時，感覺也挺累的。
)
