金华做公司网站,企业品牌vi设计,中国建设人才网站,wordpress 音乐格式LRUCache实现 思路#xff1a;使用linkedHashMap。按照插入顺序的有序链表。 get 操作。cache不包含#xff0c;返回-1。包含。我们需要当前key重新put。 /将 key 变为最近使用 put。如果包含。修改当前key值。然后将key变成最近使用。不包含。如果cacheSize大于当前最大size…LRUCache实现 思路使用linkedHashMap。按照插入顺序的有序链表。 get 操作。cache不包含返回-1。包含。我们需要当前key重新put。 /将 key 变为最近使用 put。如果包含。修改当前key值。然后将key变成最近使用。不包含。如果cacheSize大于当前最大size。我们需要溢出最近没有使用的。那就是链表的最后一个元素。链表的头部。 class LRUCache {int cap;LinkedHashMapInteger, Integer cache new LinkedHashMap();public LRUCache(int capacity) { this.cap capacity;}public int get(int key) {if (!cache.containsKey(key)) {return -1;}// 将 key 变为最近使用makeRecently(key);return cache.get(key);}public void put(int key, int val) {if (cache.containsKey(key)) {// 修改 key 的值cache.put(key, val);// 将 key 变为最近使用makeRecently(key);return;}if (cache.size() this.cap) {// 链表头部就是最久未使用的 keyint oldestKey cache.keySet().iterator().next();cache.remove(oldestKey);}// 将新的 key 添加链表尾部cache.put(key, val);}private void makeRecently(int key) {int val cache.get(key);// 删除 key重新插入到队尾cache.remove(key);cache.put(key, val);}
} public class LRUCache {//双链表 从左往右使用减少class DLinkedNode{int key, val;DLinkedNode pre;DLinkedNode next;public DLinkedNode(){}public DLinkedNode(int _key, int _val) {this.key _key;this.val _val;}}DLinkedNode tail, head; //双链表头指针和尾部指针HashMapInteger, DLinkedNode cache new HashMap();int size; //当前元素数量int capacity; //容量//1.初始化public LRUCache(int _capacity) {this.capacity _capacity;this.size 0;tail new DLinkedNode();head new DLinkedNode();head.next tail;tail.pre head;}public int get(int key) {DLinkedNode node cache.get(key);if(node null){//不存在keyreturn -1;}else {//使用了该数更新缓存deleteNode(node);addToHead(node);}return node.val;}public void put(int key, int value) {DLinkedNode node cache.get(key);//如果存在修改并更新缓存;if(node ! null){node.val value;deleteNode(node);addToHead(node);}else {//不存在//1.判断容量 达到最大容量删除最近未使用节点(别忘了cache也要删)if(size capacity){DLinkedNode removeNode tail.pre;deleteNode(removeNode);cache.remove(removeNode.key);size--;}DLinkedNode newNode new DLinkedNode(key, value);size;addToHead(newNode);cache.put(key, newNode);}}//删除双链表中的节点public void deleteNode(DLinkedNode node){node.pre.next node.next;node.next.pre node.pre;}//加入到链表头部public void addToHead(DLinkedNode node){node.pre head;node.next head.next;head.next.pre node;head.next node;}
}/*** 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);*/
