力扣labuladong一刷day52天LRU算法

力扣labuladong一刷day52天LRU算法

概念

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 HashMap<Integer, 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 {LinkedHashMap<Integer, 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);}
}