运用你所掌握的数据结构，设计和实现一个  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

看到这道题，我首先想到的是采用LinkedHashMap去做，可能自己太菜，LinkedHashMap中没有找到自己直接能用的方法😭

只能采用下面的HashMap + 双向循环链表来实现了： 

注意：

1、get方法也会改变优先级

2、set方法注意满和不满，存在不存在四种

import java.util.HashMap;
import java.util.Map;class LRUCache {// 想在O(1)时间段内完成get操作，那必须是map结构// 想在put时删除最后结点为O(1)操作，插入在头节点处，那必须是linkedlist结构// 单一结构无法实现，建立类class Node{Node(int val1, int val2){this.val1 = val1;this.val2 = val2;};// 自身的值int val1, val2;// 前驱后继Node pre, next;}Map<Integer, Node> map;int size ;int len;Node first;Node last;public LRUCache(int capacity) {map = new HashMap<>();size = capacity;first = new Node(-1, -1);last = new Node(-1, -1);first.next = last;last.pre = first;size = capacity;len = 0;}public int get(int key) {// get也会改变优先级if(map.containsKey(key)){Node node = map.get(key);node.next.pre = node.pre;node.pre.next = node.next;// 删除map.remove(key);// 插入头节点node.next = first.next;first.next.pre = node;first.next = node;node.pre = first;map.put(key, node);return map.get(key).val2;}else {return -1;}}public void put(int key, int value) {// 如果存在if(map.containsKey(key)){map.get(key).next.pre = map.get(key).pre;map.get(key).pre.next = map.get(key).next;map.remove(key);// 直接插入头部Node node = new Node(key, value);node.next = first.next;first.next.pre = node;first.next = node;node.pre = first;map.put(key, node);}else {// 如果不存在if(len < size){// 直接插入头部Node node = new Node(key, value);node.next = first.next;first.next.pre = node;first.next = node;node.pre = first;len += 1;map.put(key, node);}else {// 如果满了map.remove(last.pre.val1);last.pre.pre.next = last;last.pre = last.pre.pre;// 直接插入头部Node node = new Node(key, value);node.next = first.next;first.next.pre = node;first.next = node;node.pre = first;map.put(key, node);}}}public static void main(String[] args) {LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );cache.put(1, 1);cache.put(2, 2);System.out.println(cache.get(1));       // 返回  1cache.put(3, 3);    // 该操作会使得关键字 2 作废System.out.println(cache.get(2));       // 返回 -1 (未找到)cache.put(4, 4);    // 该操作会使得关键字 1 作废System.out.println(cache.get(1));       // 返回 -1 (未找到)System.out.println(cache.get(3));       // 返回  3System.out.println(cache.get(4));       // 返回  4}
}