为什么做电影网站没有流量,废旧物品手工制作大全,哔哩哔哩网站建设模板,建设银行储蓄卡余额查询系统LRU 缓存
力扣链接#xff1a;146. LRU 缓存
题目描述
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类#xff1a; LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓…LRU 缓存
力扣链接146. LRU 缓存
题目描述
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类 LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1 。 void put(int key, int value) 如果关键字 key 已经存在则变更其数据值 value 如果不存在则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity 则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例 Java代码LinkedHashMap
class LRUCache extends LinkedHashMapInteger, Integer{private int capacity;public LRUCache(int capacity) {super(capacity, 0.75F, true);this.capacity capacity;}public int get(int key) {return super.getOrDefault(key, -1);}public void put(int key, int value) {super.put(key, value);}Overrideprotected boolean removeEldestEntry(Map.EntryInteger, Integer eldest) {return size() capacity;}
}
Java代码哈希表 双向链表
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;}
}/*** 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);*/
