【CT】LeetCode手撕—146. LRU 缓存

---

题目

• 原题连接：146. LRU 缓存

---

1-思路

1-1 LRU知识点

• LRU ：最近最少使用算法，如果经常请求的数据不会被淘汰，会被淘汰的是最近最少请求的数据。
• 热门数据会往上排列

• 看到 LRU，就想到 LRU 对应的数据结构 ——> HashMap + 双向链表

---

1-2 实现思路

LRU 算法的具体步骤

• **1- 头插：**新数据直接插入到列表头部
• **2- 移动到头：**缓存数据被命中，将数据移动到列表头部
• **3- 删除尾部：**缓存已经满的时候，移除列表尾部数据

LRU的子数据结构

① 双向链表 DLinkedNode 结点定义

• 包含 key 、value，key 就是 HashMap 的 key

class DLinkedNode{int key;int value;DLinkedNode pre;DLinkedNode next;DLinkedNode(){}DLinkedNode(int k,int v){key = k; value = v;}
}

② 其他字段

• cache ：缓存 map ：key 放 key，value 放值
• size：当前缓存中的元素个数
• capacity：为缓存的容量
• DLinkedNode head,tail：定义双向链表的头尾结点

Map<Integer,DLinkedNode> cache = new HashMap<Integer,DLinkedNode>();
int size;
int capacity;
DLinkedNode head,tail;

LRU实现的方法

① 初始化——LRUCache中初始化

• 根据 capacity 传入的容量进行初始化

    public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.pre = head;}

② public int get(int key) 取元素方法

获取元素涉及到的方法如下

• 1- public int get(int key)：
  • 通过 key 获取元素，直接使用 map 的get方法
  • 若不存在，返回 -1
  • 若存在，先将其 moveToHead(DLinkedNode node) 再返回
• 2- moveToHead(DLinkedNode node)
  • private DLinkedNode remove(DLinkedNode node)：先删除node元素
  • private void addToHead(DLinkedNode node)再添加到头
• 3- remove(DLinkedNode node)
  • 双链表 删除 node 结点
• 4- addToHead(DLinkedNode node)
  • 双链表头插

---

③ public void put(int key, int value) 存元素方法

• 添加元素思考：
  • 当前元素不存在，直接添加，添加过程中需要判断缓存是否已满
  • 若存在，更新 value 即可

---

2-实现

⭐146. LRU 缓存——题解思路

class LRUCache {// 成员class DLinkedNode{int key;int value;DLinkedNode pre;DLinkedNode next;DLinkedNode(){}DLinkedNode(int k,int v){key = k;value = v;}}HashMap<Integer,DLinkedNode> cache = new HashMap<>();int size;int capacity;DLinkedNode head,tail;public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.pre = head;}public int get(int key) {// 获取元素 keyDLinkedNode node = cache.get(key);if(node==null){return -1;}moveToHead(node);return node.value;}public void put(int key, int value) {DLinkedNode node = cache.get(key);if(node == null){node = new DLinkedNode(key,value);addToHead(node);cache.put(key,node);size++;if(size>capacity){DLinkedNode last = removeLast();cache.remove(last.key);}}else{node.value =value;moveToHead(node);}}private DLinkedNode removeLast(){DLinkedNode node = tail.pre;remove(node);return node;}private void moveToHead(DLinkedNode node){// 先删除 node // 再添加 noderemove(node);addToHead(node);}private void remove(DLinkedNode node){node.pre.next = node.next;node.next.pre = node.pre;}private void addToHead(DLinkedNode node){node.next = head.next;head.next.pre = node;head.next = node;node.pre = head;}}/*** 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);*/

---

3- ACM实现

package Daily_LC.Month6_Week1.Day85;import java.util.HashMap;
import java.util.Scanner;public class LRUCache {// 1- 定义数据class DLinkedNode{int key;int value;DLinkedNode pre;DLinkedNode next;DLinkedNode(){}DLinkedNode(int k,int v){key = k;value = v;}}int size;int capacity;DLinkedNode head,tail;HashMap<Integer,DLinkedNode> cache = new HashMap<>();// 2- 初始化public LRUCache(int capacity){this.capacity = capacity;this.size = 0;head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.pre = head;}// 3- 实现 LRU 的get方法public int get(int key){DLinkedNode node = cache.get(key);if(node== null){return -1;}moveToHead(node);return node.value;}private void moveToHead(DLinkedNode node){remove(node);addToHead(node);}private void remove(DLinkedNode node){node.pre.next = node.next;node.next.pre = node.pre;}private void addToHead(DLinkedNode node){node.next = head.next;head.next.pre = node;head.next = node;node.pre = head;}// 4- 实现 LRU 的put方法public void put(int key,int value){DLinkedNode node = cache.get(key);if(node==null){node = new DLinkedNode(key,value);cache.put(key,node);addToHead(node);size++;if(size>capacity){DLinkedNode ttail = removeTail();cache.remove(ttail.key);size--;}}}private DLinkedNode removeTail(){DLinkedNode node = tail.pre;remove(node);return node;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);System.out.println("输入cache缓存容量capacity");int capacity = scanner.nextInt();LRUCache cache = new LRUCache(capacity);while (scanner.hasNext()) {String operation = scanner.next();if (operation.equals("get")) {int key = scanner.nextInt();System.out.println(cache.get(key));} else if (operation.equals("put")) {int key = scanner.nextInt();int value = scanner.nextInt();cache.put(key, value);}}scanner.close();}
}

---