1.題目描述

2.思路

LRU(最近最少使用）：如果緩存的容量為2，剛開始的兩個元素都入棧。之后該2元素中有其中一個元素（重點元素）被訪問。把最近訪問過的重點元素保留，另一個邊緣元素就得離開緩存了。

下面是leetcode思路：

總結：
（1）創建一個哈希表和雙向鏈表。鏈表頭部是最近剛使用過的元素，尾部是最近不經常使用的元素。
（2）put（），首先如果新加入的元素在哈希表中不存在，則直接創建新節點加入到map中。如果雙向鏈表的節點數超過鏈表容量，則剔除尾部節點（包括它的值）。如果新加入的元素存在（key存在），我們通過get進行定位，把節點值進行更新，移動到頭部（說明是最近剛被訪問的）
（3）get（），如果get（key）不存在直接返回-1，如果key存在，說明key節點是最近被使用的節點。通過哈希表定位到雙向鏈表的位置，并將其移動到雙向鏈表的頭部，返回該節點的值。

3.代碼實現

class LRUCache {class doubleLinkedNode{int key;int value;doubleLinkedNode prev;doubleLinkedNode next;public doubleLinkedNode() {}public doubleLinkedNode(int key, int value) {this.key = key;this.value = value;}}private Map<Integer,doubleLinkedNode> cache=new HashMap<Integer,doubleLinkedNode>();private int size;private int capacity;private doubleLinkedNode head;private doubleLinkedNode tail;public LRUCache(int capacity) {this.size=0;this.capacity=capacity;//使用偽頭部和偽尾部節點head=new doubleLinkedNode();tail=new doubleLinkedNode();head.next=tail;tail.prev=head;}public int get(int key) {doubleLinkedNode node=cache.get(key);if(node==null){return -1;}//如果key存在，通過哈希表定位，再移動到頭部moveToHead(node);return node.value;}public void put(int key, int value) {doubleLinkedNode node=cache.get(key);if(node==null){//2.如果key不存在，則創建一個新的節點doubleLinkedNode newNode=new doubleLinkedNode(key,value);//添加到哈希表cache.put(key,newNode);//添加到雙向鏈表的頭部addToHead(newNode);size++;// 如果添加的數量超出容量if(size>capacity){//超出容量，說明要刪除雙向鏈表的尾部節點doubleLinkedNode tail=removeTail();//刪除哈希表中對應的項，刪尾部節點對應的key值cache.remove(tail.key);size--;}}else{//如果key存在，先通過哈希表定位，再修改value，并移動到頭部node.value=value;moveToHead(node);}}private void addToHead(doubleLinkedNode node){node.prev=head;node.next=head.next;head.next.prev=node;head.next=node;}private void removeNode(doubleLinkedNode node){node.prev.next=node.next;node.next.prev=node.prev;}private void moveToHead(doubleLinkedNode node){removeNode(node);addToHead(node);}private doubleLinkedNode removeTail(){doubleLinkedNode res=tail.prev;removeNode(res);return res;}
}/*** 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);*/