LeetCode 146. LRU 缓存

Categories:

Tags:

题目描述
相似题目

题目描述

✅ 146. LRU 缓存

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

        Node() {
        }

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

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

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new Node();
        this.tail = new Node();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
            return;
        }

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

        if (cache.size() > capacity) {
            Node removed = removeTail();
            cache.remove(removed.key);
        }
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    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 Node removeTail() {
        Node last = tail.prev;
        removeNode(last);
        return last;
    }
}

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
    }

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

    if len(c.cache) > c.capacity {
        removed := c.removeTail()
        delete(c.cache, removed.key)
    }
}

func (c *LRUCache) moveToHead(node *Node) {
    c.removeNode(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) removeTail() *Node {
    last := c.tail.prev
    c.removeNode(last)
    return last
}

相似题目

题目	难度	考察点
460. LFU 缓存	困难	哈希表 + 双向链表
588. 设计内存文件系统	困难	哈希表、设计
604. 迭代压缩字符串	简单	迭代器设计
Design a Load Distributor	困难	设计
1756. 设计最近使用（MRU）队列	中等	队列 + MRU 设计
432. 全 O(1) 的数据结构	困难	哈希表 + 双向链表

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/17639942