网站建设制作费,网站后期培训机构全国排名,汽车网站建设的基本功能,渭南建设工程招标投标网站写了一个小时#xff0c;终于把示例跑过了#xff0c;没想到啊提交之后第19/22个测试用例没过 我把测试用例的输出复制在word上看看和我的有什么不同#xff0c;没想到有18页的word#xff0c;然后我一直检查终于找出了问题#xff0c;而且这个bug真的太活该了#xff0c… 写了一个小时终于把示例跑过了没想到啊提交之后第19/22个测试用例没过 我把测试用例的输出复制在word上看看和我的有什么不同没想到有18页的word然后我一直检查终于找出了问题而且这个bug真的太活该了感觉只有傻屌才能写出这种bug,以下是我之前的代码
class LRUCache {HashMapInteger,Integer map;int cap;int useIndex;HashMapInteger,Integer lastUseMap;public LRUCache(int capacity) {map new HashMapInteger,Integer();lastUseMap new HashMapInteger,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;SetMap.EntryInteger, Integer entrySet lastUseMap.entrySet();for (Map.EntryInteger,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操作解决了只需要解决过期淘汰就可以了我是用一个 HashMapInteger,Integer map;
进行正真的putget缓存操作然后用一个 int useIndex;
来记录每次get和put操作的序号(从0开始每次自增如果get失败就不自增)然后再用一个map
HashMapInteger,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 MapInteger, DLinkedNode cache new HashMapInteger, 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是keyvalue是链表的节点。链表中越头部的节点是越新的节点越再尾部的节点是越久未使用的节点。
get方法只需要通过key拿到node节点如果为null直接返回-1否则返回node.val并且需要把这个node移到链表的最前面。
put方法也是通过key拿到node节点如果node不存在就创建一个node然后把key和这个node放进hashMap,把这个node放到链表的头部然后size如果这个时候size最大容量了那么就把尾部节点删除并且再map中删除这个keysize--;如果node存在直接把node的value改成参数value然后把node移到链表头部剩下的方法都是关于双向链表的操作了。
