PCH1024

Appearance

反转链表 ​

leetcode

js
var reverseList = function (head) {
    let newHead = head;
    let headNext = head && head.next;
    while (headNext) {
        // 取出 headNext
        head.next = headNext.next;
        // 链接 headNext
        headNext.next = newHead;
        // 重制 newHead
        newHead = headNext;
        // 重制 headNext
        headNext = head.next;
    }
    return newHead;
};
var reverseList = function (head) {
    let newHead = head;
    let headNext = head && head.next;
    while (headNext) {
        // 取出 headNext
        head.next = headNext.next;
        // 链接 headNext
        headNext.next = newHead;
        // 重制 newHead
        newHead = headNext;
        // 重制 headNext
        headNext = head.next;
    }
    return newHead;
};

深拷贝双向链表 ​

leetcode

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。

js
/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */
var copyRandomList = function (head) {
    let list = [];
    let mp = new Map();
    let i = 0;
    while (head) {
        mp.set(head, i);
        const node = new Node(head.val, null, head.random);
        list.push(node);
        head = head.next;
        i++;
    }
    for (let i = 0; i < list.length; i++) {
        let prev = list[i - 1] || null;
        let node = list[i] || null;
        let next = list[i + 1] || null;
        prev && (node.prev = prev);
        node.next = next;
        node.random = node.random && list[mp.get(node.random)];
    }

    return list[0];
};
/**
 * // Definition for a Node.
 * function Node(val, next, random) {
 *    this.val = val;
 *    this.next = next;
 *    this.random = random;
 * };
 */
var copyRandomList = function (head) {
    let list = [];
    let mp = new Map();
    let i = 0;
    while (head) {
        mp.set(head, i);
        const node = new Node(head.val, null, head.random);
        list.push(node);
        head = head.next;
        i++;
    }
    for (let i = 0; i < list.length; i++) {
        let prev = list[i - 1] || null;
        let node = list[i] || null;
        let next = list[i + 1] || null;
        prev && (node.prev = prev);
        node.next = next;
        node.random = node.random && list[mp.get(node.random)];
    }

    return list[0];
};

LRU ​

leetcode

js
// 双向链表
class Link {
    constructor() {
        this.length = 0; // 长度
        this.headNode = null; // 双向链表头节点
        this.lastNode = null; // 双向链表尾节点
    }
    // 前插入
    unshift(node) {
        if (this.headNode) {
            const headNode = this.headNode;
            headNode.prev = node;
            node.next = headNode;
            this.headNode = node;
        } else {
            this.headNode = node;
            this.lastNode = node;
        }
        this.length++;
    }
    // 删除
    delete(node) {
        if (node === this.headNode && node === this.lastNode) {
            // 唯一节点
            this.headNode = null;
            this.lastNode = null;
        } else if (node === this.headNode) {
            // 头节点
            const nextNode = node.next;
            nextNode.prev = null;
            this.headNode = nextNode;
        } else if (node === this.lastNode) {
            // 尾节点
            const prevNode = node.prev;
            prevNode.next = null;
            this.lastNode = prevNode;
        } else {
            // 中间节点
            const nextNode = node.next;
            const prevNode = node.prev;
            prevNode.next = nextNode;
            nextNode.prev = prevNode;
        }
        this.length--;
    }
}
// 链表节点
class LinkNode {
    constructor(key, value) {
        this.key = key; // 健
        this.value = value; // 值
        this.prev = null; // 前节点
        this.next = null; // 后节点
        this.visit = 1; // 访问次数
    }
}

class LRUCache {
    constructor(capacity = 10) {
        this.capacity = capacity; // 容量
        this.link = new Link(); // 双向链表
        this.hash = new Map(); // 哈希表
    }
    get(key) {
        // 存在
        if (this.hash.has(key)) {
            const node = this.hash.get(key);
            this.link.delete(node);
            this.link.unshift(node);
            return node.value;
        }
        // 不存在
        return -1;
    }
    put(key, value) {
        // 存在
        if (this.hash.has(key)) {
            const node = this.hash.get(key);
            this.link.delete(node);
            node.value = value;
            this.link.unshift(node);
            return;
        }
        // 溢出
        if (this.hash.size === this.capacity) {
            const lastNode = this.link.lastNode;
            this.link.delete(lastNode);
            this.hash.delete(lastNode.key);
        }
        // 添加
        const node = new LinkNode(key, value);
        this.hash.set(key, node);
        this.link.unshift(node);
    }
}
// 双向链表
class Link {
    constructor() {
        this.length = 0; // 长度
        this.headNode = null; // 双向链表头节点
        this.lastNode = null; // 双向链表尾节点
    }
    // 前插入
    unshift(node) {
        if (this.headNode) {
            const headNode = this.headNode;
            headNode.prev = node;
            node.next = headNode;
            this.headNode = node;
        } else {
            this.headNode = node;
            this.lastNode = node;
        }
        this.length++;
    }
    // 删除
    delete(node) {
        if (node === this.headNode && node === this.lastNode) {
            // 唯一节点
            this.headNode = null;
            this.lastNode = null;
        } else if (node === this.headNode) {
            // 头节点
            const nextNode = node.next;
            nextNode.prev = null;
            this.headNode = nextNode;
        } else if (node === this.lastNode) {
            // 尾节点
            const prevNode = node.prev;
            prevNode.next = null;
            this.lastNode = prevNode;
        } else {
            // 中间节点
            const nextNode = node.next;
            const prevNode = node.prev;
            prevNode.next = nextNode;
            nextNode.prev = prevNode;
        }
        this.length--;
    }
}
// 链表节点
class LinkNode {
    constructor(key, value) {
        this.key = key; // 健
        this.value = value; // 值
        this.prev = null; // 前节点
        this.next = null; // 后节点
        this.visit = 1; // 访问次数
    }
}

class LRUCache {
    constructor(capacity = 10) {
        this.capacity = capacity; // 容量
        this.link = new Link(); // 双向链表
        this.hash = new Map(); // 哈希表
    }
    get(key) {
        // 存在
        if (this.hash.has(key)) {
            const node = this.hash.get(key);
            this.link.delete(node);
            this.link.unshift(node);
            return node.value;
        }
        // 不存在
        return -1;
    }
    put(key, value) {
        // 存在
        if (this.hash.has(key)) {
            const node = this.hash.get(key);
            this.link.delete(node);
            node.value = value;
            this.link.unshift(node);
            return;
        }
        // 溢出
        if (this.hash.size === this.capacity) {
            const lastNode = this.link.lastNode;
            this.link.delete(lastNode);
            this.hash.delete(lastNode.key);
        }
        // 添加
        const node = new LinkNode(key, value);
        this.hash.set(key, node);
        this.link.unshift(node);
    }
}

LFU ​

leetcode

js
// 双向链表节点
class LinkNode {
    constructor(key, value) {
        this.key = key; // 健
        this.value = value; // 值
        this.prev = null; // 前节点
        this.next = null; // 后节点
        this.visit = 1; // 访问次数
    }
}
// 双向链表
class Link {
    constructor() {
        this.length = 0; // 长度
        this.headNode = null; // 双向链表头节点
        this.lastNode = null; // 双向链表尾节点
    }
    // 前插入
    unshift(node) {
        if (this.headNode) {
            const headNode = this.headNode;
            headNode.prev = node;
            node.next = headNode;
            this.headNode = node;
        } else {
            this.headNode = node;
            this.lastNode = node;
        }
        this.length++;
    }
    // 删除
    delete(node) {
        if (node === this.headNode && node === this.lastNode) {
            // 唯一节点
            this.headNode = null;
            this.lastNode = null;
        } else if (node === this.headNode) {
            // 头节点
            const nextNode = node.next;
            nextNode.prev = null;
            this.headNode = nextNode;
        } else if (node === this.lastNode) {
            // 尾节点
            const prevNode = node.prev;
            prevNode.next = null;
            this.lastNode = prevNode;
        } else {
            // 中间节点
            const nextNode = node.next;
            const prevNode = node.prev;
            prevNode.next = nextNode;
            nextNode.prev = prevNode;
        }
        this.length--;
    }
}

// LRU Cache 类
class LFUCache {
    constructor(capacity = 10) {
        this.capacity = capacity; // 容量
        this.hash = new Map(); // 哈希表
        this.min = 0; // 最少访问
        this.links = [
            // 访问分层存储数据结构
            // new Link() // 最久访问
        ];
    }
    getLink(visit) {
        if (!this.links[visit]) {
            this.links[visit] = new Link();
        }
        return this.links[visit];
    }
    updateNode(node, value) {
        const link = this.getLink(node.visit);
        if (this.min === node.visit && link.length === 1) {
            this.min++; // 最小且唯一，则 min++
        }
        // 更新 visit
        link.delete(node);
        node.visit += 1;
        node.value = value || node.value;
        this.getLink(node.visit).unshift(node);
    }
    get(key) {
        if (this.hash.has(key)) {
            const node = this.hash.get(key);
            this.updateNode(node, node.value);
            return node.value;
        }
        return -1;
    }
    put(key, value) {
        if (this.hash.has(key)) {
            // 已存在
            const node = this.hash.get(key);
            this.updateNode(node, value);
            return;
        }
        if (this.hash.size === this.capacity) {
            // 溢出先删除最少最旧
            const minLink = this.links[this.min];
            const oldNode = minLink.lastNode;
            minLink.delete(oldNode);
            this.hash.delete(oldNode.key);
        }
        // 添加
        const node = new LinkNode(key, value);
        this.min = 1;
        this.hash.set(key, node);
        const link = this.getLink(1);
        link.unshift(node);
    }
}
// 双向链表节点
class LinkNode {
    constructor(key, value) {
        this.key = key; // 健
        this.value = value; // 值
        this.prev = null; // 前节点
        this.next = null; // 后节点
        this.visit = 1; // 访问次数
    }
}
// 双向链表
class Link {
    constructor() {
        this.length = 0; // 长度
        this.headNode = null; // 双向链表头节点
        this.lastNode = null; // 双向链表尾节点
    }
    // 前插入
    unshift(node) {
        if (this.headNode) {
            const headNode = this.headNode;
            headNode.prev = node;
            node.next = headNode;
            this.headNode = node;
        } else {
            this.headNode = node;
            this.lastNode = node;
        }
        this.length++;
    }
    // 删除
    delete(node) {
        if (node === this.headNode && node === this.lastNode) {
            // 唯一节点
            this.headNode = null;
            this.lastNode = null;
        } else if (node === this.headNode) {
            // 头节点
            const nextNode = node.next;
            nextNode.prev = null;
            this.headNode = nextNode;
        } else if (node === this.lastNode) {
            // 尾节点
            const prevNode = node.prev;
            prevNode.next = null;
            this.lastNode = prevNode;
        } else {
            // 中间节点
            const nextNode = node.next;
            const prevNode = node.prev;
            prevNode.next = nextNode;
            nextNode.prev = prevNode;
        }
        this.length--;
    }
}

// LRU Cache 类
class LFUCache {
    constructor(capacity = 10) {
        this.capacity = capacity; // 容量
        this.hash = new Map(); // 哈希表
        this.min = 0; // 最少访问
        this.links = [
            // 访问分层存储数据结构
            // new Link() // 最久访问
        ];
    }
    getLink(visit) {
        if (!this.links[visit]) {
            this.links[visit] = new Link();
        }
        return this.links[visit];
    }
    updateNode(node, value) {
        const link = this.getLink(node.visit);
        if (this.min === node.visit && link.length === 1) {
            this.min++; // 最小且唯一，则 min++
        }
        // 更新 visit
        link.delete(node);
        node.visit += 1;
        node.value = value || node.value;
        this.getLink(node.visit).unshift(node);
    }
    get(key) {
        if (this.hash.has(key)) {
            const node = this.hash.get(key);
            this.updateNode(node, node.value);
            return node.value;
        }
        return -1;
    }
    put(key, value) {
        if (this.hash.has(key)) {
            // 已存在
            const node = this.hash.get(key);
            this.updateNode(node, value);
            return;
        }
        if (this.hash.size === this.capacity) {
            // 溢出先删除最少最旧
            const minLink = this.links[this.min];
            const oldNode = minLink.lastNode;
            minLink.delete(oldNode);
            this.hash.delete(oldNode.key);
        }
        // 添加
        const node = new LinkNode(key, value);
        this.min = 1;
        this.hash.set(key, node);
        const link = this.getLink(1);
        link.unshift(node);
    }
}

༼ つ/̵͇̿̿/’̿’̿ ̿ ̿̿ ̿̿◕ _◕ ༽つ/̵͇̿̿/’̿’̿ ̿ ̿̿ ̿̿ ̿̿

COPYRIGHT © 1992-PRESENT PCH1024-V1.0.64