题目描述
分析
1. 双向链表+map
put(): a. 首次添加k和v，会新建节点，添加到双向链表的头结点处(头插法)，将k和节点的引用存到map中； b. 若不是首次插入，则通过map找到节点的引用，修改节点的值，再将此节点移到头结点； c. 若容量慢了，则删除尾节点
get(): 要达到O(1)，即直接从map中获取，并且此节点移到头结点处
代码实现
public enum Q146 {
instance;
static class LRUCache {
// save k and v
LinkedNode head;
LinkedNode tail;
// save k and LinkedNode's point
Map<Integer,LinkedNode> map;
int capacity;
// Linked's size
int length;
public LRUCache(int capacity) {
if(capacity<=0) throw new Error("capacity is illegal");
this.capacity=capacity;
this.map=new HashMap<>(capacity);
this.head=new LinkedNode();
this.tail=new LinkedNode();
// init head and tail
head.next=tail;
head.prev=null;
tail.prev=head;
tail.next=null;
}
public int get(int key) {
if(map.containsKey(key)){
LinkedNode node = map.get(key);
moveToHead(node);
return node.val;
}
return -1;
}
private void moveToHead(LinkedNode node) {
if(node==null||node.prev==head) return;
LinkedNode prevNode=node.prev;
prevNode.next=node.next;
node.next.prev=prevNode;
node.next=head.next;
node.prev=head;
head.next.prev=node;
head.next=node;
}
public void put(int key, int value) {
if(map.containsKey(key)){
LinkedNode node = map.get(key);
node.val=value;
moveToHead(node);
return;
}
if(length>=capacity){
LinkedNode removedNode = removeLast();
if(removedNode!=null){
map.remove(removedNode.key);
}
}
map.put(key,addFist(key,value));
}
private LinkedNode addFist(int key,int value){
LinkedNode newNode=new LinkedNode(key,value);
newNode.next=head.next;
newNode.prev=head;
head.next.prev=newNode;
head.next=newNode;
length++;
return newNode;
}
private LinkedNode removeLast(){
if(tail==null||tail.prev==null) return null;
LinkedNode node=tail.prev.prev;
if(node!=null){
LinkedNode removeNode=tail.prev;
node.next=tail;
tail.prev=node;
length--;
return removeNode;
}
return null;
}
class LinkedNode {
public int key;
public int val;
public LinkedNode prev;
public LinkedNode next;
public LinkedNode(){}
public LinkedNode(int key,int val) {
this.key=key;
this.val = val;
}
}
}
// test
private void test1(){
LRUCache lruCache = new LRUCache(3);
lruCache.put(1,1);
lruCache.put(2,2);
lruCache.put(3,3);
System.out.println(lruCache.get(1));
// remove 2
lruCache.put(4,4);
// -1
System.out.println(lruCache.get(2));
lruCache.put(3,6);
// 6
System.out.println(lruCache.get(3));
}
private void test2(){
// 4->2
LRUCache lruCache = new LRUCache(2);
lruCache.put(2,1);
lruCache.put(1,1);
lruCache.put(2,3);
lruCache.put(4,1);
// -1
System.out.println(lruCache.get(1));
// 3
System.out.println(lruCache.get(2));
}
public static void main(String[] args) {
Q146.instance.test2();
}
}
