leetcode146：LRU缓存

题目链接

leetcode

题目描述

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

C++ 代码

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

/*
    哈希表 + 双向链表

    时间复杂度：O(1)
        get 操作 O(1)，因为哈希表可以快速定位结点，而移动结点到头部也是 O(1) 操作。
        put 操作 O(1)，因为哈希表和链表操作都是 O(1) 复杂度。
    空间复杂度：O(capacity)
        其中 capacity 是缓存的最大容量。
        哈希表占用空间最多为 O(capacity)，链表占用空间最多为 O(capacity) 的空间。
*/
class LRUCache {
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        head = new Node(), tail = new Node();
        head->next = tail, tail->prev = head;
    }

    int get(int key) {
        // key 不存在
        if (!cache.count(key)) {
            return -1;
        }
        // key 存在
        Node* p = cache[key];
        removeNode(p);
        addNode(p);
        return p->val;
    }
    
    void put(int key, int value) {
        // key 不存在
        if (!cache.count(key)) {
            // 缓存已满
            if (cache.size() == capacity) {
                Node* p = tail->prev;
                removeNode(p);
                cache.erase(p->key);
                delete p;
            }
            // 缓存不满
            Node* p = new Node(key, value);
            addNode(p);
            cache[key] = p;
        } else {
            // key 存在
            Node* p = cache[key];
            p->val = value;
            removeNode(p);
            addNode(p);
        }
    }

private:
    struct Node {
        int key, val;
        Node *prev, *next;
        Node() : key(-1), val(-1), prev(nullptr), next(nullptr) {}
        Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
    };
    // 双向链表
    Node *head, *tail;
    // 哈希表
    unordered_map<int, Node*> cache;
    // 缓存容量
    int capacity;

    // 添加一个节点到链表的头部
    void addNode(Node* p) {
        p->prev = head;
        p->next = head->next;
        head->next->prev = p;
        head->next = p;
    }

    // 从链表中删除一个节点
    void removeNode(Node* p) {
        p->next->prev = p->prev;
        p->prev->next = p->next;
    }
};

int main() {
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << endl; // 返回 1
    cache.put(3, 3);    // 该操作会使得关键字 2 作废
    cout << cache.get(2) << endl; // 返回 -1 (未找到)
    cache.put(4, 4);    // 该操作会使得关键字 1 作废
    cout << cache.get(1) << endl; // 返回 -1 (未找到)
    cout << cache.get(3) << endl; // 返回 3
    cout << cache.get(4) << endl; // 返回 4

    return 0;
}

Golang 代码

/*
   双向链表：维护结点的访问顺序，最近访问的结点放在头部，最久未访问的在尾部。
   哈希表：快速查找结点。

    Get 操作：
        若结点存在，则将其移到双向链表的头部。
    Put 操作：
        若结点存在，则更新其值并移到头部。
        否则，创建新结点添加到头部，若此时缓存超过容量，则移除双向链表的尾部结点。

   时间复杂度：O(1)
       Get 操作：
           通过哈希表查找结点的时间复杂度为 O(1)，将结点移到头部的时间复杂度也为 O(1)。
       Put 操作：
           更新/添加结点的时间复杂度为 O(1)，移除尾部结点的时间复杂度也为 O(1)。
       故总时间复杂度为 O(1)。
   空间复杂度：O(capacity)
       双向链表和哈希表的空间大小取决于缓存的容量，最大为 O(capacity)。
*/

package main

import "fmt"

// 双向链表节点
type Node struct {
    key, val int
    prev, next *Node
}

// LRU 缓存
type LRUCache struct {
    head *Node
    tail *Node
    capacity int
    hash map[int]*Node
}

// Constructor 初始化 LRU 缓存
func Constructor(capacity int) LRUCache {
    cache := LRUCache {
        head: &Node{},
        tail: &Node{},
        capacity: capacity,
        hash: make(map[int]*Node),
    }
    cache.head.next = cache.tail
    cache.tail.prev = cache.head
    return cache
}

// addNodeToHead 添加节点到头部
func (lru *LRUCache) addNodeToHead(node *Node) {
    node.prev = lru.head
    node.next = lru.head.next
    lru.head.next.prev = node
    lru.head.next = node
}

// removeNode 删除节点
func (lru *LRUCache) removeNode(node *Node) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

// removeNodeFromTail 移除尾部节点
func (lru *LRUCache) removeNodeFromTail() *Node {
    node := lru.tail.prev
    lru.removeNode(node)
    return node
}

// Get 获取键的值
func (lru *LRUCache) Get(key int) int {
    // key 存在
    if node, ok := lru.hash[key]; ok {
        lru.removeNode(node)
        lru.addNodeToHead(node)
        return node.val
    }
    // key 不存在
    return -1
}

// Put 添加或更新键值对
func (lru *LRUCache) Put(key int, value int)  {
    // key 存在
    if node, ok := lru.hash[key]; ok {
        node.val = value
        lru.removeNode(node)
        lru.addNodeToHead(node)
    } else {
        // key 不存在
        // 缓存已满
        if len(lru.hash) == lru.capacity {
            node = lru.removeNodeFromTail()
            delete(lru.hash, node.key)
        }
        // 缓存不满
        newNode := &Node{key: key, val: value}
        lru.addNodeToHead(newNode)
        lru.hash[key] = newNode
    }
}

func main() {
    // 测试用例
	cache := Constructor(2)

	cache.Put(1, 1) // 缓存是 {1=1}
	cache.Put(2, 2) // 缓存是 {1=1, 2=2}
	fmt.Println(cache.Get(1)) // 返回 1，缓存是 {1=1, 2=2}

	cache.Put(3, 3)           // LRU key 是 2，缓存是 {1=1, 3=3}
	fmt.Println(cache.Get(2)) // 返回 -1（未找到），缓存是 {1=1, 3=3}

	cache.Put(4, 4)           // LRU key 是 1，缓存是 {4=4, 3=3}
	fmt.Println(cache.Get(1)) // 返回 -1（未找到），缓存是 {4=4, 3=3}
	fmt.Println(cache.Get(3)) // 返回 3，缓存是 {3=3, 4=4}
	fmt.Println(cache.Get(4)) // 返回 4，缓存是 {4=4, 3=3}
}