企业科技网站建设,刚入手一手房怎么网上做网站,企业网站托管外包平台,谷歌搜索引擎免费入口2022题目链接#xff1a;https://leetcode.cn/problems/lru-cache/description/?envTypestudy-plan-v2envIdtop-100-liked 原理非常简单#xff0c;一个双端链表配上一个hash表。 首先我们要知道什么是LRU就是最小使用淘汰。怎么淘汰#xff0c;链表尾部就是最不常用的直接…题目链接https://leetcode.cn/problems/lru-cache/description/?envTypestudy-plan-v2envIdtop-100-liked 原理非常简单一个双端链表配上一个hash表。 首先我们要知道什么是LRU就是最小使用淘汰。怎么淘汰链表尾部就是最不常用的直接删除最近使用过的就移动到链表头部。要查找就利用hash表进行映射查找。 代码
class LRUCache {//需要定义的双端链表节点//哈希表class Node{int key;int value;Node prev;Node next;public Node() {}public Node(int _key,int _value) {key _key;value _value;}}private MapInteger,Node cache new HashMap();private int size;private int capacity;private Node head,tail;public LRUCache(int capacity) {this.size 0;this.capacity capacity;head new Node();tail new Node();head.next tail;tail.prev head;}public int get(int key) {Node node cache.get(key);if(node null) return -1;moveToHead(node);return node.value;}public void put(int key, int value) {//如果存在if(cache.containsKey(key)){Node t cache.get(key);t.value value;moveToHead(t);}else{//如果不存在size;if(sizecapacity){cache.remove(tail.prev.key);//System.out.println(tail.prev.key);moveTail();size--;}Node node new Node(key,value);Node temp head.next;head.next node;node.prev head;temp.prev node;node.next temp;cache.put(key,node);}}public void moveToHead(Node node){//本身删除了Node qian node.prev;qian.next node.next;node.next.prev qian;//再插到头部Node temp head.next;head.next node;node.prev head;temp.prev node;node.next temp;}public void moveTail(){Node temp tail.prev.prev;temp.next tail;tail.prev temp;}
}/*** 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);*/
