LeetCode 面试题 16.25. LRU 缓存

Categories:

题目描述
思路分析
1. 解法一：哈希表 + 双向链表（推荐）
相似题目

题目描述

✅ 面试题 16.25. LRU 缓存

思路分析

解法一：哈希表 + 双向链表（推荐）

核心思路：

哈希表实现 O(1) 查找键到节点。

双向链表维护访问顺序，头部为最近使用，尾部为最久未使用。

get/put 都将节点移动到链表头；容量满时删除尾部节点。

复杂度分析：

时间复杂度：O(1)，每次操作均为常数时间。

空间复杂度：O(capacity)，存储哈希表和链表节点。

import java.util.*;

class LRUCache {
    private static class Node {
        int key;
        int value;
        Node prev;
        Node next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<Integer, Node> map;
    private final Node head;
    private final Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        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.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            // 更新后移动到头部
            moveToHead(node);
            return;
        }

        if (map.size() == capacity) {
            // 移除尾部节点
            Node removed = removeTail();
            map.remove(removed.key);
        }

        Node newNode = new Node(key, value);
        map.put(key, newNode);
        addToHead(newNode);
    }

    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;
    }
}

type Node struct {
	key   int
	value int
	prev  *Node
	next  *Node
}

type LRUCache struct {
	capacity int
	cache    map[int]*Node
	head     *Node
	tail     *Node
}

func Constructor(capacity int) LRUCache {
	head := &Node{}
	tail := &Node{}
	head.next = tail
	tail.prev = head

	return LRUCache{
		capacity: capacity,
		cache:    make(map[int]*Node),
		head:     head,
		tail:     tail,
	}
}

func (c *LRUCache) Get(key int) int {
	node, ok := c.cache[key]
	if !ok {
		return -1
	}

	// 访问后移动到头部
	c.moveToHead(node)
	return node.value
}

func (c *LRUCache) Put(key int, value int) {
	if node, ok := c.cache[key]; ok {
		node.value = value
		// 更新后移动到头部
		c.moveToHead(node)
		return
	}

	if len(c.cache) == c.capacity {
		// 移除尾部节点
		removed := c.removeTail()
		delete(c.cache, removed.key)
	}

	node := &Node{key: key, value: value}
	c.cache[key] = node
	c.addToHead(node)
}

func (c *LRUCache) addToHead(node *Node) {
	node.prev = c.head
	node.next = c.head.next
	c.head.next.prev = node
	c.head.next = node
}

func (c *LRUCache) removeNode(node *Node) {
	node.prev.next = node.next
	node.next.prev = node.prev
}

func (c *LRUCache) moveToHead(node *Node) {
	c.removeNode(node)
	c.addToHead(node)
}

func (c *LRUCache) removeTail() *Node {
	node := c.tail.prev
	c.removeNode(node)
	return node
}

相似题目

题目	难度	考察点
146. LRU 缓存	中等	设计数据结构
460. LFU 缓存	困难	设计数据结构
355. 设计推特	中等	设计
716. 最大栈	困难	栈、设计
432. 全 O(1) 的数据结构	困难	设计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/20444064