LRU自定义最近最少使用-java实现

一：leetCode 题目

题目链接：

题目链接：146.LRU缓存

为什么要写博客记录下呢？

1.这个题很锻炼自己的编码能力（代码量多，结构多）
2.这个题很锻炼自己的owner能力（感觉挑战底层类，不屈于写业务代码）
3.这个题很锻炼自己的耐力（调试比较麻烦）
4.这个题很锻炼自己的边界能力（各种边界条件需要测试）

二：思路

1. 最近最少使用：

最近最少使用 翻译下：把最后一个不使用的给踢出去

维护一个队列
使用的放到队列的前头
队尾永远是最近最少使用的

翻译：使用了就放队列前头，想移除就移除队尾

2. 如何实现队列，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 Map<Integer, Integer> metaMap;// 用于记录 key 和队列的关系private final Map<Integer, 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);}
}