手撕题

柯里化

function curry(...args) {
    let argsList = [...args];

    const fn = function (...args) {
        if (args.length) {
            argsList = [...argsList, ...args];
            return fn;
        }
        return argsList.reduce((acc, val) => acc + val);
    }
    return fn;
}

console.log(curry(1)(2)(3, 4)());

hardMAn

https://mp.weixin.qq.com/s/-hEjxY0yI6ZBTzAlc3xwAw

lru o(1)不使用 map,set

// 定义双向链表节点类
class DLinkedNode {
    constructor(key = 0, value = 0) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

// 定义 LRU 缓存类
class LRUCache {
    constructor(capacity) {
        // 缓存容量
        this.capacity = capacity;
        // 当前缓存中的元素数量
        this.size = 0;
        // 哈希表，用于快速查找节点
        this.cache = {};
        // 双向链表的虚拟头节点
        this.head = new DLinkedNode();
        // 双向链表的虚拟尾节点
        this.tail = new DLinkedNode();
        // 初始化双向链表
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    // 获取缓存中的元素
    get(key) {
        if (!this.cache[key]) {
            return -1;
        }
        // 如果存在，将该节点移动到链表头部
        const node = this.cache[key];
        this.moveToHead(node);
        return node.value;
    }

    // 插入或更新缓存中的元素
    put(key, value) {
        if (this.cache[key]) {
            // 如果 key 已经存在，更新节点的值，并将其移动到链表头部
            const node = this.cache[key];
            node.value = value;
            this.moveToHead(node);
        } else {
            // 如果 key 不存在，创建新节点
            const node = new DLinkedNode(key, value);
            this.cache[key] = node;
            this.addToHead(node);
            this.size++;
            if (this.size > this.capacity) {
                // 如果缓存已满，删除链表尾部的节点
                const removed = this.removeTail();
                delete this.cache[removed.key];
                this.size--;
            }
        }
    }

    // 将节点添加到链表头部
    addToHead(node) {
        node.prev = this.head;
        node.next = this.head.next;
        this.head.next.prev = node;
        this.head.next = node;
    }

    // 删除节点
    removeNode(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 将节点移动到链表头部
    moveToHead(node) {
        this.removeNode(node);
        this.addToHead(node);
    }

    // 删除链表尾部的节点
    removeTail() {
        const node = this.tail.prev;
        this.removeNode(node);
        return node;
    }
}

  
// 使用 map
var LRUCache = function (capacity) {
    this.limit = capacity;
    this.cache = new Map();
};
LRUCache.prototype.get = function (key) {
    let tmp;

    if (this.cache.has(key)) {
        tmp = this.cache.get(key);

        this.cache.delete(key);
        this.cache.set(key, tmp);
    }

    return tmp ?? -1;
};
LRUCache.prototype.put = function (key, value) {
    if (this.cache.has(key)) {
        this.cache.delete(key);
    }
    this.cache.set(key, value);

    if (this.cache.size > this.limit) {
        this.cache.delete(this.cache.keys().next().value);
    }
};