运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
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
解题思路：
LRU ：最近最少使用
在Java语言中，LinkedList是一种常用的数据容器，并且LinkeList实现了list和Deque接口，所以具备列表操作和双向队列的能力，如API：
增
public boolean add(E e)，链表末尾添加元素，返回是否成功；
public void add(int index, E element)，向指定位置插入元素；
public boolean addAll(Collection<? extends E> c)，将一个集合的所有元素添加到链表后面，返回是否成功；
public boolean addAll(int index, Collection<? extends E> c)，将一个集合的所有元素添加到链表的指定位置后面，返回是否成功；
public void addFirst(E e)，添加到第一个元素；
public void addLast(E e)，添加到最后一个元素；
public boolean offer(E e)，向链表末尾添加元素，返回是否成功；
public boolean offerFirst(E e)，头部插入元素，返回是否成功；
public boolean offerLast(E e)，尾部插入元素，返回是否成功；
删
public void clear()，清空链表；
public E removeFirst()，删除并返回第一个元素；
public E removeLast()，删除并返回最后一个元素；
public boolean remove(Object o)，删除某一元素，返回是否成功；
public E remove(int index)，删除指定位置的元素；
public E poll()，删除并返回第一个元素；
public E remove()，删除并返回第一个元素；
查
public boolean contains(Object o)，判断是否含有某一元素；
public E get(int index)，返回指定位置的元素；
public E getFirst(), 返回第一个元素；
public E getLast()，返回最后一个元素；
public int indexOf(Object o)，查找指定元素从前往后第一次出现的索引；
public int lastIndexOf(Object o)，查找指定元素最后一次出现的索引；
public E peek()，返回第一个元素；
public E element()，返回第一个元素；
public E peekFirst()，返回头部元素；
public E peekLast()，返回尾部元素；
改
public E set(int index, E element)，设置指定位置的元素；
所以我们可以借助LinkedList列表操作和HashMap查找的特性来实现LRU
(ps: java 存在api：LinkedHashMap可以认为是HashMap+LinkedList，即它既使用HashMap操作数据结构，又使用LinkedList维护插入元素的先后顺序)。
显然使用HashMap+LinkedList或者LinkedHashMap能够很容易解答该题，但是直接使用语言自带API并不是该题的初衷，所以我们要模仿LinkedHashMap：
1.HashMap,用来存储key和链表节点，方便后续查询操作
2.双向链表，方便节点的操作，如增删改。
综上，代码如下：
class LRUCache {
private int capacity;
private int count;
private Map<Integer,Node> map = new HashMap<Integer,Node>();
//定义头尾伪节点，这样在添加和删除节点时不需要判断相邻节点是否存在问题
private Node head;
private Node tail;
public LRUCache(int capacity) {
this.capacity = capacity;
this.count = 0;
head = new Node();
tail = new Node();
head.next = tail;
tail.pre = head;
}
public int get(int key) {
Node node = map.get(key);
if(node == null)
{
return -1;
}
removeNode(node);
moveToHead(node);
return node.val;
}
public void put(int key, int value) {
Node node = map.get(key);
if(node != null)
{
node.val = value;
removeNode(node);
moveToHead(node);
}else
{
Node newNode = new Node(key,value);
//容量已满，需要删除尾部节点（其实是倒数第二个节点）
if(count == capacity)
{
int tailKey = removeTail(tail);
map.remove(tailKey);
}else{
count++;
}
moveToHead(newNode);
map.put(key,newNode);
}
}
public void removeNode(Node node)
{
node.pre.next = node.next;
node.next.pre = node.pre;
}
//将node添加到头结点（其实是插入到head伪节点之后）
public void moveToHead(Node node)
{
Node second = head.next; //获取真正的head节点
head.next = node;
node.pre = head;
node.next = second;
second.pre = node;
}
//删除尾结点（倒数第二个节点才是真正的尾结点）
public int removeTail(Node node)
{
Node pre = tail.pre;
removeNode(pre);
return pre.key;
}
/**
* 自定义双向链表
*/
class Node
{
public Node pre;
public Node next;
public int key;
public int val;
//默认无参构造
public Node()
{
}
//有参构造
public Node(int key,int val)
{
this.key = key;
this.val = val;
}
}
}
网友评论