北京教育云平台网站建设,中国服装设计网站,seminar什么意思中文,威海团购网站建设LRU自定义最近最少使用 一#xff1a;leetCode 题目二#xff1a;思路三#xff1a;上代码3.1#xff1a;类代码3.2#xff1a; 测试代码 一#xff1a;leetCode 题目
题目链接#xff1a; 题目链接#xff1a;146.LRU缓存 为什么要写博客记录下呢#xff1f; 1.这个… LRU自定义最近最少使用 一leetCode 题目二思路三上代码3.1类代码3.2 测试代码 一leetCode 题目
题目链接 题目链接146.LRU缓存 为什么要写博客记录下呢 1.这个题很锻炼自己的编码能力代码量多结构多 2.这个题很锻炼自己的owner能力感觉挑战底层类不屈于写业务代码 3.这个题很锻炼自己的耐力调试比较麻烦 4.这个题很锻炼自己的边界能力各种边界条件需要测试 二思路
最近最少使用 最近最少使用 翻译下把最后一个不使用的给踢出去 维护一个队列 使用的放到队列的前头 队尾永远是最近最少使用的 翻译使用了就放队列前头想移除就移除队尾 如何实现队列O(1) 的复杂度 首先想到的是链表这里使用最普通的 listNode的结构体 class ListNode {int val;ListNode next;ListNode parent;public ListNode(int val) {this.val val;this.next null;this.parent null;}
}三上代码
代码
类代码测试代码
3.1类代码
import java.util.HashMap;
import java.util.Map;public class LRUCache {// 初始化的容量private final int capacity;// 元数据private final MapInteger, Integer metaMap;// 用于记录 key 和队列的关系private final MapInteger, ListNode metaLinkedMap;// 最后一个结点private ListNode lastNode;// 头结点private final ListNode headNode;public LRUCache(int capacity) {this.capacity capacity;metaMap new HashMap();metaLinkedMap new HashMap();// 请注意 这里我太笨了我这里前两个结点都是头结点。这样有利于我个人的思考 ListNode dataNode new ListNode(0);headNode new ListNode(0);headNode.next dataNode;}// 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1public int get(int key) {if (metaMap.containsKey(key)) {// 调整频率adjustExistNodeSort(key);return metaMap.get(key);}return -1;}// 如果关键字 key 已经存在则变更其数据值 value 如果不存在则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity 则应该 逐出 最久未使用的关键字public void put(int key, int value) {if (metaMap.containsKey(key)) {// 更新热点数据adjustExistNodeSort(key);// 替换数据metaMap.put(key, value);} else {if (metaMap.size() capacity) {// 需要移除数据removeLastNode();}ListNode putNode new ListNode(key);// 更新热点数据adjustNewNodeSort(putNode);// 初始化信息metaMap.put(key, value);metaLinkedMap.put(key, putNode);}}/*** 排序一个已经存在的结点* param key 已经存在的key*/private void adjustExistNodeSort(Integer key) {ListNode hotNode metaLinkedMap.get(key);ListNode oldHeadNode headNode.next.next;if (hotNode oldHeadNode){return;}hotNode.parent.next hotNode.next;if (hotNode.next ! null){hotNode.next.parent hotNode.parent;}if (lastNode hotNode metaMap.size() ! 1) {lastNode hotNode.parent;}if (oldHeadNode ! null) {oldHeadNode.parent hotNode;hotNode.next oldHeadNode;}headNode.next.next hotNode;hotNode.parent headNode.next;}/*** 调整一个新结点的排序* param putNode 新节点*/private void adjustNewNodeSort(ListNode putNode) {// 初始化末尾节点if (lastNode null || metaMap.size() 0) {lastNode putNode;}// 放到头节点ListNode oldHeadNode headNode.next.next;if (oldHeadNode ! null) {oldHeadNode.parent putNode;putNode.next oldHeadNode;}headNode.next.next putNode;putNode.parent headNode.next;}/*** 移除最后一个元素*/private void removeLastNode() {int lastVal lastNode.val;metaMap.remove(lastVal);metaLinkedMap.remove(lastVal);lastNode lastNode.parent;lastNode.next null;}
}class ListNode {int val;ListNode next;ListNode parent;public ListNode(int val) {this.val val;this.next null;this.parent null;}
}
3.2 测试代码
import java.util.HashSet;
import java.util.Set;// Press Shift twice to open the Search Everywhere dialog and type show whitespaces,
// then press Enter. You can now see whitespace characters in your code.
public class Main {public static void main(String[] args) {LRUCache lruCache new LRUCache(1);lruCache.get(6);lruCache.get(8);lruCache.put(12,1);lruCache.get(2);lruCache.put(15,11);lruCache.put(5,2);lruCache.put(1,15);lruCache.put(4,2);lruCache.get(5);lruCache.put(15,15);}
}
