Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

LeetCode 146. LRU缓存机制 #6

Open
yinxin630 opened this issue Feb 18, 2019 · 1 comment
Open

LeetCode 146. LRU缓存机制 #6

yinxin630 opened this issue Feb 18, 2019 · 1 comment
Labels

Comments

@yinxin630
Copy link
Owner

题目

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

思路

  1. 使用Map记录缓存值, 使用链表记录缓存操作顺序, 最后操作的缓存置于链表头部, 链表尾部就是最少操作的缓存
  2. 读取缓存时, 更新缓存操作顺序, 将缓存节点从链表中移除, 再将其添加到链表头部. 移除节点时要保证链表的连续性, 为了在O(1)时间完成该操作, 需要使用双向链表
  3. 设置缓存时, 如果是已存在的缓存, 则直接更新缓存值即可, 并更新缓存操作顺序. 如果是不存在的缓存, 将缓存加到链表头部, 添加后如果缓存超过了上限, 则将链表尾部的缓存清除掉

代码

class DoubleLinkList {
    constructor() {
        this.head = null;
        this.tail = null;
        this.length = 0;
    }

    unshift(node) {
        if (this.head && this.tail) {
            node.prev = null;
            node.next = this.head;
            this.head.prev = node;
            this.head = node;
        } else {
            node.prev = node.next = null;
            this.head = this.tail = node;
        }

        this.length++;
        return node;
    }

    pop() {
        if (this.tail) {
            const node = this.tail;
            if (this.head === this.tail) {
                this.head = this.tail = null;
            } else {
                this.tail.prev.next = null;
                this.tail = this.tail.prev;
            }
            this.length--;
            return node;
        }
    }

    remove(node) {
        if (node !== this.head && node !== this.tail) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        if (node === this.head) {
            this.head = this.head.next;
        }
        if (node === this.tail) {
            this.tail = this.tail.prev;
        }
        this.length--;
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.list = new DoubleLinkList();
        this.map = new Map();
    }

    get(key) {
        let node = this.map.get(key);
        if (node) {
            this.list.remove(node);
            this.list.unshift(node);
            return node.value;
        } else {
            return -1;
        }
    }

    put(key, value) {
        let node = this.map.get(key);
        if (node) {
            node.value = value;
            this.list.remove(node);
            this.list.unshift(node);
        } else {
            node = { key, value };
            this.list.unshift(node);
            this.map.set(key, node);
            if (this.list.length > this.capacity) {
                const tail = this.list.pop();
                this.map.delete(tail.key);
            }
        }
    }
}
@vnues
Copy link

vnues commented Sep 13, 2020

Map这种数据结构本身遍历是有顺序的 按照插入的顺序遍历 所以可以不用链表来记住顺序

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

2 participants