寫在前面

??最近想復(fù)習(xí)一下數(shù)據(jù)結(jié)構(gòu)與算法相關(guān)的內(nèi)容，找一些題來(lái)做一做。如有更好思路，歡迎指正。

---

---

一、場(chǎng)景描述

??運(yùn)用你所掌握的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)和實(shí)現(xiàn)一個(gè) LRU (Least Recently Used， 最近最少使用) 緩存機(jī)制。

它應(yīng)該支持以下操作，獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 。
1、獲取數(shù)據(jù) get(key)， 如果密鑰 (key) 存在于緩存中，則獲取密鑰的值（總是正數(shù)），否則返回 -1。
2、寫入數(shù)據(jù) put(key, value)， 如果密鑰不存在，則寫入其數(shù)據(jù)值，
當(dāng)緩存容量達(dá)到上限時(shí)，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最近最少使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

進(jìn)階:
你是否可以在 O(1) 時(shí)間復(fù)雜度內(nèi)完成這兩種操作？示例：
LRUCache cache = new LRUCache(2);// 緩存容量cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 該操作會(huì)使得密鑰 2 作廢
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 該操作會(huì)使得密鑰 1 作廢
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

---

二、具體步驟

1.環(huán)境說(shuō)明

名稱	說(shuō)明
IntelliJ IDEA	2019.2

2.雙向循環(huán)鏈表

以下簡(jiǎn)單畫(huà)了個(gè)圖，說(shuō)下雙向循環(huán)鏈表的基本結(jié)構(gòu)。

3.代碼

以下為Java版本實(shí)現(xiàn)：

/*** LRU* 雙向循環(huán)鏈表實(shí)現(xiàn)** @author qiuxianbao* @date 2024/02/14* @since ace_1.4.0_20240109*/
public class Lc146_LRU {public static void main(String[] args) {LRUCache cache = new LRUCache(2);cache.put(1, 1);System.out.println(cache);  // LRUCache{capacity=2, cacheMap.size=1, cacheMap={1=ListNode{key=1, value=1}}, dummy=ListNode{key=null, value=null}}cache.put(2, 2);System.out.println(cache);  // LRUCache{capacity=2, cacheMap.size=2, cacheMap={1=ListNode{key=1, value=1}, 2=ListNode{key=2, value=2}}, dummy=ListNode{key=null, value=null}}System.out.println(cache.get(1));  // 返回 1cache.put(3, 3);    // 該操作會(huì)使得密鑰 2 作廢System.out.println(cache);  // LRUCache{capacity=2, cacheMap.size=2, cacheMap={1=ListNode{key=1, value=1}, 3=ListNode{key=3, value=3}}, dummy=ListNode{key=null, value=null}}System.out.println(cache.get(2)); // 返回 -1 (未找到)cache.put(4, 4);    // 該操作會(huì)使得密鑰 1 作廢System.out.println(cache);  // LRUCache{capacity=2, cacheMap.size=2, cacheMap={3=ListNode{key=3, value=3}, 4=ListNode{key=4, value=4}}, dummy=ListNode{key=null, value=null}}System.out.println(cache.get(1)); // 返回 -1 (未找到)System.out.println(cache.get(3)); // 返回  3System.out.println(cache.get(4)); // 返回  4}/*** 思路:* 有 key 有 value，那么這個(gè)結(jié)點(diǎn)的 data有 int key, int value* 同時(shí)要具備很容易找到 頭部（每次添加或獲取時(shí)需要移動(dòng)的） 和 尾部（刪除） 節(jié)點(diǎn)* 因此，選擇雙向循環(huán)鏈表** 為了減少查找，可以借助于Map當(dāng)做緩存（快速獲取元素），用于表示實(shí)際容器大小* 還需要有一個(gè)LRU的大小 capacity，用于和實(shí)際容器大小 cacheMap.size 比較** put操作*      key存在，則更新 value，放到頭部*      否則，判斷是否超過(guò)容量*            超過(guò)，先刪除鏈表尾部元素，然后再新增，放到頭部*            否則，新增，放到頭部* get操作*      每次都更新當(dāng)結(jié)點(diǎn)到鏈表頭部** 不管是put，還是get，都保證頭部都是最新的節(jié)點(diǎn)** 定義 capacity，用于初始化存儲(chǔ)容量* 定義一個(gè) map 用于記錄元素，方便判斷是否存在以及根據(jù) key去獲取節(jié)點(diǎn)* 定義一個(gè) 雙向循環(huán)鏈表，方便獲取鏈表頭部/尾部元素，便于添加/刪除** 定義構(gòu)造函數(shù)，用于初始化數(shù)據(jù)包括dummy節(jié)點(diǎn)*/static class LRUCache {// LRU大小int capacity;// 緩存，方便獲取元素, size 就是元素實(shí)際的大小Map<Integer, ListNode> cacheMap;// 雙向循環(huán)鏈表// dummy.next就是 head 節(jié)點(diǎn)，dummy.prev就是 tail 節(jié)點(diǎn)private ListNode dummy;public LRUCache(int capacity) {this.capacity = capacity;this.cacheMap = new HashMap<>();// 空元素初始化this.dummy = new ListNode();this.dummy.prev = this.dummy;this.dummy.next = this.dummy;}/*** 放元素* 也移動(dòng)到頭部，空間不足時(shí)，從尾部刪除（需要有一個(gè)刪除操作）** @param k* @param val*/public void put(int k, int val) {ListNode existNode = cacheMap.get(k);if (existNode != null) {existNode.value = val;move2Head(existNode);} else {if (cacheMap.size() >= this.capacity) {// 刪除尾部結(jié)點(diǎn)ListNode tail = dummy.prev;delete(tail);// 刪除緩存cacheMap.remove(tail.key);}// 構(gòu)建新節(jié)點(diǎn)，添加到頭部ListNode listNode = new ListNode(k, val);add2Head(listNode);cacheMap.put(k, listNode);}}/*** 獲取元素* 時(shí)時(shí)移動(dòng)到頭部** @param k* @return*/public int get(int k) {int result = -1;ListNode listNode = cacheMap.get(k);if (listNode != null) {result = listNode.value;move2Head(listNode);}return result;}/*** 移動(dòng)到頭部* 先刪除，再添加** @param e*/private void move2Head(ListNode e) {delete(e);add2Head(e);}/*** 添加到頭部** @param e*/private void add2Head(ListNode e) {ListNode head = dummy.next;e.next = head;head.prev = e;e.prev = dummy;dummy.next = e;}/*** 刪除節(jié)點(diǎn)** @param e*/private void delete(ListNode e) {ListNode p = e.prev;ListNode n = e.next;p.next = n;n.prev = p;e.prev = null;e.next = null;}@Overridepublic String toString() {return "LRUCache{" +"capacity=" + capacity +", cacheMap.size=" + cacheMap.size() +", cacheMap=" + cacheMap +", dummy=" + dummy +'}';}/*** 雙向循環(huán)鏈表結(jié)構(gòu)*/class ListNode {// 數(shù)據(jù)Integer key;Integer value;// 前驅(qū)指針ListNode prev;// 后繼指針ListNode next;public ListNode() {}public ListNode(Integer key, Integer value) {this.key = key;this.value = value;}@Overridepublic String toString() {return "ListNode{" +"key=" + key +", value=" + value +'}';}}}}

---

寫在后面

??如果本文內(nèi)容對(duì)您有價(jià)值或者有啟發(fā)的話，歡迎點(diǎn)贊、關(guān)注、評(píng)論和轉(zhuǎn)發(fā)。您的反饋和陪伴將促進(jìn)我們共同進(jìn)步和成長(zhǎng)。