当前位置：首页 > news >正文

LeetCode热题100——146. LRU 缓存

news 2025/8/2 5:14:06

https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-100-liked

请你设计并实现一个满足 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) 的平均时间复杂度运行。

小米一面，没刷过题所以栽了，静下来心看看解决方案

题解

题目中涉及到了查询、插入和删除都要平均时间复杂度O(1)，查询想要时间复杂度O(1) 可以用数组，插入删除如果使用数组无法满足要求，因为从数组中删除元素涉及到元素的移动复杂度 O(n), 我们必须使用链表来插入和删除，链表分为单链表和双链表，如果使用单链表删除元素的话还是需要遍历才能找到前后的元素，所以我们使用 哈希表查询 + 双链表操作 的思路

在这里插入图片描述
通过设置head和tail虚节点，避免判空等处理，这样取第一个元素时直接调用 head.next ，取最后一个元素时直接调用 tail.pre

class LRUCache {class Node {int val;int key;Node next;Node pre;public Node(int key, int val) {this.key = key;this.val = val;}}private int mSize;private Map<Integer, Node> map;private Node head;private Node tail;public LRUCache(int size) {mSize = size;map = new HashMap<>();// 技巧处，使用头尾虚节点来处理 空异常head = new Node(-1, -1);tail = new Node(-1, -1);head.next = tail;tail.pre = head;}public int get(int key) {if (!map.containsKey(key)) return -1;Node node = map.get(key);removeNode(node);addToHead(node);return node.val;}public void put(int key, int val) {if (map.containsKey(key)) {removeNode(map.get(key));}Node node = new Node(key, val);map.put(key, node);addToHead(node);// 易错点，超过限制时需要同时移除 双链表 node和 map中的nodeif(map.size() > mSize){Node lastNode = tail.pre;removeNode(lastNode);map.remove(lastNode.key);}}private void addToHead(Node node) {Node first = head.next;head.next = node;node.next = first;first.pre = node;node.pre = head;}private void removeNode(Node node) {Node preNode = node.pre;Node nextNode = node.next;preNode.next = nextNode;nextNode.pre = preNode;}
}