知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 02 - LRU缓存 ## 题目(LeetCode 146) 设计一个 LRU(最近最少使用)缓存,支持 get 和 put 操作,均为 O(1)。 ## 大白话理解 哈希表负责 O(1) 查找,双向链表负责维护使用顺序。最近用过的放头部,满了就淘汰尾部。 ## 解法:HashMap + 双向链表 ```java class LRUCache { class Node { int key, val; Node prev, next; Node(int k, int v) { key = k; val = v; } } int capacity; Map<Integer, Node> map; Node head, tail; // 哨兵节点 public LRUCache(int capacity) { this.capacity = capacity; map = new HashMap<>(); head = new Node(0, 0); tail = new Node(0, 0); head.next = tail; tail.prev = head; } public int get(int key) { if (!map.containsKey(key)) return -1; Node node = map.get(key); remove(node); addToHead(node); return node.val; } public void put(int key, int value) { if (map.containsKey(key)) { Node node = map.get(key); node.val = value; remove(node); addToHead(node); } else { Node node = new Node(key, value); map.put(key, node); addToHead(node); if (map.size() > capacity) { Node last = tail.prev; remove(last); map.remove(last.key); } } } private void remove(Node node) { node.prev.next = node.next; node.next.prev = node.prev; } private void addToHead(Node node) { node.next = head.next; node.prev = head; head.next.prev = node; head.next = node; } } ``` ## 复杂度 - get / put 均为 O(1) 时间,O(capacity) 空间 ## 一句话总结 HashMap 做索引,双向链表维护顺序,哨兵节点简化边界处理。 --- 下一篇:[03 - 反转链表](./03-reverse-list.md) ## 说明 LRU 缓存的 O(1) get/put 要求决定了必须用 **HashMap + 双向链表** 的组合。 Java 中也可以直接继承 `LinkedHashMap` 并重写 `removeEldestEntry` 来实现,但面试中通常要求手写数据结构。`LinkedHashMap` 内部实现原理与本解法完全相同。 > 💬 **Q:Node 可以用 ListNode 吗?不定义 key,只定义 val?** > > 不行,`key` 是必须保留的。原因在于**淘汰尾部节点时,需要同时从 HashMap 里删掉对应的 key**: > > ```java > Node last = tail.prev; > remove(last); > map.remove(last.key); // ← 必须知道 key,才能从 HashMap 中删除 > ``` > > 如果 Node 没有存 `key`,拿到链表尾节点后,根本不知道它对应 HashMap 中的哪个 key,就无法调 `map.remove()`,导致 HashMap 里永远有脏数据,容量控制失效。 > > ListNode 只有 `val` 没有 `key`,用于普通链表遍历题没问题。但 LRU 中,双向链表和 HashMap 是**双向绑定**的——链表节点需要携带 key,这样在 O(1) 删除链表节点的同时,才能同步删除 HashMap 里的条目。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入