leetcode 146.LRU缓存

思路一：哈希表模拟

如果只用哈希表进行模拟的话，需要开辟两个哈希表进行存储，一个装入数据，一个是记录数据key放入的次数。

然后，可以结合操作系统中最近最久算法的那个实例操作进行模拟，但是时间复杂度会O（n），因此并不是这道题的最优解，并且会因为时间限制通过不了，可以通过这个模拟方法复习操作系统，并且提升代码能力。

class LRUCache {int volumn;Map<Integer,Integer>map;Map<Integer,Integer>count;int cnt=0;public LRUCache(int capacity) {this.volumn=capacity;map=new HashMap<>();count=new HashMap<>();}public int get(int key) {if(map.containsKey(key)){Set set=count.keySet();Iterator it=set.iterator();while(it.hasNext()){Integer tmp=(Integer)it.next();count.put(tmp,count.get(tmp)+1);}count.put(key,1);return map.get(key);}elsereturn -1;}public void put(int key, int value) {if(!map.containsKey(key)){cnt++;}if(cnt>volumn&&!map.containsKey(key)){cnt--;Set set=count.keySet();Iterator it=set.iterator();int maxs=0;while(it.hasNext()){Integer tmp=(Integer)it.next();maxs=Math.max(maxs,count.get(tmp));}Set set1=count.keySet();Iterator its=set1.iterator();while(its.hasNext()){Integer tmp=(Integer)its.next();if(count.get(tmp)==maxs){map.remove(tmp);count.remove(tmp);break;}}Set sets=count.keySet();Iterator itw=sets.iterator();while(itw.hasNext()){Integer tmp=(Integer)itw.next();count.put(tmp,count.get(tmp)+1);}map.put(key,value);count.put(key,1);}else{Set set1=count.keySet();Iterator it=set1.iterator();while(it.hasNext()){Integer tmp=(Integer)it.next();count.put(tmp,count.get(tmp)+1);}count.put(key,1);map.put(key,value);}}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/

思路二：用双向链表，哈希表作为辅助。

这个过程有点像自己在一堆书里拿书，就是灵神的那个题解思想，这里直接上代码。

注意事项：在写remove函数的时候，可能会出现空指针的异常，这是因为传入的参数可能是一个null，所以为了避免这种事情发生，我们要么就在函数前面加上声明特判null，要么就需要保证传入的结点必须是非null的，这样的话就需要对其他相关的函数进行约束。

class LRUCache {private final int capacity;private class Node{Node pre;Node next;int key,value;public Node(int key,int value){this.key=key;this.value=value;}}private final Node dummy=new Node(0,0);private Map<Integer,Node>map=new HashMap<>();public LRUCache(int capacity) {this.capacity=capacity;dummy.next=dummy;dummy.pre=dummy;}public int get(int key) {Node t=getNode(key);return t!=null?t.value:-1;}public void put(int key, int value) {Node node=getNode(key);if(node!=null){node.value=value;return;}node=new Node(key,value);map.put(key,node);pullFront(node);if(map.size()>capacity){Node tmp=dummy.pre;remove(tmp);map.remove(tmp.key);}}public Node getNode(int key){if(!map.containsKey(key)){return null;}Node tmp=map.get(key);remove(tmp);pullFront(tmp);return tmp;}public void remove(Node tmp){tmp.pre.next=tmp.next;tmp.next.pre=tmp.pre;}public void pullFront(Node tmp){tmp.pre=dummy;tmp.next=dummy.next;tmp.pre.next=tmp;tmp.next.pre=tmp;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/