LeetCode146. LRU 缓存🌟🌟🌟🌟中等

课后作业

问题描述

原文链接：146. LRU 缓存

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

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多调用 2 * 105 次 get 和 put

代码实现

Java

class LRUCache {
    Map<Integer, Node> map = new HashMap();
    int capacity;
    int size;
    Node head;
    Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;

        this.head = new Node(-1, -1);
        this.tail = new Node(-2, -2);
        head.next = tail;
        tail.pre = head;

    }

    public int get(int key) {
        // 判断是否存在
        Node tmp = map.get(key);
        if(tmp != null){
            // 删除
            delete(tmp);
            insertTohead(tmp);
            return tmp.value;
        }

        return -1;
    }

    public void put(int key, int value) {
        // 判断key是否存在
        Node tmp = map.get(key);
        if(tmp != null){
            // 删除
            delete(tmp);
            // 插入到头部
            tmp.value = value;
            insertTohead(tmp);
            return;
        }
        // 不存在
        Node newHead = new Node(key, value);
        // 插入到头部
        insertTohead(newHead);
        size++;
        map.put(key, newHead);
        if(size > capacity){
            // 删除最后一个节点
            Node res = tail.pre;
            delete(res);
            map.remove(res.key);
            size--;
        }
    }

    // 插入到头部head->tmp->....
    public void insertTohead(Node tmp){
        tmp.next = head.next;
        head.next.pre = tmp;
        head.next = tmp;
        tmp.pre = head;
    }

    // 删除tmp节点
    public void delete(Node tmp){
        tmp.pre.next = tmp.next;
        tmp.next.pre = tmp.pre;
    }



    // 定义双向链表
    class Node{
        int value;
        int key;
        Node next;
        Node pre;

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




    // 面试中考的挺多=》面大厂=〉掌握

    /*方法1:单链表

    head->(4,4)->(3,3)->null

    put:
    1.不存在，直接把节点插入到头部
    2.如果存在，把这个节点从链表中删除，并且插入到头部
    3.如果插入式，超过最大容量，则链表最后一个节点删除

    get:如果存在，则返回，并且把节点删除+插入到链表头部
        如果不存在，则直接返回-1，其他都不用操作

    时间复杂度：put:O(n). get:O(n)


    # 优化1：加哈希表 <key,Node>
   看似O(1)，但其实不能O(1)，因为还需要删除节点，删除节点需要
   找到前驱节点，找前驱节点的过程也需要O（n)

   # 继续优化：双向链表 + 哈希表
   可以O(1)
   演示：
   head<->(3,3)<->(4,4)<->tail
    */

}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

Python

class LRUCache(object):
    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.map = {}
        self.capacity = capacity
        self.size = 0

        self.head = Node(-1, -1)
        self.tail = Node(-2, -2)
        self.head.next = self.tail
        self.tail.pre = self.head

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        # 判断是否存在
        tmp = self.map.get(key)
        if tmp:
            # 删除
            self.delete(tmp)
            self.insertTohead(tmp)
            return tmp.value
        return -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        # 判断key是否存在
        tmp = self.map.get(key)
        if tmp:
            # 删除
            self.delete(tmp)
            # 插入到头部
            tmp.value = value
            self.insertTohead(tmp)
            return
        # 不存在
        newHead = Node(key, value)
        # 插入到头部
        self.insertTohead(newHead)
        self.size += 1
        self.map[key] = newHead
        if self.size > self.capacity:
            # 删除最后一个节点
            res = self.tail.pre
            self.delete(res)
            self.map.pop(res.key)
            self.size -= 1

    # 插入到头部head->tmp->....
    def insertTohead(self, tmp):
        tmp.next = self.head.next
        self.head.next.pre = tmp
        self.head.next = tmp
        tmp.pre = self.head

    # 删除tmp节点
    def delete(self, tmp):
        tmp.pre.next = tmp.next
        tmp.next.pre = tmp.pre

# 定义双向链表
class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None
        self.pre = None

C++

class LRUCache {
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        size = 0;

        // 初始化头尾节点
        this->head = new Node(-1, -1);
        this->tail = new Node(-2, -2);
        head->next = tail;
        tail->pre = head;

    }

    int get(int key) {
        // 判断是否存在
        Node* tmp = map[key];
        if(tmp != nullptr){
            // 删除
            deleteNode(tmp);
            // 插入到头部
            insertToHead(tmp);
            return tmp->value;
        }

        return -1;
    }

    void put(int key, int value) {
        // 判断key是否存在
        Node* tmp = map[key];
        if(tmp != nullptr){
            // 删除
            deleteNode(tmp);
            // 插入到头部
            tmp->value = value;
            insertToHead(tmp);
            return;
        }
        // 不存在
        Node* newHead = new Node(key, value);
        // 插入到头部
        insertToHead(newHead);
        size++;
        map[key] = newHead;
        if(size > capacity){
            // 删除最后一个节点
            Node* res = tail->pre;
            deleteNode(res);
            map.erase(res->key);
            size--;
        }
    }

private:
    // 定义双向链表
    struct Node{
        int value;
        int key;
        Node* next;
        Node* pre;

        Node(int k, int v){
            this->key = k;
            this->value = v;
            next = nullptr;
            pre = nullptr;
        }
    };
    unordered_map<int, Node*> map; // key->Node指针
    int capacity; // 最大容量
    int size; // 当前大小
    Node* head; // 双向链表头节点
    Node* tail; // 双向链表尾节点

    // 插入到头部head->tmp->....
    void insertToHead(Node* tmp){
        tmp->next = head->next;
        head->next->pre = tmp;
        head->next = tmp;
        tmp->pre = head;
    }

    // 删除节点
    void deleteNode(Node* tmp){
        tmp->pre->next = tmp->next;
        tmp->next->pre = tmp->pre;
    }
};

Go

type LRUCache struct {
    mapCache  map[int]*Node
    capacity  int
    size      int
    head, tail  *Node
}

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

// 构造函数
func Constructor(capacity int) LRUCache {
    lru := LRUCache{
        mapCache: make(map[int]*Node),
        capacity: capacity,
        size:     0,
        head:     &Node{key: -1, value: -1},
        tail:     &Node{key: -2, value: -2},
    }
    lru.head.next = lru.tail
    lru.tail.prev = lru.head
    return lru
}

// get方法
func (this *LRUCache) Get(key int) int {
    if node, ok := this.mapCache[key]; ok {
        // 如果存在，删除该节点并插入到头部
        this.deleteNode(node)
        this.insertToHead(node)
        return node.value
    }
    return -1
}

// put方法
func (this *LRUCache) Put(key int, value int) {
    if node, ok := this.mapCache[key]; ok {
        // 如果存在，删除该节点并插入到头部
        this.deleteNode(node)
        node.value = value
        this.insertToHead(node)
    } else {
        // 如果不存在，创建新节点并插入到头部
        newNode := &Node{key: key, value: value}
        this.insertToHead(newNode)
        this.mapCache[key] = newNode
        this.size++
        if this.size > this.capacity {
            // 如果超过最大容量，删除尾部节点
            tailNode := this.tail.prev
            this.deleteNode(tailNode)
            delete(this.mapCache, tailNode.key)
            this.size--
        }
    }
}

// 在头部插入一个节点
func (this *LRUCache) insertToHead(node *Node) {
    node.next = this.head.next
    this.head.next.prev = node
    this.head.next = node
    node.prev = this.head
}

// 删除一个节点
func (this *LRUCache) deleteNode(node *Node) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

帅地训练营会员

打赏 收藏 海报挣佣金 推广链接