題目

請?jiān)O(shè)計(jì)實(shí)現(xiàn)一個(gè)最近最少使用（Least Recently Used，LRU）緩存，要求如下兩個(gè)操作的時(shí)間復(fù)雜度都是O（1）。

• get（key）：如果緩存中存在鍵key，則返回它對應(yīng)的值；否則返回-1。
• put（key，value）：如果緩存中之前包含鍵key，則它的值設(shè)為value；否則添加鍵key及對應(yīng)的值value。在添加一個(gè)鍵時(shí)，如果緩存容量已經(jīng)滿了，則在添加新鍵之前刪除最近最少使用的鍵（緩存中最長時(shí)間沒有被使用過的元素）。

分析

哈希表HashMap的get操作和put操作的時(shí)間復(fù)雜度都是O（1），但普通的哈希表無法找出最近最少使用的鍵，因此，需要在哈希表的基礎(chǔ)上進(jìn)行改進(jìn)。

由于需要知道緩存中最近最少使用的元素，因此可以把存入的元素按照訪問的先后順序存入鏈表中。每次訪問一個(gè)元素（無論是通過get操作還是通過put操作），該元素都被移到鏈表的尾部。這樣，位于鏈表頭部的元素就是最近最少使用的。

下面考慮如何實(shí)現(xiàn)把一個(gè)節(jié)點(diǎn)移到鏈表的尾部。這實(shí)際上包含兩個(gè)步驟，首先要把節(jié)點(diǎn)從原來的位置刪除，然后把它添加到鏈表的尾部。需要注意的是，在鏈表中刪除一個(gè)節(jié)點(diǎn)，實(shí)際上是把它的前一個(gè)節(jié)點(diǎn)的next指針指向它的下一個(gè)節(jié)點(diǎn)。如果這個(gè)鏈表是單向鏈表，那么找到一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)需要從鏈表的頭節(jié)點(diǎn)開始順序掃描每個(gè)節(jié)點(diǎn)，也就需要O（n）的時(shí)間。

為了快速找到一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)從而實(shí)現(xiàn)用O（1）的時(shí)間刪除一個(gè)節(jié)點(diǎn)，可以用雙向鏈表來存儲緩存中的元素。在雙向鏈表中查找一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)只需要順著prev指針向前走一步，時(shí)間復(fù)雜度為O（1）。

因此，設(shè)計(jì)最近最少使用緩存需要結(jié)合哈希表和雙向鏈表的特點(diǎn)。哈希表的鍵就是緩存的鍵，哈希表的值為雙向鏈表中的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都是一組鍵與值的數(shù)對。

解

public class Test {public static void main(String[] args) {LRUCache lruCache = new LRUCache(4);lruCache.put(1,1);lruCache.put(2,2);lruCache.put(3,3);lruCache.put(4,4);ListNode node1 = lruCache.head;while (node1 != null){System.out.println(node1.value);node1 = node1.next;}System.out.println("-------------------------");lruCache.get(2);ListNode node2 = lruCache.head;while (node2 != null){System.out.println(node2.value);node2 = node2.next;}System.out.println("-------------------------");lruCache.put(1,8);ListNode node3 = lruCache.head;while (node3 != null){System.out.println(node3.value);node3 = node3.next;}System.out.println("-------------------------");lruCache.put(5,5);ListNode node4 = lruCache.head;while (node4 != null){System.out.println(node4.value);node4 = node4.next;}}static class ListNode{public int key;public int value;public ListNode next;public ListNode prev;public ListNode(int k,int v){key = k;value = v;}}static class LRUCache{private ListNode head;private ListNode tail;private Map<Integer,ListNode> map;int capacity;public LRUCache(int cap){map = new HashMap<>();head = new ListNode(-1,-1);tail = new ListNode(-1,-1);head.next = tail;tail.prev = head;capacity = cap;}public int get(int key){ListNode node = map.get(key);if (node == null){return -1;}moveToTail(node,node.value);return node.value;}public void put(int key,int value){if (map.containsKey(key)){moveToTail(map.get(key),value);}else {if (map.size() == capacity){ListNode toBeDeleted = head.next;deleteNode(toBeDeleted);map.remove(toBeDeleted.key);}ListNode node = new ListNode(key,value);intsertToTail(node);map.put(key,node);}}private void moveToTail(ListNode node,int newValue){deleteNode(node);node.value = newValue;intsertToTail(node);}private void deleteNode(ListNode node){node.prev.next = node.next;node.next.prev = node.prev;}private void intsertToTail(ListNode node){tail.prev.next = node;node.prev = tail.prev;node.next = tail;tail.prev = node;}}
}