Leetcode每日一题-146（5.25-java版本）
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
方法一：
比较暴力直接用LinkedHashMap。
class LRUCache {
LinkedHashMap<Integer,Integer> map = new LinkedHashMap<>();
int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
if(!map.containsKey(key))
return -1;
int res = map.get(key);
map.remove(key);
map.put(key,res);
return res;
}
public void put(int key, int value) {
if(map.containsKey(key)){
map.remove(key);
map.put(key,value);
return;
}
if(capacity==0){
map.remove(map.entrySet().iterator().next().getKey());
}else{
capacity--;
}
map.put(key,value);
}
} 方法二：
方法二采用双向链表 加 hashmap，hashmap中存储（key，node），双向链表的尾部代表新加入的节点，头部表示可能过期的节点。
class LRUCache {
HashMap<Integer,Node>map = new HashMap<>();
int capacity;
Node head,tail;
class Node{
int key,value;
Node pre,next;
public Node(int key,int value){
this.key = key;
this.value = value;
}
}
//节点加入队列末尾
public void add(Node node){
node.next = tail;
node.pre = tail.pre;
tail.pre.next = node;
tail.pre = node;
}
//删除当前节点
public void del(Node node){
node.pre.next = node.next;
node.next.pre = node.pre;
}
public LRUCache(int capacity) {
this.capacity = capacity;
head = new Node(0,0);
tail = new Node(0,0);
head.next = tail;
tail.pre = head;
}
public int get(int key) {
Node node = map.get(key);
if(node == null)
return -1;
if(node.next != tail){
del(node);
add(node);
}
return node.value;
}
public void put(int key, int value) {
Node temp =map.get(key);
if(temp!=null){
if(temp.next != tail){
del(temp);
temp.value = value;
map.put(key,temp);
add(temp);
return;
}
tail.pre.value = value;
return;
}
if(capacity==0){
Node node1 = head.next;
map.remove(node1.key);
del(node1);
}else{
capacity--;
}
Node node = new Node(key,value);
map.put(key,node);
add(node);
}
} 
美团开奖213人在聊
投递百度等公司10个岗位