【Day 12 】2023-11-27 - 146. LRU 缓存机制

[azl397985856]

146. LRU 缓存机制

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/lru-cache/

前置知识

暂无

题目描述

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 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

[Junru281]

Leetcode 146 Nov 26

146. LRU Cache

Ideas

想要Time complexity小, 又是存pairs, 我直接就考虑的HashMap, 当作cache. 对于如何实现LRU, 我考虑的用另外一个data structure去record visits

如果visited Array 去keep track priority, set的时候是O(1), 但是retrieve的时候, 要遍历array里面的所有elements, 需要O(n)

于是考虑LinkedList, 但是LinkedList的containsKey也需要O(n)时间. 如果要O(1)的话, 可以考虑其他data structure

class LRUCache {
    HashMap<Integer, Integer> cache;
    int size = 0;
    LinkedList<Integer> LRU = new LinkedList<>();

    public LRUCache(int capacity) {
        cache = new HashMap<Integer, Integer>(capacity);
        size = capacity;
    }

    public int get(int key) {
        if(cache.get(key) == null)
            return -1;
        else {
            LRU.remove((Integer) key);
            LRU.add(key);
            return cache.get(key);
        }
    }

    public void put(int key, int value) {
        if(cache.containsKey(key) || cache.size() < size){
            LRU.remove((Integer) key);
        }
        else{
            cache.remove(LRU.poll());
        }
        LRU.add(key);
        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);
 */

题解里面是用Hashmap来encode node存放的位置, 并且把node包装成一个object(里面包括prev, next). 用LinkedList类似data structure去改变head, tail指向.

[kiirii4]

思路

访问和增删操作都要达到O(1)，还要存入对值，这里可以使用unorder_map，每一个key可以访问唯一的链表节点，在链表节点中存储value，维护链表，使最近使用的节点移至表头，在链表超过预设容量时，删除表尾节点及unorded_map的对应成员

代码

struct DList {
    int key, value;
    DList* prev;
    DList* next;
    DList() : key(0), value(0), prev(nullptr), next(nullptr) {}
    DList(int _key, int _value) : key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, DList*> cache;
    DList* head;
    DList* tail;
    int size;
    int capacity;

public:
    LRUCache(int _capacity): capacity(_capacity), size(0){
    head = new DList();
    tail = new DList();
    head->next = tail;
    tail->prev = head;
    }

    int get(int key) {
        if(!cache.count(key))
        {
            return -1;
        }
        DList* node = cache[key];
        MoveToHead(node);
        return node->value;
    }

    void put(int key, int value) {
        if(!cache.count(key)) {
            DList* node = new DList(key, value);
            cache[key] = node;
            AddToHead(node);
            ++size;
            if(size > capacity) {
                DList* removed = RemoveTail();
                cache.erase(removed->key);
                delete removed;
                --size;
            }
        }
        else {
            DList* node = cache[key];
            node->value = value;
            MoveToHead(node);
        }
    }

    void AddToHead(DList* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    void RemoveNode(DList* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void MoveToHead(DList* node) {
        RemoveNode(node);
        AddToHead(node);
    }

    DList* RemoveTail() {
        DList* node = tail->prev;
        RemoveNode(node);
        return node;
    }
};

• 可以使链表构成一个循环链表，这样就可以只用一个哨兵节点

[laurallalala]

class DoubleListNode:
    def __init__(self, key, val, prev=None, nxt=None):
        self.key = key
        self.val = val
        self.prev = prev
        self.next = nxt

class LRUCache:
    '''
    a dict key->(val, node) to make sure get takes O(1)
    a double linked list to make sure put also takes O(1)
        put -> not in the dict, not exceed, create a new node and insert to the front, and add entry to dict
        put -> not in the dict, exceed, find the front node to evict, and the rest is the same as above
        put -> in the dict, if not exceed the capacity, update the value and insert the node to front
    '''

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.head = DoubleListNode(-1, -1)
        self.tail = DoubleListNode(-1, -1)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.dict = {}

    def get(self, key: int) -> int:
        if key in self.dict:
            value, node = self.dict[key]
            self.moveToFront(node)
            return self.dict[key][0]
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key not in self.dict:
            if len(self.dict) == self.capacity:
                # evict
                evict = self.tail.prev
                evict.prev.next = self.tail
                self.tail.prev = evict.prev
                print(evict.key)
                del self.dict[evict.key]
            node = DoubleListNode(key, value, self.head, self.head.next)
            self.head.next.prev = node
            self.head.next = node
            self.dict[key] = (value, node)    
        else:
            _, node = self.dict[key]
            node.val = value
            self.moveToFront(node)
            self.dict[key] = (value, node)

    def moveToFront(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

        tmp = self.head.next
        self.head.next = node
        node.next = tmp
        node.prev = self.head
        tmp.prev = node

Time: get - O(1), put - O(1) Space: O(N)

[ycan253]

class LRUCache:

    def __init__(self, capacity: int):
        self.data = dict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        #  get操作后先pop再插入，相当于进行一次使用
        s = self.data.get(key, -1)
        if s != -1:
            self.data.pop(key)
            self.data[key] = s
        return s

    def put(self, key: int, value: int) -> None:
        #  key存在，更新，再次进行使用
        if key in self.data:
            self.data.pop(key)
            self.data[key] = value
        else:
            # 判断容量是否达到capacity，未达到，直接插入
            if len(self.data) < self.capacity:
                self.data[key] = value
            else:
                #  达到capacity，将第一个也就是要求的最久未使用的逐出pop
                k = next(iter(self.data))
                self.data.pop(k)
                self.data[key] = value

[adfvcdxv]

思路

hash+双向链表

代码

class Node {
    constructor(key = 0, value = 0) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.dummy = new Node(); // 哨兵节点
        this.dummy.prev = this.dummy;
        this.dummy.next = this.dummy;
        this.keyToNode = new Map();
    }

    getNode(key) {
        if (!this.keyToNode.has(key)) { // 没有这本书
            return null;
        }
        const node = this.keyToNode.get(key); // 有这本书
        this.remove(node); // 把这本书抽出来
        this.pushFront(node); // 放在最上面
        return node;
    }

    get(key) {
        const node = this.getNode(key);
        return node ? node.value : -1;
    }

    put(key, value) {
        let node = this.getNode(key);
        if (node) { // 有这本书
            node.value = value; // 更新 value
            return;
        }
        node = new Node(key, value) // 新书
        this.keyToNode.set(key, node);
        this.pushFront(node); // 放在最上面
        if (this.keyToNode.size > this.capacity) { // 书太多了
            const backNode = this.dummy.prev;
            this.keyToNode.delete(backNode.key);
            this.remove(backNode); // 去掉最后一本书
        }
    }

    // 删除一个节点（抽出一本书）
    remove(x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
    }

    // 在链表头添加一个节点（把一本书放在最上面）
    pushFront(x) {
        x.prev = this.dummy;
        x.next = this.dummy.next;
        x.prev.next = x;
        x.next.prev = x;
    }
}

复杂度分析

时间复杂度：对于 put 和 get 都是 O(1)O(1)O(1)。

空间复杂度：O(capacity)

[0Christ1]

142. Linked List Cycle II

题目描述

设计和实现一个 LRU (Least recent use) 缓存机制

前置知识

• linked list
• Cache
• LRU

思路

• 题外话：在CompArch课上讲过Cache，但学艺不精 :(。其中一个project作业就是用到了LRU，不过我们只需要写一个function。
• 针对这题，对目前的我来说自己想明白+把code写清楚还是比较难，所以参考了一下官方题解。
  • 我觉得python直接调用库很方便，但是还是得自己搞明白里面的逻辑

代码

from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity: init):
        self.maxsize = capacity
        self.lrucache = OrderedDict()

    def get(self, key: int) -> int:
        if key in self.lrucache:
            self.lrucache.move_to_end(key)
        return self.lrucache.get(key, -1)

    def put(self, key: int, value: int) -> None:
        if key in self.lrucache:
            del self.lrucache[key]
        self.lrucache[key] = value
        if len(self.lrucache) > self.maxsize:
            self.lrucache.popitem(last=False)

复杂度分析

• 时间复杂度：平均的时间都是 $O(N)$
• 空间复杂度：链表和哈希表占用的空间都是 $O(N)$，所以总的时间复杂度为 $O(N)$。N即capacity

[Chloe-C11]

双指针

class ListNode:
    def __init__(self, key, value):
        self.key = key 
        self.value = value 
        self.prev = None 
        self.next = None 

class LRUCache:

    def __init__(self, capacity: int):
        # 键到节点的映射
        self.dic = dict() 
        # 缓存容量
        self.capacity = capacity 
        # 哨兵节点
        self.head = ListNode(0, 0) 
        self.tail = ListNode(-1, -1) 
        # 双指针
        self.head.next = self.tail 
        self.tail.prev = self.head 

    def get(self, key: int) -> int:
        if key in self.dic:
            node = self.dic[key] 
            self.removeFromList(node) 
            # 将节点插入到链表头部（因为它刚刚被访问）
            self.insertIntoHead(node) 
            return node.value 
        else:
            return -1 

    def put(self, key: int, value: int) -> None:
        # 类似于get()        
        if key in self.dic:             
            node = self.dic[key] 
            self.removeFromList(node)
            self.insertIntoHead(node) 
            node.value = value        
        # 如果缓存已满
        else: 
            if len(self.dic) >= self.capacity: 
                # 从列表尾部删除最近最少使用的节点（同时从字典中删除）
                self.removeFromTail() 
            node = ListNode(key,value) 
            self.dic[key] = node 
            # 将新节点插入到链表头部
            self.insertIntoHead(node) 

    # 从链表中删除节点
    def removeFromList(self, node):
        node.prev.next = node.next 
        node.next.prev = node.prev

    def insertIntoHead(self, node):
        headNext = self.head.next 
        self.head.next = node 
        node.prev = self.head 
        node.next = headNext 
        headNext.prev = node

    def removeFromTail(self):
        if len(self.dic) == 0: return
        tail_node = self.tail.prev
        del self.dic[tail_node.key]
        self.removeFromList(tail_node)

[Danielyan86]

思路

• 直接使用内置函数，这题就失去考算法意义了。
• hash + 双向链表实现

思路不是很复杂，但是实际实现 code 时候细节很多，很容易出错，需要注意这几点

• 链表里面也需要存一个 key，方便通过 node 获取到字典的 key，可以理解成 hash 和链表的 node 也是双向的
• 初始化头尾哨兵节点，让插入和删除更加方便
• delete 和 add node 的操作可以封装，方便 get 和 put 调用，del 字典操作操作不要放到子方法里，减少冗余
• put 一个已经存在 key 操作因为包括了一个 get 步骤，可以直接调用 get 方法
• 才用末尾节点为最新的是为了和 ordereddict 方向保持一致
• get 不要忘了 return value

code

# hash + Doubly linked list
class LRUCache:
    def __init__(self, capacity: int):
        self.size = capacity
        self.cache = dict()
        self.head, self.tail = LinkNode(), LinkNode()
        self.head.next, self.tail.pre = self.tail, self.head

    def get(self, key: int) -> int:
        if key not in self.cache: return -1
        node = self.cache[key]
        self.remove_node(node)
        self.add_tail(node)

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key].value = value
            self.get(key)
        else:
            if len(self.cache) == self.size:
                node = self.head.next # get the head node and remove it
                self.remove_node(node)
                del self.cache[node.key]
            node = LinkNode(key, value)
            self.add_tail(node)
            self.cache[key] = node

    def remove_node(self, node):
        pre, nt = node.pre, node.next
        pre.next = nt
        nt.pre = pre
        node.pre = node.next = None

    def add_tail(self, node):
        pre = self.tail.pre
        pre.next = node
        node.pre = pre
        node.next = self.tail
        self.tail.pre = node

# ordereddict
class LRUCache:
    #let's assume the fist item is the less used due to orderedDict feature
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache: return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        # need to judge the key existing in dictionary d[k]=v is enough
        self.cache[key] = value # add to the end by default
        self.cache.move_to_end(key)
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False) # pop the first item

complexity

Because using the hash table to find the node, the time is constant

• time: O(1)
• space: O(1)

[larscheng]

思路

分析题目：数据需要频繁的O(1)增删（链表）、需要通过O(1)查询（哈希表） 确定数据结构：哈希表+双向链表 注意点：

• get：需要将当前节点移动到头节点
• put：容量已满时链表尾部节点即为最久未使用节点，要进行删除
• 使用虚拟头部和虚拟尾部避免边界判断

参考讲义：链表-套路五：设计题

代码

class LRUCache {
    class ListNode{

        int key;
        int val;
        ListNode pre;
        ListNode next;
        public ListNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
        public ListNode() {}
    }
    HashMap<Integer,ListNode> map = new HashMap<>();
    ListNode head;
    ListNode tail;
    int size;
    int capacity;
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        this.head = new ListNode();
        this.tail = new ListNode();
        //dummyhead ⇄ ..... ⇄ dummytail
        //虚拟头
        this.head.next = this.tail;
        //虚拟尾
        this.tail.pre = this.head;
    }

    public int get(int key) {
        ListNode node = map.get(key);
        if (node != null) {
            del(node);
            addHead(node);
            return node.val;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        ListNode node = map.get(key);
        if (node != null) {
            node.val = value;
            map.put(key, node);

            del(node);
            addHead(node);
        } else {
            ListNode newNode = new ListNode(key,value);
            if (size >= capacity) {
                //del tail
                map.remove(this.tail.pre.key);
                del(this.tail.pre);
                this.size--;
            }
            map.put(key, newNode);
            addHead(newNode);
            this.size++;
        }
    }

    private void del(ListNode listNode) {
        //del
        ListNode pre = listNode.pre;
        ListNode next = listNode.next;
        pre.next = next;
        next.pre = pre;
    }

    private void addHead(ListNode listNode) {
        //dummyhead     ⇄   otherNode   ⇄   dummytail
        //dummyhead ⇄ listNode ⇄ otherNode ⇄ dummytail
        listNode.pre = this.head;
        listNode.next = this.head.next;
        this.head.next.pre = listNode;
        this.head.next = listNode;
    }
}

复杂度

• 时间复杂度： put 和 get 都是 O(1)。
• 空间复杂度：O(n)，n为链表长度

[witerth]

/**

• @param {number} capacity */ var LRUCache = function(capacity) { this.capacity = capacity; this.length = 0; this.hashCache = {}; this.head = null; this.tail = null; };

var creatNode = function(key, value, pre) { return { key: key, value: value, pre: pre || null, next: null } }

var moveNode = function(cur) { if (this.head === this.tail) return; if (!cur.next) { return; } if (cur.pre) { cur.next.pre = cur.pre; cur.pre.next = cur.next; } else { this.head = cur.next; cur.next.pre = null; } cur.next = null; this.tail.next = cur; cur.pre = this.tail; this.tail = cur; }

/**

• @param {number} key

• @return {number} */ LRUCache.prototype.get = function(key) { if (this.length === 0) return -1; let cur = this.hashCache[key]; if (!cur) return -1;

  moveNode.call(this, cur); return this.hashCache[key].value; };

/**

• @param {number} key
• @param {number} value

• @return {void} */ LRUCache.prototype.put = function(key, value) { let cur = this.hashCache[key]; if (cur) { cur.value = value; moveNode.call(this, cur);

  } else { this.length++; cur = creatNode(key, value, this.tail); this.hashCache[key] = cur; if (this.length === 1) { this.head = cur; this.tail = cur; return null; } this.tail.next = cur; this.tail = cur; if (this.length > this.capacity) { this.length--; this.hashCache[this.head.key] = undefined; this.head = this.head.next; this.head.pre = null;

  }

  } };

/**

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

[JinhMa]

public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int key, int value) {this.key = key; this.value = value;}
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用伪头部和伪尾部节点
        this.head = new DLinkedNode();
        this.tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在，先通过哈希表定位，再移到头部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在，创建一个新的节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 添加进哈希表
            cache.put(key, newNode);
            // 添加至双向链表的头部
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 如果超出容量，删除双向链表的尾部节点
                DLinkedNode tail = removeTail();
                // 删除哈希表中对应的项
                cache.remove(tail.key);
                --size;
            }
        }
        else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

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

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

[snmyj]

class LRUCache { int cap; LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>(); public LRUCache(int capacity) { this.cap = capacity; }

public int get(int key) {
    if (!cache.containsKey(key)) {
        return -1;
    }

    makeRecently(key);
    return cache.get(key);
}

public void put(int key, int val) {
    if (cache.containsKey(key)) {
        cache.put(key, val);
        makeRecently(key);
        return;
    }

    if (cache.size() >= this.cap) {
        int oldestKey = cache.keySet().iterator().next();
        cache.remove(oldestKey);
    }
    cache.put(key, val);
}

private void makeRecently(int key) {
    int val = cache.get(key);
    cache.remove(key);
    cache.put(key, val);
}

}

[rennzhang]

题目

146. LRU 缓存机制

思路

题目有要求时间复杂度必须O(1)，因此不能使用遍历的方式；

首先看了下 LRU缓存 的概念，用链表实现简单来说就是，链表一头是最新的，另一头是最旧的。因此在get 或者 put 时应该把当前放到最新的那一头，而当超出的时候从最旧的那一头移除一个节点即可，同时需要更新哈希表；

所以至少需要一个虚拟头结点和虚拟尾节点，可以直接获取到 使用频率最高或最低的节点，那么尾节点需要一个 prev 指针，并且 put 的节点可能在链表的任何位置，在不借助其他结构存储节点位置的情况（如用数组），那么每个节点都需要有一个 prev 指针，用来修改前后节点的指针，至此，能确定这道题需要用到双向链表。

但细节比较多，尤其是指针的操作，很容易出错，最终代码还是参考了题解写出来的。

代码

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.head = new ListNode();
  this.last = new ListNode();
  this.head.next = this.last;
  this.last.prev = this.head;
  this.useSpace = 0
  this.map = {};
};

LRUCache.prototype.isFull = function () {
  return this.useSpace == this.capacity;
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  let node = this.map[key];
  if (node) {
    this.appendHead(this.removeNode(node));
    return node.val;
  }
  return -1;
};
LRUCache.prototype.removeNode = function (node) {
  node.prev.next = node.next;
  node.next.prev = node.prev;
  node.prev = null;
  node.next = null;

  return node;
};

LRUCache.prototype.appendHead = function (node) {
  node.prev = this.head;
  node.next = this.head.next;
  this.head.next = node;
  node.next.prev = node;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  if (key in this.map) {
    let node = this.map[key]
    this.appendHead(this.removeNode(node));
    this.map[key] = node

    node.val = value;
  } else {
    if (this.isFull()) {
      const node = this.last.prev;
      delete this.map[node.key];
      const newNode = this.removeNode(node)
      newNode.val = value
      newNode.key = key
      this.appendHead(newNode);
      this.map[key] = newNode
    } else {
      let node = new ListNode(value);
      node.key = key
      this.appendHead(node);
      this.map[key] = node
      this.useSpace ++
    }
  }
};

复杂度分析

• 时间复杂度：O(1)

• 空间复杂度：O(N)