leetcode 146. LRU Cache

这道题的算法，是android里面常用来做图片缓存的算法lrucache的简化版本

简单的来说呢，就是维护一个LinkedHashMap。这种map的结构如下，map自带前后两个指针

static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } }

先确定map的大小，然后当map满了，就删除map中链表头部的节点，当有任何节点被更新或者读取，就将它移动到map链表的尾部

public class LRUCache { LinkedHashMap<Integer,Integer> map=new LinkedHashMap<>(); int size=0; int headkey=-1; public LRUCache(int capacity) { this.size=capacity; } public int get(int key) { if(map.containsKey(key)){ int ret=map.get(key); if(key==this.headkey){ int value=map.get(key); map.remove(key); map.put(key,value); this.headkey= map.entrySet().iterator().next().getKey(); }else{ int value=map.get(key); map.remove(key); map.put(key,value); } return ret; } return -1; } public void put(int key, int value) { if(size==0) return; if(map.size()==0){ map.put(key,value); this.headkey=key; }else if(map.size()<size&&map.size()>0){ if(map.containsKey(key)) { map.remove(key); map.put(key,value); this.headkey= map.entrySet().iterator().next().getKey(); }else{ map.put(key,value); } }else{ if(map.containsKey(key)) { map.remove(key); map.put(key,value); this.headkey= map.entrySet().iterator().next().getKey(); }else{ int temp=this.headkey; map.remove(temp); map.put(key,value); this.headkey= map.entrySet().iterator().next().getKey(); } } } }