search

threedayAAAAA / alg-exercise

算法训练
0 stars 0 forks source link

【基础篇 - Day 12】 2023-02-24 - 146. LRU 缓存 （02. 链表 ） #14

Open threedayAAAAA opened 1 year ago

threedayAAAAA commented 1 year ago

请你设计并实现一个满足  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

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/lru-cache 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

threedayAAAAA commented 1 year ago

思路

确定需要使⽤的数据结构

var LRUCache = function(capacity) { this.dataMap = new Map() this.virHeadNode = new DubListNode() this.tailNode = this.virHeadNode this.capacity = capacity this.currentCap = 0 };

LRUCache.prototype.updateOrder = function(curNode) { const preNode = curNode.pre if(this.virHeadNode.next === curNode){ return } const nextNode = curNode?.next preNode.next = nextNode if(nextNode){ nextNode.pre = preNode }

const oldHeadNode = this.virHeadNode.next
curNode.next = oldHeadNode
if(oldHeadNode){
    oldHeadNode.pre = curNode
}

this.virHeadNode.next = curNode
curNode.pre = this.virHeadNode

if(curNode === this.tailNode){
    this.tailNode = preNode
}

}

LRUCache.prototype.insertToHead = function(key, value) { const oldHeadNode = this.virHeadNode.next const newNode = new DubListNode(key, value, this.virHeadNode, oldHeadNode) this.virHeadNode.next = newNode if(oldHeadNode){ oldHeadNode.pre = newNode } this.dataMap.set(key, newNode) this.currentCap++ if(this.currentCap === 1){ this.tailNode = this.virHeadNode.next } }

LRUCache.prototype.removeTailNode = function() { if(this.tailNode === this.virHeadNode || !this.tailNode){ return } this.dataMap.delete(this.tailNode.key) const tailPreNode = this.tailNode.pre if(tailPreNode){ tailPreNode.next = null } this.tailNode = tailPreNode this.currentCap-- }

LRUCache.prototype.get = function(key) { const targetNode = this.dataMap.get(key) if(!targetNode){ return -1 } this.updateOrder(targetNode) return targetNode.val };

LRUCache.prototype.put = function(key, value) { const targetNode = this.dataMap.get(key) if(targetNode){ this.updateOrder(targetNode) targetNode.val = value } else { if(this.currentCap >= this.capacity){ this.removeTailNode() } this.insertToHead(key, value) } };



## 时空复杂度
- 时间复杂度：$O(1)$
- 空间复杂度：$O(n)$ n为容量的⼤⼩
yunliuyan commented 1 year ago

思路

代码

class DoubleNodeList {
    key: number;
    val: number;
    prev: DoubleNodeList | null;
    next: DoubleNodeList | null;
    constructor(key?: number, val?: number, prev?: DoubleNodeList | null, next?: DoubleNodeList |null) {
        this.key = key ?? 0;
        this.val = val ?? 0;
        this.prev = prev ?? null;
        this.next = next ?? null;
    }
}
class LRUCache {
    capacity: number;
    len: number;
    head: DoubleNodeList;
    end: DoubleNodeList;
    hashMap: Map<number, DoubleNodeList>;

    constructor(capacity: number) {
        this.capacity = capacity;
        this.len = 0;
        this.head = new DoubleNodeList();
        this.end = new DoubleNodeList();
        this.hashMap = new Map();
    }

    addToHead(key: number, val: number) {
        const addNode = new DoubleNodeList(key, val);
        const headNext = this.head.next;
        this.head.next = addNode;
        addNode.prev = this.head;
        if(headNext) {
            //首节点相连
            addNode.next = headNext;
            headNext.prev = addNode;
        }else {
            // 尾节点相连
            this.end.prev = addNode;
            addNode.next = this.end;
        }
        this.hashMap.set(key, addNode);
        this.len++;
    }

    remove(key: number): void {
        if(this.hashMap.has(key)) {
            const rmNode = this.hashMap.get(key);
            const rmNodePre = rmNode.prev;
            const rmNodeNext = rmNode.next;
            rmNodePre.next = rmNodeNext;
            rmNodeNext.prev = rmNodePre;
            this.delHashMapVal(key);
        }
    }

    removeEndNode(): void {
        const endPrev = this.end.prev;
        if(endPrev) {
            const prev = endPrev.prev;
            prev.next = this.end;
            this.end.prev = prev;
            this.delHashMapVal(endPrev.key);
        }
    }

    delHashMapVal(key: number): void {
        if(this.hashMap.has(key)) {
            this.hashMap.delete(key);
            this.len--;
        }
    }

    get(key: number): number {
        // 不在哈希表里面返回-1
        if (!this.hashMap.has(key)) {
            return -1;
        }
        // 在哈希表，我们要返回这个数据，并将这个数据移到首节点
        const res = this.hashMap.get(key);
        // 删除该节点
        this.remove(key);
        // 在首部加上该节点
        this.addToHead(key, res.val);
        return res.val;
    }

    put(key: number, value: number): void {
        // 在哈希表存在，删除该值
        if(this.hashMap.has(key)) {
            this.remove(key);
        }
        //不在哈希表里面，在首节点添加新节点.若长度大于最大容量值，在删除尾部值
        if(this.len === this.capacity) {
            this.removeEndNode();
        }
        this.addToHead(key, value);
    }
}

时空复杂度