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
}

class LRUCache { /** 思路：双向链表 + 哈希表 */ class Node{ int key; int value; Node pre = null; Node next = null; public Node(){ } public Node(int key, int value){ this.key = key; this.value = value; } } int capacity; int size; Map<Integer,Node> map = new HashMap(); Node dummyHead = new Node(); Node dummyTail = new Node(); public LRUCache(int capacity) { this.capacity = capacity; this.size = 0; dummyHead.next = dummyTail; dummyTail.pre = dummyHead; } public int get(int key) { Node target = map.get(key); if(target != null){ delete(target); insertToHead(target); return target.value; } return -1; } public void put(int key, int value) { Node target = map.get(key); if(target != null){ target.value = value; delete(target); insertToHead(target); return; } Node newNode = new Node(key,value); map.put(key,newNode); insertToHead(newNode); size++; if(size > capacity){ map.remove(dummyTail.pre.key); delete(dummyTail.pre); size--; } } private void delete(Node temp){ temp.pre.next = temp.next; temp.next.pre = temp.pre; } private void insertToHead(Node temp){ temp.next = dummyHead.next; temp.pre = dummyHead; dummyHead.next.pre = temp; dummyHead.next = temp; } } /** * 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); */

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) { // 判断是否存在 1.存在：返回关键字的值，并删除，再放入到头结点 2.不存在：返回 -1 。 Node temp = map.get(key); if(temp != null){ // 删除，并插入到头部 delete(temp); // 插入到头部 insertToHead(temp); return temp.value; } return -1; } public void put(int key, int value) { // 判断是否存在 // 1.存在：修改关键字的Node,并删除移动到头部 // 2.不存在：则向缓存中插入该组 key-value 插入到头结点 // 3.插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。删除尾部 Node temp = map.get(key); if(temp != null){ // 删除，修改关键字的Node，插入头部 delete(temp); temp.value = value; // 变更其数据值 value insertToHead(temp); return; } // 2.不存在 // Node newNode = new Node(key, value); // 创建节点，就是map的value // insertToHead(newNode); // size++; // map.put(key, newNode); // // 3.插入操作导致关键字数量超过 capacity // if(size > capacity){ // // 逐出最久未使用的关键字。删除尾部 // Node res = tail.pre; // delete(res); // // map移除 // map.remove(res.key); // size--; // } // 3.插入操作导致关键字数量超过 capacity if(size == capacity){ // 逐出最久未使用的关键字。删除尾部 Node res = tail.pre; delete(res); // map移除 map.remove(res.key); size--; } Node newNode = new Node(key, value); // 创建节点，就是map的value insertToHead(newNode); size++; map.put(key, newNode); } // 删除节点 public void delete(Node temp){ // 前驱 temp.pre 后继 temp.next temp.pre.next = temp.next; temp.next.pre = temp.pre; } // 插入节点到头部 public void insertToHead(Node temp){ // 注意顺序 temp.next = head.next; head.next.pre = temp; head.next = temp; temp.pre = head; } // 双向链表定义 class Node{ int key; int value; Node next; Node pre; public Node(int key, int value){ this.key = key; this.value = value; } } }

int n; unordered_map<int,Node*>hash;//key-value，序号和节点 void remove(Node*p){ p->right->left=p->left; p->left->right=p->right; } //双向链表，规定左边是刚用的 void insert(Node*p){//插入节点，应当插入到最左侧 p->right=L->right; p->left=L; L->right->left=p; L->right=p; } //缓存初始化，capacity是缓存的最大容量 LRUCache(int capacity) { n=capacity; //左右两边是虚拟的两个头结点 L=new Node(-1,-1),R=new Node(-1,-1); //两个虚拟头结点挂接 L->right=R; R->left=L; } //取其中一个节点（涉及哈希表的查找，以及双链表的插删） int get(int key) { //没找到关键字 if(hash.count(key)==0)return -1; //用哈希表获取该节点 auto p=hash[key]; remove(p); insert(p); return p->value; } void put(int key, int value) { if(hash.count(key)){ //如果key存在，修改对应value，移除再加入 auto p=hash[key]; p->value=value; remove(p); insert(p); }else{//检查缓存满不满 if(hash.size()==n){//满了，删除右边的，即为最久未用 auto p=R->left; remove(p);//删除链表节点 hash.erase(p->key);//更新哈希表 delete p;//释放内存 }//创建节点、插入节点，链表和哈希表都需要更新 auto p=new Node(key,value); hash[key]=p; insert(p); } }

class LRUCache { // 双向链表 + 哈希表 Map<Integer,Node> map = new HashMap<>(); int capacity; int size; Node head; Node tail; 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.prev = head; } public int get(int key) { Node node = map.get(key); if(node != null) { // 先删除该节点 delete(node); // 再插入到头部 insertToHead(node); return node.val; } return -1; } public void put(int key, int value) { // 判断key是否存在 Node node = map.get(key); // key存在，把节点值更新，插入到头部 if(node != null) { delete(node); // 覆盖旧值 node.val = value; insertToHead(node); return; } // key不存在，就新增一个节点插入 Node newNode = new Node(key,value); insertToHead(newNode); size ++; map.put(key,newNode); // 实际个数超出容量 if(size > capacity) { // 删除最后一个节点 Node res = tail.prev; delete(res); map.remove(res.key); size --; } } // 删除节点 public void delete(Node node) { node.prev.next = node.next; node.next.prev = node.prev; } // 将节点插入到头部 public void insertToHead(Node node) { node.next = head.next; head.next.prev = node; head.next = node; node.prev = head; } class Node { int key; int val; Node next; Node prev; public Node(int key, int val) { this.key = key; this.val = val; } } }

//利用LinkedHashMap实现LRU class LRUCache { private LinkedHashMap<Integer, Integer> cache; private int capacity; public LRUCache(int capacity) { cache = new LinkedHashMap<>(); this.capacity = capacity; } public int get(int key) { if(!cache.containsKey(key)) return -1; int val = cache.get(key); cache.remove(key); cache.put(key, val); return val; } public void put(int key, int value) { if(cache.containsKey(key)){ cache.remove(key); cache.put(key, value); return; } if(cache.size() >= capacity){ cache.remove(cache.keySet().iterator().next()); } cache.put(key, value); } } /** * 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); */

发表回复取消回复

后才能评论

Mr.肖永久会员 2024年3月28日下午6:25

少年不识流川枫永久会员 2024年3月17日下午3:56

Yuki 永久会员 2024年2月1日下午12:02

打卡
class LRUCache {
public:
//使用双链表+哈希实现，每个节点记录时间时间戳
struct Node{
int key,value;
Nodeleft,right;
Node(int _key,int _value):key(_key),value(_value),left(NULL),right(NULL){}
}*L,*R;

};

星河揽我入梦永久会员 2023年10月31日下午9:13

如果get的节点不为空为什么要删除这个节点，再插入到头部

登录以回复

AD钙奶普通 2023年9月3日上午12:14

阿尚普通 2023年8月18日下午4:43

帅气的冬瓜普通 2023年6月29日下午5:33

打卡

登录以回复

课后作业

问题描述

代码实现

Java

Python

C++

Go

发表回复 取消回复

评论(7)

付款后无法显示下载地址或者无法查看内容？

发表回复取消回复