网站建设宣传ppt模板下载,技能培训机构,WordPress作者信息框,网页设计阶段力扣labuladong一刷day52天LRU算法 文章目录 力扣labuladong一刷day52天LRU算法概念一、146. LRU 缓存思路一#xff1a;使用双向链表加map来手动实现。思路二#xff1a;使用LinkedHashMap 概念
LRU的全称为Least Recently Used#xff0c;翻译出来就是最近最少使用的意思…力扣labuladong一刷day52天LRU算法 文章目录 力扣labuladong一刷day52天LRU算法概念一、146. LRU 缓存思路一使用双向链表加map来手动实现。思路二使用LinkedHashMap 概念
LRU的全称为Least Recently Used翻译出来就是最近最少使用的意思它是一种内存淘汰算法当内存不够时将内存中最久没使用的数据清理掉。 LUR算法是内存管理的一种页面置换算法就是用来删除内存中不被使用的数据腾出空间来把常用的数据存进去。
一、146. LRU 缓存
题目链接https://leetcode.cn/problems/lru-cache/
思路一使用双向链表加map来手动实现。
class Node {public int key, val;public Node next, prev;public Node(int k, int v) {key k;val v;}
}class DoubleList{private Node head, tail;private int size;public DoubleList() {head new Node(0, 0);tail new Node(0, 0);head.next tail;tail.prev head;size 0;}void addLast(Node x) {x.next tail;x.prev tail.prev;tail.prev.next x;tail.prev x;size;}void remove(Node x) {x.prev.next x.next;x.next.prev x.prev;size--;}Node removeFirst() {if (head.next tail) {return null;}Node first head.next;remove(first);return first;}int size() {return size;}
}class LRUCache{private HashMapInteger, Node map;private DoubleList cache;private int cap;public int get(int key) {if (!map.containsKey(key)) {return -1;}makeRecently(key);return map.get(key).val;}public void put(int key, int value) {if (map.containsKey(key)) {deleteKey(key);addRecently(key, value);return;}if (cap cache.size()) {deleteLastRecently();}addRecently(key, value);}public LRUCache(int capacity) {this.cap capacity;this.map new HashMap();this.cache new DoubleList();}private void makeRecently(int key) {Node node map.get(key);cache.remove(node);cache.addLast(node);}private void addRecently(int key, int value) {Node node new Node(key, value);map.put(key, node);cache.addLast(node);}private void deleteKey(int key) {Node node map.remove(key);cache.remove(node);}private void deleteLastRecently() {Node node cache.removeFirst();map.remove(node.key);}}/*** 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);*/思路二使用LinkedHashMap
put都是从尾部加入要想删除头部可以使用map.keySet().iterator().next();拿到key然后删除。
class LRUCache {LinkedHashMapInteger, Integer map;int cap 0;public LRUCache(int capacity) {map new LinkedHashMap();cap capacity;}public int get(int key) {if (!map.containsKey(key)) {return -1;}Integer val map.remove(key);map.put(key, val);return val;}public void put(int key, int value) {if (map.containsKey(key)) {map.remove(key);map.put(key, value);return;}if (cap map.size()) {Integer first map.keySet().iterator().next();map.remove(first);}map.put(key, value);}
}
