LeetCode146.LRU缓存

写了一个小时，终于把示例跑过了，没想到啊提交之后第19/22个测试用例没过

我把测试用例的输出复制在word上看看和我的有什么不同，没想到有18页的word，然后我一直检查终于找出了问题，而且这个bug真的太活该了，感觉只有傻屌才能写出这种bug,以下是我之前的代码：

class LRUCache {HashMap<Integer,Integer> map;int cap;int useIndex;HashMap<Integer,Integer> lastUseMap;public LRUCache(int capacity) {map = new HashMap<Integer,Integer>();lastUseMap = new HashMap<Integer,Integer>();cap = capacity;useIndex =0;}public int get(int key) {if(map.containsKey(key)){lastUseMap.put(key,useIndex);useIndex++;return map.get(key);}else{return -1;}}public void put(int key, int value) {if(!map.containsKey(key)){if(map.size() == cap){int min = 10000;int delKey = -1;Set<Map.Entry<Integer, Integer>> entrySet = lastUseMap.entrySet();for (Map.Entry<Integer,Integer> entry : entrySet) {if(entry.getValue() < min){min = entry.getValue();delKey = entry.getKey();}}map.remove(delKey);lastUseMap.remove(delKey);}}map.put(key,value);lastUseMap.put(key,useIndex);useIndex++;}
}

我想讲我的算法思想，最后再讲里面的那个bug。

我的想法是，用hashmap来进行put和get操作，这样就不用自己写真正put和get的代码了（其实一开始看到题目写put和get算法复杂度是O1我用的是数组，写了很久没写出来，直接换成了hashmap，因为一开始我以为hashmap的算法复杂度大于1，但其实不是的，因为hashmap是数组--->数组+链表 ---->数组+红黑树，最简单的情况是用hash函数直接算出数组下标，算法复杂度是O1，如果数组的这个位置上是个链表，那么还要用O(n)遍历链表，如数组的这个位置上是个红黑树，那么还要用O(nlogn)遍历红黑树，但大多数情况还是O(1)）

那么put和get操作解决了，只需要解决过期淘汰就可以了，我是用一个

 HashMap<Integer,Integer> map;

进行正真的putget缓存操作，然后用一个

 int useIndex;

来记录每次get和put操作的序号(从0开始，每次自增，如果get失败就不自增)，然后再用一个map

HashMap<Integer,Integer> lastUseMap;

来记录map中的每个元素的最新一次的操作序号。

构造函数就不用说了，把这几个属性初始化以下就行。

先讲get方法，如果map中没有这个key返回-1，如果有这个key，把lastUseMap中的这个key的value更新为本次操作的序号，再把序号加一，再把map中这个key的value返回。

再讲讲put方法，先对size进行判断，如果达到最大容量cap那么就要删除掉map中的一个最久未使用的元素，要找出最久未使用的元素只需要对lastUseMapz进行一次遍历即可，这个就属于基操了，先定义个较大数min，然后把遍历出来的value和min进行比较，如果小于min就把min更新为这个value，找到了这个最久没用的元素后再map和lastUseMap中把这个元素删除就可以了，然后是进行put操作，除了把key和value put进map以外还要记得把key和当前操作序号put进lastUseMap，然后操作序号自增。

需要注意的一点是，在尽心put操作之前先看看map里面有没有这个key，如果有直接put就行不用删除，这是个坑，有个测试用例就是这个。

最后讲讲那个傻逼bug，就是min的初值，我当时也没想到操作次数会达到18页word啊，就直接给了10000，所以在第19个测试用例报错了，只要把min的初值赋为Integer.MAX_VALUE就可以了。

再看看官方题解吧：

题解用的是hsahMap+双向链表的做法，并且它并没有用封装好的LinkedList,而是自己写一个简介的链表，以下是题解代码：

public class LRUCache {class DLinkedNode {int key;int value;DLinkedNode prev;DLinkedNode next;public DLinkedNode() {}public DLinkedNode(int _key, int _value) {key = _key; value = _value;}}private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();private int size;private int capacity;private DLinkedNode head, tail;public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;// 使用伪头部和伪尾部节点head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.prev = head;}public int get(int key) {DLinkedNode node = cache.get(key);if (node == null) {return -1;}// 如果 key 存在，先通过哈希表定位，再移到头部moveToHead(node);return node.value;}public void put(int key, int value) {DLinkedNode node = cache.get(key);if (node == null) {// 如果 key 不存在，创建一个新的节点DLinkedNode newNode = new DLinkedNode(key, value);// 添加进哈希表cache.put(key, newNode);// 添加至双向链表的头部addToHead(newNode);++size;if (size > capacity) {// 如果超出容量，删除双向链表的尾部节点DLinkedNode tail = removeTail();// 删除哈希表中对应的项cache.remove(tail.key);--size;}}else {// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部node.value = value;moveToHead(node);}}private void addToHead(DLinkedNode node) {node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}private void removeNode(DLinkedNode node) {node.prev.next = node.next;node.next.prev = node.prev;}private void moveToHead(DLinkedNode node) {removeNode(node);addToHead(node);}private DLinkedNode removeTail() {DLinkedNode res = tail.prev;removeNode(res);return res;}
}

hashMap的key是key，value是链表的节点。链表中越头部的节点是越新的节点，越再尾部的节点是越久未使用的节点。

get方法只需要通过key拿到node节点，如果为null直接返回-1，否则返回node.val，并且需要把这个node移到链表的最前面。

put方法也是通过key拿到node节点，如果node不存在就创建一个node，然后把key和这个node放进hashMap,把这个node放到链表的头部，然后size++，如果这个时候size>最大容量了那么就把尾部节点删除，并且再map中删除这个key，size--;如果node存在直接把node的value改成参数value然后把node移到链表头部，剩下的方法都是关于双向链表的操作了。