知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 09 - LRU 缓存 ## 题目(LeetCode 146) 设计一个 LRU(最近最少使用)缓存,支持 get 和 put 操作,均为 O(1)。 ## 大白话理解 HashMap 负责 O(1) 查找,双向链表负责 O(1) 维护使用顺序。最近用过的放链表头部,最久没用的在尾部,满了就删尾部。 ``` 双向链表(从新到旧): head ↔ [最近用的] ↔ [次近] ↔ ... ↔ [最久没用的] ↔ tail HashMap:key → 链表节点(O(1) 定位) ``` ## 代码 ```java class LRUCache { private int capacity; private Map<Integer, Node> map = new HashMap<>(); private Node head = new Node(), tail = new Node(); // 哨兵 class Node { int key, val; Node prev, next; Node() {} Node(int k, int v) { key = k; val = v; } } public LRUCache(int capacity) { this.capacity = capacity; head.next = tail; tail.prev = head; } public int get(int key) { Node node = map.get(key); if (node == null) return -1; moveToHead(node); // 用过了,移到最前面 return node.val; } public void put(int key, int value) { Node node = map.get(key); if (node != null) { node.val = value; moveToHead(node); } else { Node newNode = new Node(key, value); map.put(key, newNode); addToHead(newNode); if (map.size() > capacity) { Node removed = removeTail(); // 删最久没用的 map.remove(removed.key); } } } private void addToHead(Node node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node; } private void removeNode(Node node) { node.prev.next = node.next; node.next.prev = node.prev; } private void moveToHead(Node node) { removeNode(node); addToHead(node); } private Node removeTail() { Node node = tail.prev; removeNode(node); return node; } } ``` head 和 tail 是哨兵节点,不存数据,简化边界处理。 ## 一句话总结 HashMap 查找 O(1) + 双向链表维护顺序 O(1)。用过的移到头部,满了删尾部。 --- 上一篇:[08 - 排序链表](./08-sort-list.md) | 下一篇:[10 - 回文链表](./10-palindrome-list.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入