【Day 12 】2021-12-23 - 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

[Grendelta]

思路

建立一个双向哈希链表

代码

class DLinkedNode: def init(self, key=0, value=0): self.key = key self.value = value self.prev = None self.next = None

class LRUCache:

def __init__(self, capacity):
    self.capacity = capacity
    self.size = 0
    self.cache = dict()
    self.head = DLinkedNode()
    self.tail = DLinkedNode()
    self.head.next = self.tail
    self.tail.prev = self.head

def get(self, key):
    if key in self.cache:
        node = self.cache[key]
        self.moveToHead(node)
        return node.value
    else:
        return -1

def put(self, key, value):
    # 若在cache中
    if key in self.cache:
        node = self.cache[key]
        node.value = value
        self.moveToHead(node)

    # 若不在cache中
    else:
        node =  DLinkedNode(key, value)
        # 添加到head.next
        self.addToHead(node)

        # 更新cache
        self.cache[key] = node

        # 满了，要删除tial.prev
        if self.size > self.capacity: 
            self.cache.pop(self.tail.prev.key)
            self.remove(self.tail.prev)

def addToHead(self, node):
    node.next = self.head.next
    self.head.next.prev = node
    node.prev = self.head
    self.head.next = node
    self.size += 1

def remove(self, node):
    node.prev.next = node.next
    node.next.prev = node.prev
    self.size -= 1
    return 

def moveToHead(self, node):
    self.remove(node)
    self.addToHead(node)

复杂度

时间复杂度 O(1) 空间复杂度 O(N)

[yan0327]

思路： 太久不会写忘记了=-=重新复习了一下。 关键LRU算法是 哈希表+双向链表组成 双向链表需要pre、next，同时记录key，value值 便于查询 LRU结构体需要的是 哈希表[key]*DLinkNode, capcity容量，size大小，头和尾节点 同时，我们自己实现四个函数来简化设计。 第一个函数添加到头，因为LRU用完一个节点要添加到头部。 这里的做法是把node直接插入head和head.Next中间，同时令head.Next.prev = node ,head.next = node [注意顺序] 第二个函数是移除节点：双向链表的移除很简单： 直接node.prev.next = node.next ；node.next.prev = node.prev 第三个函数是移动到头节点，就是前两个函数的拼接 第四个函数是删除尾节点，为了保证当size＞capcity时移除最久使用的节点。 直接从尾节点读前缀节点，调用移除节点，返回该节点。

对于put的话，需要检测当前当前的key是否存在，若存在则直接修改value值，并调用移动到链表头函数， 如果key不存在，则添加到节点到头部，size++，并判断size是否大于capcity，若大于则移除尾节点【记得删除哈希表的key值】 GO语言的删除是delete(this.cache,removed.key) 对于get的话，直接判断节点是否存在，若存在则读cache并返回值，否则返回1

type DLinkNode struct{
    key,value int
    prev,next *DLinkNode
}

type LRUCache struct {
    size int
    capacity int
    cache map[int]*DLinkNode
    head,tail *DLinkNode
}
func InitDLinkNode (key,value int) *DLinkNode{
    return &DLinkNode{
        key:key,
        value:value,
    }
}

func Constructor(capacity int) LRUCache {
    l := LRUCache{
        cache:map[int]*DLinkNode{},
        head:InitDLinkNode(0,0),
        tail:InitDLinkNode(0,0),
        capacity:capacity,
    }
    l.head.next = l.tail
    l.tail.prev = l.head
    return l
}

func (this *LRUCache) Get(key int) int {
    if _,ok := this.cache[key];ok{
        node := this.cache[key]
        this.moveToHead(node)
        return node.value
    }else{
        return -1
    }
}

func (this *LRUCache) Put(key int, value int)  {
    if _,ok := this.cache[key];!ok{
        node := InitDLinkNode(key,value)
        this.cache[key] =node
        this.addToHead(node)
        this.size++
        if this.size > this.capacity{
            removed := this.removeNodeTail()
            delete(this.cache,removed.key)
            this.size--
        }
    }else{
        node := this.cache[key]
        node.value = value
        this.moveToHead(node)
    }
}
func (this *LRUCache) addToHead(node *DLinkNode){
    node.prev = this.head
    node.next = this.head.next
    this.head.next.prev = node
    this.head.next = node
}
func(this *LRUCache) removeNode(node *DLinkNode){
    node.prev.next = node.next
    node.next.prev = node.prev
}
func(this *LRUCache) moveToHead(node *DLinkNode){
    this.removeNode(node)
    this.addToHead(node)
}
func(this *LRUCache) removeNodeTail() *DLinkNode{
    node := this.tail.prev
    this.removeNode(node)
    return node
}

时间复杂度O（1） 空间复杂度O(1)

[chakochako]

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

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = dict()
        self.head = DlinkNode()
        self.tail = DlinkNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache.get(key)
        self.moveToHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            node = DlinkNode(key, value)
            self.cache[key] = node
            self.addToHead(node)
            self.size = self.size + 1
            if self.size > self.capacity:
                removed = self.removeTail()
                self.cache.pop(removed.key)
                self.size = self.size - 1
        else:
            node = self.cache.get(key)
            node.value = value
            self.moveToHead(node)

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

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

    def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)

    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

[q815101630]

LRU

使用 linkedList 来创建 LRU 缓存。

class Node:
    def __init__(self,key=0, value=0):
        self.key = key
        self.val = value
        self.prev = None
        self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.hash = {}
        self.head = Node()
        self.last = Node()
        self.head.next = self.last
        self.last.prev = self.head
        self.capacity = capacity
        self.size = 0

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

        node.prev.next = node.next
        node.next.prev = node.prev
        self.appendToHead(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.hash:
            node = self.hash[key]
            node.val = value

            node.prev.next = node.next
            node.next.prev = node.prev

            self.appendToHead(node)
            return
        if self.size < self.capacity:
            node = Node(key, value)
            self.hash[key] = node
            self.appendToHead(node)
            self.size+=1
        else:
            self.replaceNode(key, value)

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

    def replaceNode(self, newKey, newVal):
        deleted = self.last.prev

        del self.hash[deleted.key]
        deleted.key = newKey
        deleted.val = newVal
        self.hash[newKey] = deleted

        deleted.prev.next = deleted.next
        deleted.next.prev = deleted.prev
        self.appendToHead(deleted)

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

操作都是常数时间

[feifan-bai]

思路

1. Hash table + double linked list
2. Double linked list stores the key-value pairs, with the order that the pairs near the head are the most recently used.
3. Hash table maps the key of the cached data to its position in the Double linked list.
4. First use the hash table to find the position of the cache item, then move it to the head of the double linked list.

代码

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

class DoubleList:
    def __init__(self):
        self.head = Node(-1, -1)
        self.tail = Node(-1, -1)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def addFirst(self, x):
        x.next = self.head.next
        x.prev = self.head
        self.head.next.prev = x
        self.head.next = x
        self.size += 1

    def remove(self, x):
        x.prev.next = x.next
        x.next.prev = x.prev
        self.size -= 1

    def removelast(self):
        if self.size == 0: 
            return None
        last_node = self.tail.prev
        self.remove(last_node)
        return last_node

    def getSize(self):
        return self.size

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}
        self.cache = DoubleList()

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        val = self.map[key].val
        self.put(key, val)
        return val

    def put(self, key:int, value:int) -> None:
        new_item = Node(key, value)
        if key in self.map:
            self.cache.remove(self.map[key])
            self.cache.addFirst(new_item)
            self.map[key] = new_item
        else:
            if self.capacity == self.cache.getSize():
                last_node = self.cache.removelast()
                self.map.pop(last_node.key)
            self.cache.addFirst(new_item)
            self.map[key] = new_item

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

复杂度分析

• 时间复杂度：O(1)
• 空间复杂度：O(N), N = capacity

[pengfeichencpf]

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

private int capacity;
private Map<Integer, Node> map;
private Node dummyhead, dummytail;

public LRUCache(int capacity) {
    this.capacity = capacity;
    this.map = new HashMap<>();
    this.dummyhead = new Node(-1, -1);
    this.dummytail = new Node(-1, -1);
    this.dummyhead.next = this.dummytail;
    this.dummytail.prev = this.dummyhead;
}

public int get(int key) {
    Node node = getNode(key);
    if(null == node) return -1;
    return node.value;
}

Node getNode(int key) {
    Node node = map.get(key);
    if(null == node) return null;
    disconnect(node);
    insertHead(node);
    return node;
}

void disconnect(Node node) {
    node.next.prev = node.prev;
    node.prev.next = node.next;        
}

void insertHead(Node node) {
    node.next = dummyhead.next;
    dummyhead.next.prev = node;
    node.prev = dummyhead;
    dummyhead.next = node;        
}

public void put(int key, int value) {
    Node node = getNode(key);
    if(null != node) {
        node.value = value;
    }
    else {
        node = new Node(key, value);
        insertHead(node);

        map.put(key, node);
        if(map.size() > capacity) {
            Node tail = dummytail.prev;
            disconnect(tail);
            map.remove(tail.key);
        }
    }
}

}

[tian-pengfei]

struct ListNode2 {
      int val;
      ListNode2 *next;
      ListNode2 *pre;
      ListNode2() : val(0), next(nullptr),pre(nullptr) {}
      ListNode2(int x) : val(x), next(nullptr),pre(nullptr) {}
      ListNode2(int x, ListNode2 *pre,ListNode2 *next) : val(x), next(pre),pre(nullptr) {}
  };

class LRUCache {

    map<int,ListNode2*> m;
    int cap=0;
    int size=0;
    ListNode2* head = new ListNode2(-1);
    ListNode2* tail = new ListNode2(-1);
public:
    LRUCache(int capacity) {
        head->next=tail;
        tail->next=head;
        cap=capacity;
    }

    int get(int key) {
        if(m.find(key)==m.end()){
            return -1;
        }
        ListNode2 * node = m.at(key);
        ListNode2 *pre = node->pre;
        ListNode2 *next = node->next;
        pre->next = next;
        next->pre = pre;
        //放到头部
        ListNode2* head_next = head->next;
        head->next=node;
        node->pre=head;
        node->next=head_next;
        head_next->pre = node;
        return node->val;
    }

    void put(int key, int value) {
        ListNode2 * node = nullptr;
        ListNode2* head_next = head->next;
        if(m.find(key)==m.end()){
            if(size+1>cap){
                ListNode2 *deleteNode = tail->pre;
                deleteNode->pre->next=tail;
                tail->pre=deleteNode->pre;
                m.erase(deleteNode->val);
                delete deleteNode;

            } else{
                size++;
            }
            node =new ListNode2(value);
            m[key]=node;
        } else{
            node = m.at(key);
            node->val=value;
            ListNode2 *pre = node->pre;
            ListNode2 *next = node->next;
            pre->next = next;
            next->pre = pre;
        }

        //放到头部
        head->next=node;
        node->pre=head;
        node->next=head_next;
        head_next->pre = node;
    }
};

[Bochengwan]

思路

通过双端队列，使得put和get达到O(1)的时间复杂度

代码

class Node:
    def __init__(self):
        self.key = 0
        self.value = 0
        self.prev = None
        self.next = None

class LRUCache:
    def _add_node(self,node):
        node.next = self.head.next
        node.prev = self.head

        self.head.next.prev = node
        self.head.next = node
    def _remove_node(self,node):
        prev = node.prev
        new = node.next
        prev.next = new
        new.prev = prev 

    def __init__(self, capacity: int):
        self.capacity =capacity
        self.size = 0 
        self.head,self.tail = Node(),Node()
        self.cache={}
        self.head.next,self.tail.prev= self.tail,self.head

    def get(self, key: int) -> int:
        node = self.cache.get(key,None)
        if not node:
            return -1
        self._remove_node(node)
        self._add_node(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        curr = self.cache.get(key,None)
        if not curr:
            node = Node()
            node.key = key
            node.value = value
            self.cache[key] = node
            self._add_node(node)
            self.size+=1
        else:
            curr.value = value
            self._remove_node(curr)
            self._add_node(curr)

        if self.size > self.capacity:
            the_node  = self.tail.prev
            self._remove_node(the_node)

            self.cache.pop(the_node.key)
            self.size-=1

复杂度分析

• 时间复杂度：O(1)
• 空间复杂度：O(Capacity)

[Victoria011]

基本思路

使用 hashmap + doubleLinkedList 。

代码

class LRUCache:
    def __init__(self, MSize):
        self.size = MSize
        self.cache = {}
        self.next, self.before = {}, {}
        self.head, self.tail = '#', '$'
        self.connect(self.head, self.tail)

    def connect(self, a, b):
        self.next[a], self.before[b] = b, a

    def delete(self, key):
        self.connect(self.before[key], self.next[key])
        del self.before[key], self.next[key], self.cache[key]

    def append(self, k, v):
        self.cache[k] = v
        self.connect(self.before[self.tail], k)
        self.connect(k, self.tail)
        if len(self.cache) > self.size:
            self.delete(self.next[self.head])

    def get(self, key):
        if key not in self.cache: return -1
        val = self.cache[key]
        self.delete(key)
        self.append(key, val)
        return val

    def put(self, key, value):
        if key in self.cache: self.delete(key)
        self.append(key, value)       

复杂度分析

Time complexity: O(1)

Space complexity: O(Capacity)

[ZhangNN2018]

思路

• 哈希表，，但无序，
• 调用collections.OrderedDict()先删再插入，使每次使用过的key变到最后面

复杂度

• 时间复杂度: O(N), N=capacity；
• 空间复杂度: O(N)。

代码

class LRUCache(object):

    def __init__(self, capacity):
        self.data = collections.OrderedDict()
        self.capacity = capacity 

    def get(self, key):
        if key in self.data: #如果存在，就先删除
            self.data[key] = self.data.pop(key) #再重新插入，变成末尾
            return self.data[key]
        return -1

    def put(self, key, value):
        if key in self.data: #key存在，先删除
            self.data.pop(key)  
        self.data[key] = value #再插入key，这时在最后面
        if len(self.data)>self.capacity: #如果长度超了
            self.data.popitem(last = False) #把前面的删掉一个

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

[pangjiadai]

Python3

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

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.hashmap = {} # {key: key, value: node}
        self.size = 0

    def get(self, key: int) -> int:
        if key not in self.hashmap:
            return -1
        node = self.hashmap[key]
        self.moveToHead(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.hashmap:
            node = self.hashmap[key]
            node.val = value
            self.moveToHead(node)

        else:
            node = ListNode(key, value)
            self.addToHead(node)
            self.hashmap[key] = node
            self.size += 1
            if self.size > self.capacity:
                removed = self.removeTail()
                self.hashmap.pop(removed.key)
                self.size -= 1

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

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

    def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)

    def removeTail(self):
        prev = self.tail.prev
        self.removeNode(prev)
        return prev

[zwmanman]

思路

1. use a dictionary to store key: node
2. use a doubly linked list to track latest used node
3. every operation will cause the node remove from current location and add to the end of linked list

代码

（此处撰写代码）
class Node(object):
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None
        self.prev = None

class LRUCache(object):

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

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key in self.dict:
            node = self.dict[key]
            self._remove(node)
            self._add(node)
            return node.val
        else:
            return -1

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if key in self.dict:
            self._remove(self.dict[key])
        node = Node(key, value)
        self._add(node)
        self.dict[key] = node
        if len(self.dict) > self.capacity:
            node = self.head.next
            self._remove(node)
            del self.dict[node.key]

    def _remove(self, node):
        p = node.prev
        n = node.next
        p.next = n
        n.prev = p

        # h, 1, 2, 3 t
    def _add(self, node):
        p = self.tail.prev
        p.next = node
        node.prev = p
        node.next = self.tail
        self.tail.prev = node

复杂度分析

• 时间复杂度：O(N)，其中 N Capacity。
• 空间复杂度：O(N)

[laofuWF]

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

class LRUCache:

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

    def remove(self, node):
        del self.dict[node.key]
        self.capacity += 1

        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = None

    def insert(self, node):
        self.dict[node.key] = node
        self.capacity -= 1

        self.tail.prev.next = node
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev = node

    def get(self, key: int) -> int:
        if key not in self.dict:
            return -1
        node = self.dict[key]
        self.remove(node)
        self.insert(node)

        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.dict:
            self.remove(self.dict[key])
        self.insert(ListNode(key, value))
        if self.capacity < 0:
            self.remove(self.head.next)

[RocJeMaintiendrai]

代码

class LRUCache {
    private Map<Integer, Node> map;
    private int capacity;
    private int count;
    private Node head;
    private Node tail;

    public LRUCache(int capacity) {
        map = new HashMap<>();
        this.capacity = capacity;
        count = 0;
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.pre = head;
        head.pre = null;
        tail.next = null;
    }

    public int get(int key) {
        if(map.get(key) != null) {
            Node node = map.get(key);
            int val = node.val;
            deleteNode(node);
            addToHead(node);
            return val;
        }
        return -1;
    }

    public void put(int key, int value) {
        if(map.get(key) != null) {
            Node node = map.get(key);
            node.val = value;
            deleteNode(node);
            addToHead(node);
        } else {
            Node node = new Node(key, value);
            map.put(key, node);
            if(count < capacity) {
                count++;
                addToHead(node);
            } else {
                map.remove(tail.pre.key);
                deleteNode(tail.pre);
                addToHead(node);
            }
        }
    }

    private void deleteNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void addToHead(Node node) {
        node.next = head.next;
        node.next.pre = node;
        node.pre = head;
        head.next = node;
    }
}

class Node {
    int key;
    int val;
    Node next;
    Node pre;
    public Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

复杂度分析

• 时间复杂度：O(1)
• 空间复杂度：O(n)

[Okkband]

struct DLinkedNode{
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr){}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr){}
};
class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;
public:
    LRUCache(int _capacity){
        capacity = _capacity;
        size = 0;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }

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

    void put(int key, int value) {
        if (!cache.count(key)){ // 如果cache中不存在key， 
            // 创建一个新的节点
            DLinkedNode* node = new DLinkedNode(key, value);
            //添加进哈希表内
            cache[key] = node;
            //添加至双向链表头部
            addToHead(node);
            ++size; // size 加1
            if (size > capacity){ // cache大小超过容量
                DLinkedNode* removed = removeTail(); // 删除尾部节点
                cache.erase(removed->key); // 删除哈希表索引
                delete removed; //防止内存泄漏
                --size;
            }
        } else { // key在cache中
            DLinkedNode* node = cache[key]; // 定位节点位置
            node->value = value; // 修改value
            moveToHead(node); // 移动至头部
        }
    }
    void addToHead(DLinkedNode* node){
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    void removeNode(DLinkedNode* node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    void moveToHead(DLinkedNode* node){
        removeNode(node);
        addToHead(node);
    }
    DLinkedNode* removeTail(){
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }

};

[Alexno1no2]

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

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hashmap = {}
        # 新建两个节点 head 和 tail
        self.head = ListNode()
        self.tail = ListNode()
        # 初始化链表为 head <-> tail
        self.head.next = self.tail
        self.tail.prev = self.head

    # 因为get与put操作都可能需要将双向链表中的某个节点移到头部(变成最新访问的)，所以定义一个方法
    def move_node_to_header(self, key):
            # 先将哈希表key指向的节点拎出来，为了简洁起名node
            #      hashmap[key]                               hashmap[key]
            #           |                                          |
            #           V              -->                         V
            # prev <-> node <-> next         pre <-> next   ...   node
            node = self.hashmap[key]
            node.prev.next = node.next
            node.next.prev = node.prev
            # 之后将node插入到头部节点前
            #                   hashmap[key]                     hashmap[key]
            #                       |                                 |
            #                       V        -->                      V
            # header <-> next  ... node                   header <-> node <-> next
            node.prev = self.head
            node.next = self.head.next
            self.head.next.prev = node
            self.head.next = node

    def add_node_to_header(self, key,value):
        new = ListNode(key, value)
        self.hashmap[key] = new
        new.prev = self.head
        new.next = self.head.next
        self.head.next.prev = new
        self.head.next = new

    def pop_tail(self):
        last_node = self.tail.prev
        # 去掉链表尾部的节点在哈希表的对应项
        self.hashmap.pop(last_node.key)
        # 去掉最久没有被访问过的节点，即尾部Tail之前的一个节点
        last_node.prev.next = self.tail
        self.tail.prev = last_node.prev
        return last_node

    def get(self, key: int) -> int:
        if key in self.hashmap:
            # 如果已经在链表中了久把它移到头部（变成最新访问的）
            self.move_node_to_header(key)
        res = self.hashmap.get(key, -1)
        if res == -1:
            return res
        else:
            return res.value

    def put(self, key: int, value: int) -> None:
        if key in self.hashmap:
            # 如果key本身已经在哈希表中了就不需要在链表中加入新的节点
            # 但是需要更新字典该值对应节点的value
            self.hashmap[key].value = value
            # 之后将该节点移到链表头部
            self.move_node_to_header(key)
        else:
            if len(self.hashmap) >= self.capacity:
            # 若cache容量已满，删除cache中最不常用的节点 
                self.pop_tail()
            self.add_node_to_header(key,value)

[ZacheryCao]

Idea

Ordered Dictionary

Code:

class LRUCache:

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

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

    def put(self, key: int, value: int) -> None:
        if key in self.dict:
            self.dict[key] = value
            self.dict.move_to_end(key)
        else:
            if len(self.dict)>=self.capacity:
                self.dict.popitem(last=False)
            self.dict[key] = value

Complexity:

Time: O(1) to put and get Space: O(capacity)

[zhangyalei1026]

Code

class ListNode:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None
        self.pre = None
class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.d = {}
        self.head = ListNode(-1,-1)
        self.tail = ListNode(-1, -1)
        self.head.next = self.tail
        self.tail.pre = self.head
        # key 是value, key对应的value是double linkedlist 的node
    def move_to_tail(self, key):
        node = self.d[key]
        node.pre.next = node.next
        node.next.pre = node.pre
        self.tail.pre.next = node
        node.pre = self.tail.pre
        node.next = self.tail
        self.tail.pre = node

    def get(self, key: int) -> int:
        if key in self.d:
            self.move_to_tail(key)
            return self.d[key].val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.d:
            self.d[key].val = value
            self.move_to_tail(key)
        else:
            if len(self.d) == self.capacity:
                del self.d[self.head.next.key]
                self.head.next = self.head.next.next
                self.head.next.pre = self.head

                # delete a LRU, then put new pair in     
            self.d[key] = ListNode(key, value)
            new = self.d[key]
            self.tail.pre.next = new
            new.pre = self.tail.pre
            new.next = self.tail
            self.tail.pre = new

Complexity

Time complexity: O(1) Space complexity: O(capacity)

[Husky-Gong]

class LRUCache {
    // 思路：
    // 1. get() 的时间复杂度为O(1)，使用map；put的时间复杂度为O(1)也使用map。
    //    但是，因为要将最常使用的放在最前面，则需要考虑到一个排序的过程  
    //        -> 使用linkedlist 
    //        -> 当capacity放满了，并且有新的放入，则将尾部的去掉
    //    所以，要使用linkedlist和hashmap
    //    get的时候，如果map存在该key，取出对应的val返回，并且需要把它放在linkedlist的头部
    //        -> 所以，需要创建两个方程：addHead(Node)：将node放在头部，表示最近用过
    //                               remove(Node)：将放在头部的node去除掉
    // 2. put(int key, int value)的时间复杂度为O1
    //        -> 1. 如果node存在，则将node重新放在linkedlist的头部
    //              -> 首先取出node，再remove，再addHead
    //        -> 2. 如果node不存在，则将node直接放在linkedlist头部

    class Node {
        int key;
        int val;
        Node prev;
        Node next;

        public Node (int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    Node head;
    Node tail;
    int capacity;
    int size;

    HashMap<Integer, Node> map;

    public LRUCache(int capacity) {
        // 初始化linkedlist和hashmap
        map = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);

        head.next = tail;
        tail.prev = head;

        this.capacity = capacity;
    }

    // get的时候，从map中拿，然后放在linkedlist最前面
    public int get(int key) {
        if (map.containsKey(key)) {
            Node temp = map.get(key);
            remove(temp);
            addHead(key, temp.val);
            return temp.val;
        } else {
            return -1;
        }
    }
    // 从linkedlist中取出掉一个node
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
        // 从map中删除
        map.remove(node.key);
    }

    // 加入到头结点，再判断是否超出capacity
    private void addHead(int key, int val) {
        Node temp = new Node(key, val);
        Node next = head.next;
        temp.next = next;
        next.prev = temp;
        head.next = temp;
        temp.prev = head;

        map.put(key, temp);
        size++;

        if (size > capacity) {
            Node temp2 = tail.prev;
            remove(temp2);
        }

    }

    // 判断map中是否存在该node，如果不存在直接放在linkedlist最前面
    // 如果存在该node，就取出来，再remove，再放在最前面
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node temp = map.get(key);
            remove(temp);
            addHead(key, value);
        } else {
            addHead(key, value);
        }
    }
}

[yugaoh]

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

private int capacity; private Map<Integer, Node> map; private Node dummyhead, dummytail;

public LRUCache(int capacity) { this.capacity = capacity; this.map = new HashMap<>(); this.dummyhead = new Node(-1, -1); this.dummytail = new Node(-1, -1); this.dummyhead.next = this.dummytail; this.dummytail.prev = this.dummyhead; }

public int get(int key) { Node node = getNode(key); if(null == node) return -1; return node.value; }

Node getNode(int key) { Node node = map.get(key); if(null == node) return null; disconnect(node); insertHead(node); return node; }

void disconnect(Node node) { node.next.prev = node.prev; node.prev.next = node.next;
}

void insertHead(Node node) { node.next = dummyhead.next; dummyhead.next.prev = node; node.prev = dummyhead; dummyhead.next = node;
}

public void put(int key, int value) { Node node = getNode(key); if(null != node) { node.value = value; } else { node = new Node(key, value); insertHead(node);

    map.put(key, node);
    if(map.size() > capacity) {
        Node tail = dummytail.prev;
        disconnect(tail);
        map.remove(tail.key);
    }
}

} }

[zhiyuanpeng]

class DLinkedNode(): 
    def __init__(self):
        self.key = 0
        self.value = 0
        self.prev = None
        self.next = None

class LRUCache:

    def _add_node(self, node):
        """
        """
        node.prev = self.head
        node.next = self.head.next

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

    def _remove_node(self, node):
        prev = node.prev
        new = node.next

        prev.next = new
        new.prev = prev

    def _move_to_head(self, node):
        self._remove_node(node)
        self._add_node(node)

    def _pop_tail(self):
        res = self.tail.prev
        self._remove_node(res)
        return res

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.cache = {}
        self.size = 0
        self.capacity = capacity
        self.head, self.tail = DLinkedNode(), DLinkedNode()

        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:

        node = self.cache.get(key, None)
        if not node:
            return -1

        # move the accessed node to the head;
        self._move_to_head(node)

        return node.value

    def put(self, key: int, value: int) -> None:

        node = self.cache.get(key)

        if not node: 
            newNode = DLinkedNode()
            newNode.key = key
            newNode.value = value

            self.cache[key] = newNode
            self._add_node(newNode)

            self.size += 1

            if self.size > self.capacity:
                # pop the tail
                tail = self._pop_tail()
                del self.cache[tail.key]
                self.size -= 1
        else:
            # update the value.
            node.value = value
            self._move_to_head(node)

time O(1), space O(N)

[hdyhdy]

思路： 双链表以及哈希表 关键在于把访问过的都放在最前面，这样才能实现题目的O（1）的要求

type LRUCache struct {
    size int
    capacity int
    cache map[int]*DLinkedNode
    head, tail *DLinkedNode
}

type DLinkedNode struct {
    key, value int
    prev, next *DLinkedNode
}

func initDLinkedNode(key, value int) *DLinkedNode{
    return &DLinkedNode{
        key :key,
        value:value,
    }
}

func Constructor(capacity int) LRUCache {
    l :=LRUCache{
        cache : map[int]*DLinkedNode{},
        head : initDLinkedNode(0, 0),
        tail : initDLinkedNode(0, 0),
        capacity: capacity,
    }
    l.head.next = l.tail
    l.tail.prev = l.head
    return l
}

func (this *LRUCache) Get(key int) int {
    if _,ok := this.cache[key]; !ok{
        return -1
    }
    node := this.cache[key]
    this.moveToHead(node)
    return node.value 
}

func (this *LRUCache) Put(key int, value int)  {
    if _,ok := this.cache[key]; !ok {
        node := initDLinkedNode(key, value)
        this.cache[key] = node
        this.addToHead(node)
        this.size++
        if this.size > this.capacity {
            removed := this.removeTail()
            delete(this.cache, removed.key)
            this.size -- 
        }
    } else {
        node :=this.cache[key]
        node.value = value
        this.moveToHead(node)
    }
}

func (this *LRUCache) addToHead(node *DLinkedNode){
    node.prev = this.head 
    node.next = this.head.next
    this.head.next.prev = node 
    this.head.next = node
}

func (this *LRUCache) removeToHead(node *DLinkedNode){
    node.prev.next = node.next
    node.next.prev = node.prev
}

func (this *LRUCache) moveToHead(node *DLinkedNode){
    this.removeToHead(node)
    this.addToHead(node)
}

func (this *LRUCache) removeTail() *DLinkedNode {
    node := this.tail.prev
    this.removeToHead(node)
    return node 
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

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

空间复杂度：O(capacity)

[Yark-yao]

思路

数据存储是key-value的形式，因此自然的想到使用Map存储数据；难点在于put的时候，超出容量时需要先删除最久未被访问的数据，我得思路是：每次get访问时，将map中的key先删掉，再set到map的末尾，在超出容量时，将map的第一个元素删除

代码

class LRUCache {
  // key {value,visit}
  private cacheMap = new Map();

  private capacity = 0;
  constructor(capacity: number) {
    this.capacity = capacity;
  }

  get(key: number): number {
    if (this.cacheMap.has(key)) {
      const data = this.cacheMap.get(key);
      this.cacheMap.delete(key);
      this.cacheMap.set(key, data);
      return data;
    } else {
      return -1;
    }
  }

  put(key: number, value: number): void {
    // 考虑 key已经存在的情况，则只是更新值
    if (this.cacheMap.get(key)) {
      this.cacheMap.delete(key);
    } else {
      const size = this.cacheMap.size;
      if (size >= this.capacity) {
        // 删除map的第一个元素
        for (let [iterKey] of this.cacheMap) {
          this.cacheMap.delete(iterKey);
          break;
        }
      }
    }

    this.cacheMap.set(key, value);
  }
}

复杂度

空间: O(N) 时间: O(1)

[ZJP1483469269]

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

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = dict()
        # 使用伪头部和伪尾部节点    
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # 如果 key 存在，先通过哈希表定位，再移到头部
        node = self.cache[key]
        self.moveToHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            # 如果 key 不存在，创建一个新的节点
            node = DLinkedNode(key, value)
            # 添加进哈希表
            self.cache[key] = node
            # 添加至双向链表的头部
            self.addToHead(node)
            self.size += 1
            if self.size > self.capacity:
                # 如果超出容量，删除双向链表的尾部节点
                removed = self.removeTail()
                # 删除哈希表中对应的项
                self.cache.pop(removed.key)
                self.size -= 1
        else:
            # 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)

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

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

    def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)

    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

[rzhao010]

Thoughts There would be two data structures, one for saving data, another for tracking the recently used.

For data store, a hashmap can realize O(1) read and write For tracking, linkedlist is better in add and remove compared with array. A doublylinkedlist is better than a single one, we can manage the "latest" at head, and least recently used at tail.

Code

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

    Map<Integer, DoublyLinkedNode> cache;
    DoublyLinkedNode head, tail;
    private int size, capacity;
    public LRUCache(int capacity) {
        cache = new HashMap<Integer, DoublyLinkedNode>();
        head = new DoublyLinkedNode();
        tail = new DoublyLinkedNode();
        head.next = tail;
        tail.prev = head;
        size = 0;
        this.capacity = capacity;
    }

    public int get(int key) {
        //1. get value from cache
        //2. find node in the list
        //3. remove node and put it to head
        DoublyLinkedNode tmp = cache.get(key);
        if (tmp != null) {
            remove(tmp);
            addToHead(tmp);
            return tmp.value;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        //1. check cache: if exist, update value
        //      remove -> addToHead
        //2. not exist, cache put
        // size++, check capacity
        //  if exceed, remove tail
        DoublyLinkedNode node = cache.get(key);
        if (node == null) {
            DoublyLinkedNode cur = new DoublyLinkedNode(key, value);
            cache.put(key, cur);
            addToHead(cur);
            size++;
            if (size > capacity) {
                DoublyLinkedNode tail = removeTail();
                size--;
                cache.remove(tail.key);
            }
        } else {
            node.value = value;
            cache.put(node.key, node);
            remove(node);
            addToHead(node);
        }
    }

    private void remove(DoublyLinkedNode node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }

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

    private DoublyLinkedNode removeTail() {
        DoublyLinkedNode node = tail.prev;
        remove(node);
        return node;
    }
}

Complexity

• Time: O(1) write and read
• Space: O(n)

[haixiaolu]

思路

• 用哈希表来存储键和值， 设定哈希表的长度等于capacity
  • 哈希表存储的键和输入的键一样
  • 哈希表的值可以当作一个指针指定node的值
  • 用双链表来记录最近最少和最多用的node
  • 可以设定两个dummy node， left = 最近最少用的， right = 最近最多用到的

代码 / Python

class Node:
    def __init__(self, key, val):
        self.key, self.val = key, val

        # Two pointers
        self.prev = self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.cap = capacity

        # hashmap 
        self.cache = {}   # map key to node

        # dummy nodes for least used and most used: Left = LRU, right= most recent
        self.left, self.right = Node(0, 0), Node(0, 0)

        # nodes should be connected
        self.left.next, self.right.prev = self.right, self.left

    # remove node from the list
    def remove(self, node):
        prev, next = node.prev, node.next
        prev.next, next.prev = next, prev

    # insert node at right
    def insert(self, node):
        prev, next = self.right.prev, self.right
        prev.next = next.prev = node
        node.next, node.prev = next, prev

    def get(self, key: int) -> int:
        if key in self.cache:
            # update most recent
            self.remove(self.cache[key])
            self.insert(self.cache[key])
            return self.cache[key].val
        return - 1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.remove(self.cache[key])
        self.cache[key] = Node(key, value)
        self.insert(self.cache[key])

        # check if the length exceed the capacity
        if len(self.cache) > self.cap:
            # remove from the list and delete the LRU from the hashmap
            lru = self.left.next
            self.remove(lru)
            del self.cache[lru.key]

复杂度分析

• 时间复杂度： O(1)
• 空间复杂度: O(n)

[watchpoints]

struct Node
{
    int key;
    int value;
    Node* pre ;
    Node* next;
};
class LRUCache {
private:
  map<int,Node*> hash;
  Node* head;// 头节点插入
  Node* tail;//wei节点删除
  int size ;

public:
    LRUCache(int capacity) {

      size = capacity;

      //为了减少if 判断各种异常情况. 
      head = new Node();
      tail = new Node();

      // head  tail
      head->next = tail;
      tail->pre =head;

    }

    int get(int key) {

        //01 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
        if (hash.count(key) == 0 )
        {
            return -1;
        }
        Node* ptemp = hash[key];
        //02 调整优先级, 翻转链表
        //head-1->2->tail 
        //head-2->1->tail 

         //a: move
          ptemp->pre->next = ptemp->next;
          ptemp->next->pre =ptemp->pre;//!!!

         //b: insert
          ptemp->next = head->next;
          head->next->pre = ptemp;

          head->next = ptemp;
          ptemp->pre= head;

       return ptemp->value;
    }
    //插入一个元素
    void put(int key, int value) 
    {
        //01 如果关键字已经存在，则变更其数据值
        if (hash.count(key) ==1 )
        {    
            // '[[2],[2,1],[2,2],[2],[1,1],[4,1],[2]]
            //head-->2 --tail 
            Node* ptemp = hash[key];
            ptemp->value =value;

            //a: move
            ptemp->pre->next = ptemp->next;
            ptemp->next->pre =ptemp->pre;//!!!

            //b: insert
            ptemp->next = head->next;
            head->next->pre = ptemp;

            head->next = ptemp;
            ptemp->pre= head;
            return ;
        }
        //02 不能存在，就需要插入一个元素

        //a:创建一个元素

        Node* ptemp = new Node();
        ptemp->key = key;
        ptemp->value =value;

        //b hash
        hash[key] = ptemp;

        //c:insert 新元素放前面

         // head--> tail
         //     1 
         ptemp->next = head->next; //why !!!
         head->next->pre = ptemp;

         head->next = ptemp;
         ptemp->pre = head;

         if (hash.size() > size)
         {
           // 如果超出容量，删除双向链表的尾部节点.从最后面删除
           //head-1->2->tail 

           Node* plast = tail->pre;
           hash.erase(plast->key);
           //1-->tail

            plast->pre->next = tail;
            tail->pre = plast->pre;

         }

    }
};

/**
 * 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);
 */

[suukii]

Link to LeetCode Problem

S1: 哈希表+双向链表

首先简单介绍下什么是 LRU 缓存，熟悉的可以跳过。

假设我们有一个玩具摊位，用于向顾客展示小玩具。玩具很多，摊位大小有限，不能一次性展示所有玩具，于是大部分玩具放在了仓库里。

如果有顾客来咨询某个玩具，我们就去仓库把该玩具拿出来，摆在摊位上。

因为摊位最上面的位置最显眼，所以我们总是把最新拿出来的玩具放在那。

不过由于摊位大小有限，很快就摆满了，这时如果又有顾客想看新玩具。

我们只能把摊位最下面的玩具拿回仓库(因为最下面的位置相对没那么受欢迎)，然后其他玩具往下移，腾出最上面的位置来放新玩具。

如果顾客想看的玩具就摆在摊位上，我们就可以把这个玩具直接移到摊位最上面的位置，其他的玩具就要往下挪挪位置了。还记得我们的规则吧，最近有人询问的玩具要摆在最上面显眼的位置。

这就是对 LRU 缓存的一个简单解释。回到计算机问题上面来，玩具摊位代表的就是缓存空间，我们首先需要考虑的问题是使用哪种数据结构来表示玩具摊位，以达到题目要求的时间复杂度。

数组？

如果选择数组，因为玩具在摊位上的位置会挪来挪去，这个操作的时间复杂度是$O(N)$，不符合题意，pass。

链表？

• 如果选择链表，在给定节点后新增节点，或者移除给定节点的时间复杂度是 $O(1)$。但是，链表查找节点的时间复杂度是 $O(N)$，同样不符合题意，不过还有办法补救。
• 在玩具摊位的例子中，我们是手动移动玩具，人类只需要看一眼就知道要找的玩具在哪个位置上，但计算机没那么聪明，因此还需要给它一个脑子(哈希表)来记录什么玩具在什么位置上，也就是要用一个哈希表来记录每个 key 对应的链表节点引用。这样查找链表节点的时间复杂度就降到了 $O(1)$，不过代价是空间复杂度增加到了 $O(N)$。
• 另外，由于移除链表节点后还需要把该节点前后的两个节点连起来，因此我们需要的是双向链表而不是单向链表。

// put

if key 存在:
    更新节点值
    把节点移到链表头部

else:
    if 缓存满了:
        移除最后一个节点
        删除它在哈希表中的映射

    新建一个节点
    把节点加到链表头部
    在哈希表中增加映射

// get

if key 存在:
    返回节点值
    把节点移到链表头部
else:
    返回 -1

class DLinkedListNode {
public:
    int key;
    int value;
    DLinkedListNode *prev;
    DLinkedListNode *next;
    DLinkedListNode() : key(0), value(0), prev(NULL), next(NULL) {};
    DLinkedListNode(int k, int val) : key(k), value(val), prev(NULL), next(NULL) {};
};

class LRUCache {
public:
    LRUCache(int capacity) : capacity_(capacity) {
        // 创建两个 dummy 节点来简化操作，这样就不用特殊对待头尾节点了
        dummy_head_ = new DLinkedListNode();
        dummy_tail_ = new DLinkedListNode();
        dummy_head_->next = dummy_tail_;
        dummy_tail_->prev = dummy_head_;
    }

    int get(int key) {
        if (!key_exists_(key)) {
            return -1;
        }
        // 1. 通过哈希表找到 key 对应的节点
        // 2. 将节点移到链表头部
        // 3. 返回节点值
        DLinkedListNode *node = key_node_map_[key];
        move_to_head_(node);
        return node->value;
    }

    void put(int key, int value) {
        if (key_exists_(key)) {
            // key 存在的情况
            DLinkedListNode *node = key_node_map_[key];
            node->value = value;
            move_to_head_(node);
        } else {
            // key 不存在的情况：
            // 1. 如果缓存空间满了，先删除尾节点，再新建节点
            // 2. 否则直接新建节点
            if (is_full_()) {
                DLinkedListNode *tail = dummy_tail_->prev;
                remove_node_(tail);
                key_node_map_.erase(tail->key);
            }

            DLinkedListNode *new_node = new DLinkedListNode(key, value);
            add_to_head_(new_node);
            key_node_map_[key] = new_node;
        }
    }
private:
    unordered_map<int, DLinkedListNode*> key_node_map_;
    DLinkedListNode *dummy_head_;
    DLinkedListNode *dummy_tail_;
    int capacity_;

    void move_to_head_(DLinkedListNode *node) {
        remove_node_(node);
        add_to_head_(node);
    };

    void add_to_head_(DLinkedListNode *node) {
        DLinkedListNode *prev_head = dummy_head_->next;

        dummy_head_->next = node;
        node->prev = dummy_head_;

        node->next = prev_head;
        prev_head->prev = node;
    };

    void remove_node_(DLinkedListNode *node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
        node->prev = node->next = NULL;
    };

    bool key_exists_(int key) {
        return key_node_map_.count(key) > 0;
    };

    bool is_full_() {
        return key_node_map_.size() == capacity_;
    };
};

/**
 * 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);
 */

class DoubleLinkedListNode {
    constructor(key, value) {
        this.key = key
        this.value = value
        this.prev = null
        this.next = null
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity
        this.usedSpace = 0
        // Mappings of key->node.
        this.hashmap = {}
        this.dummyHead = new DoubleLinkedListNode(null, null)
        this.dummyTail = new DoubleLinkedListNode(null, null)
        this.dummyHead.next = this.dummyTail
        this.dummyTail.prev = this.dummyHead
    }

    _isFull() {
        return this.usedSpace === this.capacity
    }

    _removeNode(node) {
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = null
        node.next = null
        return node
    }

    _addToHead(node) {
        const head = this.dummyHead.next
        node.next = head
        head.prev = node
        node.prev = this.dummyHead
        this.dummyHead.next = node
    }

    get(key) {
        if (key in this.hashmap) {
            const node = this.hashmap[key]
            this._addToHead(this._removeNode(node))
            return node.value
        }
        else {
            return -1
        }
    }

    put(key, value) {
        if (key in this.hashmap) {
            // If key exists, update the corresponding node and move it to the head.
            const node = this.hashmap[key]
            node.value = value
            this._addToHead(this._removeNode(node))
        }
        else {
        // If it's a new key.
            if (this._isFull()) {
                // If the cache is full, remove the tail node.
                const node = this.dummyTail.prev
                delete this.hashmap[node.key]
                this._removeNode(node)
                this.usedSpace--
            }
            // Create a new node and add it to the head.
            const node = new DoubleLinkedListNode(key, value)
            this.hashmap[key] = node
            this._addToHead(node)
            this.usedSpace++
        }
    }
}

/**
 * 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)
 */

• Time: $O(1)$
• Space: $O(N)$，链表空间是 $O(N)$，哈希表空间是 $O(N)$，N 为容量大小。

[wenlong201807]

代码块

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

  get(key) {
    let val = this.map.get(key);
    if (val === undefined) return -1;

    this.map.delete(key); // 因为被用过一次，原有位置删除
    this.map.set(key, val); // 放入最下面表示最新使用
    return val;
  }

  put(key, val) {
    if (this.map.has(key)) this.map.delete(key); // 如果有，删除

    this.map.set(key, val); // 放到最下面表示最新使用

    if (this.map.size > this.capacity) {
      // 这里有个知识点
      // map的entries方法，还有keys方法(可以看mdn))，会返回一个迭代器
      // 迭代器调用next也是顺序返回，所以返回第一个的值就是最老的，找到并删除即可
      this.map.delete(this.map.entries().next().value[0]);
    }
  }
}

时间复杂度和空间复杂度

• 时间复杂度 O(n)
• 空间复杂度 O(1)

[ivangin]

代码

  class LRUCache {

    private Map<Integer, Node> map;
    private int capacity;
    private int count;
    private Node head;
    private Node tail;

    class Node {
      int key;
      int value;
      Node next;
      Node pre;

      public Node(int key, int value) {
        this.key = key;
        this.value = value;
      }
    }

    public LRUCache(int capacity) {
      map = new HashMap<>();
      this.capacity = capacity;
      head = null;
      tail = null;
    }

    public int get(int key) {
      Node node = map.get(key);
      if (node == null) {
        return -1;
      }
      if (node != tail) {
        if (node == head) {
          head = head.next;
        } else {
          node.pre.next = node.next;
          node.next.pre = node.pre;
        }
        tail.next = node;
        node.pre = tail;
        node.next = null;
        tail = node;
      }
      return node.value;
    }

    public void put(int key, int value) {
      Node node = map.get(key);
      if (node != null) {
        node.value = value;
        if (node != tail) {
          if (node == head) {
            head = head.next;
          } else {
            node.pre.next = node.next;
            node.next.pre = node.pre;
          }
          tail.next = node;
          node.pre = tail;
          node.next = null;
          tail = node;
        }
      } else {
        Node newNode = new Node(key, value);
        if (capacity == 0) {
          Node temp = head;
          head = head.next;
          if (temp == tail) {
            tail = null;
          }
          map.remove(temp.key);
          capacity++;
        }
        if (head == null && tail == null) {
          head = newNode;
        } else {
          tail.next = newNode;
          newNode.pre = tail;
          newNode.next = null;
        }
        tail = newNode;
        map.put(key, newNode);
        capacity--;
      }
    }
  }

/**
 * 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);
 */

[KennethAlgol]

语言

java

public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode(){

        }
        public DLinkedNode(int _key, int _value){
            key = _key;
            value = _value;
        }
    }

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

    public LRUCache(int capacity){
        this.size = 0;
        this.capacity = capacity;
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        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;
    }
}

/**
 * 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);
 */

[Myleswork]

思路

lucifer的思路确实比较完善，算是对链表这一数据结构又复习了一遍，不戳。

代码

class DulNode{
    public:
        int key;
        int value;
        DulNode* prior;
        DulNode* next;
        DulNode() :key(0),value(0),prior(NULL),next(NULL) {};                      //默认构造函数
        DulNode(int k,int val) :key(k),value(val),prior(NULL),next(NULL) {};       //有参构造函数
    };

class LRUCache {
public:

    LRUCache(int capacity) :capamax(capacity) {
        //构造两个假节点作为头尾节点，这样就不需要将真头尾节点特殊考虑
         dummy_head = new DulNode();
         dummy_tail = new DulNode();
         dummy_head->next = dummy_tail;
         dummy_tail->prior = dummy_head;
    }

    int get(int key) {
        if(!is_exist(key)) return -1;
        DulNode* node = hash[key];  //通过hash找到该节点
        move_to_head(node);
        return node->value;
    }

    void put(int key, int value) {
        if(is_exist(key)){
            DulNode* node = hash[key];  //找节点
            node->value = value;        //改值
            move_to_head(node);         //挪节点
        }
        else{
            if(is_full()){
                hash.erase(dummy_tail->prior->key);   //在hash里删除
                del_node(dummy_tail->prior);          //删除节点
            }
            DulNode* node = new DulNode(key,value);
            add_to_head(node);                        //添加节点
            hash.emplace(key,node);
        }

    }
private:
    //设置一个哈希表来记录缓存内节点以各种操作
    unordered_map<int,DulNode*> hash;
    DulNode* dummy_head;
    DulNode* dummy_tail;
    int capamax;

    void add_to_head(DulNode* node){
        DulNode* temp = dummy_head->next;
        dummy_head->next = node;
        node->next = temp;
        node->prior = dummy_head;
        temp->prior = node;
    }

    void del_node(DulNode* node){
        node->prior->next = node->next;
        node->next->prior = node->prior;
    }

    void move_to_head(DulNode* node){
        del_node(node);
        add_to_head(node);
    }

    bool is_full(){
        if(hash.size() == capamax) return true;
        return false;
    }

    bool is_exist(int key){
        if(hash.find(key) != hash.end()) return true;
        return false;
    }
};

/**
 * 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);
 */

时间复杂度

时间复杂度：O(1) 因为有哈希和双向链表，所以时间复杂度都是O(1)

空间复杂度：O(n) 主要就是双向链表和哈希表，双向链表多两个节点

[tangjy149]

思路

LRU缓存是计算机进程管理用的机制，为了腾出内存空间，需要将最近最久未使用的进程移除。
用笔画的话，可以将整个存放空间看作类似栈的形式，每次操作之后就放在最上，每次新元素插入就移除最下面的元素，从而达到lru的策略。
但实际编码不能用这样的方式，每次操作元素可看作两步：查找和移动
查找最快应该是采用hashtable的形式，但移动不行，因此还需其他数据结构辅助
数组和链表时间复杂度都较高，移动采取双向链表的形式，可以克服问题 综上，采用哈希表+双向链表来模拟机制

代码

class LRUCache {
private:
    unordered_map<int, std::list<std::pair<int, int>>::iterator> helper;
    std::list<std::pair<int, int>> lru;
    int _capacity;
public:
    LRUCache(int capacity): _capacity(capacity) {

    }

    int get(int key) {
        auto it=helper.find(key);
        if (it!=helper.end()) {
            lru.splice(lru.begin(),lru,it->second);// 将it->second值拼接到lru
            return it->second->second;
        }
        return -1;
    }

    void put(int key, int value) {
        auto it = helper.find(key);
        if (it != helper.end()) {
            lru.splice(lru.begin(), lru, it->second);
            it->second->second = value;
            return;
        }
        lru.push_front(pair<int,int>(key,value));//因为刚刚插入，属于刚刚操作过，放在链表开始位置
        helper[key] = lru.begin();
        if (helper.size() > _capacity) {
            helper.erase(lru.back().first);
            lru.pop_back();
        }
    }

};

/**
 * 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);
 */

复杂度

时间复杂度:O(1)
空间复杂度:O(n)

[shamworld]

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.map = new Map();
    this.capacity = capacity
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if(this.map.has(key)){
        const value = this.map.get(key);
        this.map.delete(key);
        this.map.set(key,value);
        return value;
    }
    return -1
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if(this.map.has(key)){
        this.map.delete(key);
        this.map.set(key,value);
    } else {
        if(this.capacity<=this.map.size){
            this.map.delete(this.map.keys().next().value);
        }
        this.map.set(key,value);
    }
};

[ginnydyy]

Problem

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

Note

• hash map + doubly linked list
• list node should have both key and value
• note that to create methods for linked list operation, leave the map operation in the api methods

Solution

class ListNode{
    int key;
    int val;
    ListNode next;
    ListNode prev;
    public ListNode(){}
    public ListNode(int key, int val){
        this.key = key;
        this.val = val;
    }
}

class LRUCache {
    private Map<Integer, ListNode> map;
    private ListNode head;
    private ListNode tail;
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new ListNode();
        this.tail = new ListNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        int res = -1;
        if(map.containsKey(key)){
            ListNode node = map.get(key);
            res = node.val;
            moveToHead(node);
        }
        return res;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){
            ListNode node = map.get(key);
            node.val = value;
            moveToHead(node);
        }else{
            ListNode toAdd = new ListNode(key, value);
            map.put(key, toAdd);
            addToHead(toAdd);
            if(map.size() > capacity){
                ListNode node = removeTail();
                map.remove(node.key);
            }
        }
    }

    private void moveToHead(ListNode node){
        remove(node);
        addToHead(node);
    }

    private void remove(ListNode node){
        ListNode pre = node.prev;
        pre.next = node.next;
        node.next.prev = pre;
    }

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

    private ListNode removeTail(){
        ListNode toRemove = tail.prev;
        remove(toRemove);
        return toRemove;
    }
}

/**
 * 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);
 */

Complexity

• T: put and add operations are O(1).
• S: O(capacity) for the map and list.

[Flower-F]

解题思路

双链表 + 哈希表

代码

/** 
 * @param {number} key
 * @param {number} value
 */
var DoubleLinkedListNode = function(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
}

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    // 通过 dummy 节点减少边界处理
    this.dummyHead = new DoubleLinkedListNode(null, null);
    this.dummyTail = new DoubleLinkedListNode(null, null);
    this.dummyHead.next = this.dummyTail;
    this.dummyTail.prev = this.dummyHead;
};

/** 
 * @return {boolean}
 */
LRUCache.prototype._isFull = function() {
    return this.map.size === this.capacity;
}

/** 
 * @param {DoubleLinkedListNode}
 * @return {DoubleLinkedListNode}
 */
LRUCache.prototype._removeNode = function(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    // 删除节点
    node.prev = null;
    node.next = null;
    return node;
}

/** 
 * @param {DoubleLinkedListNode}
 */
LRUCache.prototype._addToHead = function(node) {
    const head = this.dummyHead.next;
    node.next = head;
    head.prev = node;
    node.prev = this.dummyHead;
    this.dummyHead.next = node;
}

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if (this.map.has(key)) {
        // get 的要放到链表头
        const node = this.map.get(key);
        this._addToHead(this._removeNode(node));
        return node.value;
    } else {
        return -1;
    }
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if (this.map.has(key)) {
        // 若已存在，修改值，然后将其放到链表头
        const node = this.map.get(key);
        node.value = value;
        this._addToHead(this._removeNode(node));
    } else {
        if (this._isFull()) {
            // 容量已满，去除尾节点，同时删除哈希表中的对应 key
            const node = this.dummyTail.prev;
            this.map.delete(node.key);
            this._removeNode(node);
        }
        // 添加头节点
        const node = new DoubleLinkedListNode(key, value);
        this.map.set(key, node);
        this._addToHead(node);
    }
};

/**
 * 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)
 */

复杂度

时间：O(1) 空间：O(n)

[samaritan1998]

LRU缓存机制

问题分析：

get方法实现O(1)时间复杂度需要哈希表

插入[关键字-值]需要链表 删除数据值要o(1)时间复杂度需要链表是双向的

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

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = dict()
        # 使用伪头部和伪尾部节点    
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # 如果 key 存在，先通过哈希表定位，再移到头部
        node = self.cache[key]
        self.moveToHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            # 如果 key 不存在，创建一个新的节点
            node = DLinkedNode(key, value)
            # 添加进哈希表
            self.cache[key] = node
            # 添加至双向链表的头部
            self.addToHead(node)
            self.size += 1
            if self.size > self.capacity:
                # 如果超出容量，删除双向链表的尾部节点
                removed = self.removeTail()
                # 删除哈希表中对应的项
                self.cache.pop(removed.key)
                self.size -= 1
        else:
            # 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)

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

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

    def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)

    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

[zol013]

class DLinkedNode():
    def __init__(self):
        self.key = 0
        self.value = 0
        self.prev = None
        self.next = None
class LRUCache:
    def _add_node(self, node):
        node.next = self.head.next
        node.prev = self.head

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

    def _remove_node(self, node):
        prev = node.prev
        new = node.next

        prev.next = new
        new.prev = prev

    def _move_to_head(self, node):
        self._remove_node(node)
        self._add_node(node)

    def _pop_tail(self):
        res = self.tail.prev
        self._remove_node(res)
        return res

    def __init__(self, capacity: int):
        self.cache = {}
        self.size = 0
        self.capacity = capacity
        self.head = DLinkedNode()
        self.tail = DLinkedNode()

        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        node = self.cache.get(key, None)
        if not node:
            return -1
        self._move_to_head(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.cache.get(key)

        if not node:
            newNode = DLinkedNode()
            newNode.key = key
            newNode.value = value
            self.cache[key] = newNode
            self._add_node(newNode)
            self.size += 1

            if self.size > self.capacity:
                res = self._pop_tail()
                del self.cache[res.key]
                self.size -= 1
        else:
            node.value = value
            self._move_to_head(node)

[taojin1992]

Idea:

dummy head and tail

Map<Integer, Node> keyNodeMap + Node head + Node tail

Node: key, val, pre, next

get: get from map, move the target to head of linkedlist
put: does map contain the key? 
    - yes: rm the old node of the same key from list; create this new node of new val; update map
    - no: check capacity, if no capacity, rm from tail and map, and inc capacity; else: add a new node to head, add to map, decrement capacity

Time:get put: O(1)
Space:O(n) if we have n entries

Code:

class LRUCache {

    class Node {
        int key;
        int val;
        Node pre;
        Node next;

        Node(int key, int val, Node pre, Node next) {
            this.key = key;
            this.val = val;
            this.pre = pre;
            this.next = next;
        }
    }

    int capacity;
    Map<Integer, Node> keyNodeMap; // key-node 
    Node head;
    Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        keyNodeMap = new HashMap<>();
        head = new Node(-1, -1, null, null);
        tail = new Node(-1, -1, null, null);
        connect(head, tail);
    }

    private void connect(Node n1, Node n2) {
        n1.next = n2;
        n2.pre = n1;
    }

    public int get(int key) {
        if (keyNodeMap.containsKey(key)) {
            Node targetNode = keyNodeMap.get(key);
            // move the node to the head
            Node targetPre = targetNode.pre;
            Node targetNext = targetNode.next;
            connect(targetPre, targetNext);

            Node afterHead = head.next;
            connect(head, targetNode);
            connect(targetNode, afterHead);

            return targetNode.val;
        } 
        return -1;
    }

    public void put(int key, int value) {
        // first check if we have this key in map
        if (keyNodeMap.containsKey(key)) {
            // no need to change capacity
            // rm current node of key from linkedlist
            Node targetNode = keyNodeMap.get(key);
            Node targetPre = targetNode.pre;
            Node targetNext = targetNode.next;
            connect(targetPre, targetNext);

            // create new node and add to head
            Node afterHead = head.next;
            Node newNode = new Node(key, value, null, null);
            connect(head, newNode);
            connect(newNode, afterHead);
            // modify map
            keyNodeMap.put(key, newNode);

        } else { // check capacity
            if (capacity == 0) {
                // 1. rm from tail and map
                Node toRm = tail.pre;
                Node newTail = toRm.pre;
                connect(newTail, tail);

                keyNodeMap.remove(toRm.key);
                // 2. inc capacity
                capacity++;
            }
            Node newNode = new Node(key, value, null, null);
            Node afterHead = head.next;
            connect(head, newNode);
            connect(newNode, afterHead);
            keyNodeMap.put(key, newNode);
            capacity--;
        }
    }
}

/**
 * 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);
 */

[stackvoid]

思路

LinkedHashMap 应用。比较简单。

代码

class LRUCache {

    LinkedHashMap<Integer, Integer> cacheHolder;
    int capacity;

    public LRUCache(int capacity) {
        cacheHolder = new LinkedHashMap(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > capacity;
            }
        };
        this.capacity = capacity;
    }

    public int get(int key) {
       return cacheHolder.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        cacheHolder.put(key, value);
    }
}

算法分析

时间复杂度：O(1)

空间复杂度：O(N)

[Serena9]

代码

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

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = dict()  
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

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

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self.addToHead(node)
            self.size += 1
            if self.size > self.capacity:
                removed = self.removeTail()
                self.cache.pop(removed.key)
                self.size -= 1
        else:
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)

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

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

    def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)

    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

[1149004121]

142. 环形链表 II

思路

要在O(1)的时间实现删除和实现查找，需要用到链表和哈希表，哈希表保存key和结点的映射。当get或者put时，要更新结点在链表中的位置，因此需要用到双向链表。

代码

    class LRUCache {
        dummy: DListNode;
        tail: DListNode;
        map: Map<number, DListNode>;
        cap: number;
        size: number;
        constructor(capacity: number) {
            this.dummy = new DListNode(-1, -1);
            this.tail = new DListNode(-1, -1);
            this.dummy.next = this.tail;
            this.tail.prev = this.dummy;
            this.cap = capacity;
            this.size = 0;
            this.map = new Map();
        }

        get(key: number): number {
            if(this.map.has(key)){
                let node = this.map.get(key);
                let value = node.val;
                this.delete(node);
                this.appendHead(node);
                return value;
            }else{
                return -1;
            }
        }

        put(key: number, value: number): void {
            let newNode = new DListNode(key, value);
            if(this.map.has(key)){
                let oldNode = this.map.get(key);
                this.delete(oldNode);
                this.appendHead(newNode);
                this.map.set(key, newNode);
            }else{
                this.appendHead(newNode);
                this.map.set(key, newNode);
                this.size++;  
                if(this.size > this.cap){
                    let key = this.deleteTail(); 
                    this.map.delete(key);          
                    this.size--;
                }
            }
        }

        delete(node: DListNode): void{
            let prev = node.prev;
            let next = node.next;
            prev.next = next;
            next.prev = prev;
        }
        appendHead(node: DListNode): void{
            let next = this.dummy.next;
            this.dummy.next = node;
            node.prev = this.dummy;
            node.next = next;
            next.prev = node;
        }

        deleteTail(): number{
            let delNode = this.tail.prev;
            this.delete(delNode);
            return delNode.key;
        }
    }

    class DListNode {
        key: number
        val: number;
        next: DListNode;
        prev: DListNode;
        constructor(key: number, val: number){
            this.key = key;
            this.val = val; 
        }
    }

复杂度分析

• 时间复杂度：O(1)。
• 空间复杂度：O(capacity)。

[Davont]

思路

自己写的超时了。。抄的漾姐的

code

class DoubleLinkedListNode {
    constructor(key, value) {
        this.key = key
        this.value = value
        this.prev = null
        this.next = null
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity
        this.usedSpace = 0
        // Mappings of key->node.
        this.hashmap = {}
        this.dummyHead = new DoubleLinkedListNode(null, null)
        this.dummyTail = new DoubleLinkedListNode(null, null)
        this.dummyHead.next = this.dummyTail
        this.dummyTail.prev = this.dummyHead
    }

    _isFull() {
        return this.usedSpace === this.capacity
    }

    _removeNode(node) {
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = null
        node.next = null
        return node
    }

    _addToHead(node) {
        const head = this.dummyHead.next
        node.next = head
        head.prev = node
        node.prev = this.dummyHead
        this.dummyHead.next = node
    }

    get(key) {
        if (key in this.hashmap) {
            const node = this.hashmap[key]
            this._addToHead(this._removeNode(node))
            return node.value
        }
        else {
            return -1
        }
    }

    put(key, value) {
        if (key in this.hashmap) {
            // If key exists, update the corresponding node and move it to the head.
            const node = this.hashmap[key]
            node.value = value
            this._addToHead(this._removeNode(node))
        }
        else {
        // If it's a new key.
            if (this._isFull()) {
                // If the cache is full, remove the tail node.
                const node = this.dummyTail.prev
                delete this.hashmap[node.key]
                this._removeNode(node)
                this.usedSpace--
            }
            // Create a new node and add it to the head.
            const node = new DoubleLinkedListNode(key, value)
            this.hashmap[key] = node
            this._addToHead(node)
            this.usedSpace++
        }
    }
}

/**
 * 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)
 */

[tongxw]

思路

LinkedHashMap

代码

class LRUCache {
    class ListNode {
        int key;
        int val;
        ListNode next;
        ListNode prev;
        ListNode(int key, int val) {
            this.next = null;
            this.prev = null;
            this.key = key;
            this.val = val;
        }
    }

    int maxSize;
    ListNode head;
    ListNode tail;
    Map<Integer, ListNode> map;
    public LRUCache(int capacity) {
        maxSize = capacity;
        head = new ListNode(0, 0);
        tail = new ListNode(0, 0);
        head.next = tail;
        tail.prev = head;
        map = new HashMap<>();
    }

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

        ListNode node = map.get(key);
        unlink(node);
        moveToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        ListNode node;
        if (map.containsKey(key)) {
            node = map.get(key);
            node.val = value;
        } else {
            node = new ListNode(key, value);
            if (map.size() == maxSize) {
                ListNode lruNode = tail.prev;
                unlink(lruNode);
                map.remove(lruNode.key);
            }
            map.put(key, node);
        }

        unlink(node);
        moveToHead(node);
    }

    private void unlink(ListNode node) {
        ListNode prev = node.prev;
        ListNode next = node.next;
        if (prev != null) {
            prev.next = next;
        }
        if (next != null) {
            next.prev = prev;
        }
    }

    private void moveToHead(ListNode node) {
        ListNode nextHead = head.next;

        head.next = node;
        node.prev = head;

        nextHead.prev = node;
        node.next = nextHead;
    }
}

[cszys888]

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

class LRUCache:
    from collections import deque
    def __init__(self, capacity: int):
        self.cache = dict()
        self.capacity = capacity
        self.size = 0
        self.head = DLinkedList()
        self.tail = DLinkedList()
        self.head.next = self.tail
        self.tail.prev = self.head

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

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self.movetohead(node)
        else:
            node = DLinkedList(key, value)
            self.addtohead(node)
            self.cache[key] = node
            self.size += 1
            if self.size > self.capacity:
                del self.cache[self.removetail().key]
                self.size -= 1

    def movetohead(self, node):
        self.removenode(node)
        self.addtohead(node)

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

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

    def removetail(self):
        node = self.tail.prev
        self.removenode(node)
        return node

[wangzehan123]

• 语言支持：Java

Java Code:

public class LRUCache {
    private class Node{
        Node prev;
        Node next;
        int key;
        int value;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }

    private int capacity;
    private HashMap<Integer, Node> hs = new HashMap<Integer, Node>();
    private Node head = new Node(-1, -1);
    private Node tail = new Node(-1, -1);

    public LRUCache(int capacity) {
        this.capacity = capacity;
        tail.prev = head;
        head.next = tail;
    }

    public int get(int key) {
        if( !hs.containsKey(key)) {         //key找不到
            return -1;
        }

        // remove current
        Node current = hs.get(key);
        current.prev.next = current.next;
        current.next.prev = current.prev;

        // move current to tail
        move_to_tail(current);          //每次get，使用次数+1，最近使用，放于尾部

        return hs.get(key).value;
    }

    public void put(int key, int value) {           //数据放入缓存
        // get 这个方法会把key挪到最末端，因此，不需要再调用 move_to_tail
        if (get(key) != -1) {
            hs.get(key).value = value;
            return;
        }

        if (hs.size() == capacity) {        //超出缓存上限
            hs.remove(head.next.key);       //删除头部数据
            head.next = head.next.next;
            head.next.prev = head;
        }

        Node insert = new Node(key, value);     //新建节点
        hs.put(key, insert);
        move_to_tail(insert);                   //放于尾部
    }

    private void move_to_tail(Node current) {    //移动数据至尾部
        current.prev = tail.prev;
        tail.prev = current;
        current.prev.next = current;
        current.next = tail;
    }
}

[CodingProgrammer]

思路

• 双向链表 + HashMap

• 建议背下来

  代码

  class LRUCache {
  
  class DoubleList {
      int key;
      int value;
      DoubleList prev;
      DoubleList next;
  
      public DoubleList() {}
  
      public DoubleList(int key, int value) {
          this.key = key;
          this.value = value;
      }
  
  }
  
  Map<Integer, DoubleList> cache;
  int capacity;
  int count;
  DoubleList dummyHead;
  DoubleList dummyTail;
  
  public LRUCache(int capacity) {
      cache = new HashMap<>();
      this.capacity = capacity;
      this.count = 0;
      this.dummyHead = new DoubleList(-1, -1);
      this.dummyTail = new DoubleList(-1, -1);
      this.dummyHead.next = this.dummyTail;
      this.dummyTail.prev = this.dummyHead;
  }
  
  private void delete(DoubleList node) {
      DoubleList prev = node.prev;
      DoubleList next = node.next;
      prev.next = next;
      next.prev = prev;
      this.count--;
  }
  
  private void add2Head(DoubleList node) {
      DoubleList headOld = this.dummyHead.next;
      this.dummyHead.next = node;
      node.prev = this.dummyHead;
      node.next = headOld;
      headOld.prev = node;
      this.count++;
  }
  
  private DoubleList deleteLast() {
      DoubleList tail = this.dummyTail.prev;
      // 倒数第二个节点为新的尾
      DoubleList tailSecond = tail.prev;
      tailSecond.next = this.dummyTail;
      this.dummyTail.prev = tailSecond;
      this.count--;
      return tail;
  }
  
  public int get(int key) {
      if (this.cache.containsKey(key)) {
          DoubleList node = cache.get(key);
          delete(node);
          add2Head(node);
          return node.value;
      } else {
          return -1;
      }
  }
  
  public void put(int key, int value) {
      DoubleList node = new DoubleList(key, value);
      // 存在
      if (cache.containsKey(key)) {
          DoubleList toDelete = cache.get(key);
          delete(toDelete);
          add2Head(node);
      } else { // 不存在
          // 超容量
          if (this.count >= this.capacity) {
              DoubleList last = deleteLast();
              cache.remove(last.key);
          }
          add2Head(node);
      }
      cache.put(key, node);
  }
  }

复杂度

• Time: O(N)
• Space : O(N)

[iambigchen]

思路

时间负责度为1，最先想到的应该是链表。双向链表来实现 remove操作。可以利用hashmap来存储每个节点，从而快速访问到每个值。每次get或put时，都将该节点删除后，添加到head。保持链表的尾部是最旧的。

关键点

建立虚拟头节点和虚拟尾节点，从而可以快速访问到链表的头、尾节点。

代码

• 语言支持：JavaScript

JavaScript Code:

/**
 * @param {number} capacity
 */
class DoubleLinkedListNode{
    constructor (key, value){
        this.key = key
        this.value = value
        this.next = null
        this.pre = null
    }
}

var LRUCache = function(capacity) {
    this.size = capacity
    this.map = {}
    this.head = new DoubleLinkedListNode(null, null)
    this.tail = new DoubleLinkedListNode(null, null)
    this.head.next =this.tail
    this.tail.pre = this.head
    this.usedSpace = 0
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if (this.map[key]) {
        let node = this.map[key]
        this.remove(node)
        this.addHead(node)
        return node.value
    }
    return -1
};
LRUCache.prototype.addHead = function(node) {
    this.map[node.key] = node
    let cur = this.head.next
    this.head.next = node
    node.pre = this.head
    cur.pre = node
    node.next = cur
};
LRUCache.prototype.remove = function(node) {
    let pre = node.pre
    let next = node.next
    pre.next = next
    next.pre = pre
    node.next = null
    node.pre = null
    delete this.map[node.key]
};
/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if (this.map[key]) {
        let node = this.map[key]
        node.value = value
        this.remove(node)
        this.addHead(node)
        this.usedSpace++
    } else {
        if (this.usedSpace === this.size) {
            this.remove(this.tail.pre)
            this.usedSpace--
        }
        let node = new DoubleLinkedListNode(key, value)
        this.addHead(node)
    }
};

/**
 * 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)
 */

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(1)$
• 空间复杂度：$O(n)$

[zhangzz2015]

思路

• 为了实现动态的删除，插入，需要链表结构，使用list。另外需要O(1)去访问数据，需要hash map。结合两个数据结构，增加一个新的数据结构，用来存储key 到list iterator之间的关系。时间复杂度为 O(1)，空间复杂度为 O(N)。

关键点

代码

• 语言支持：C++

C++ Code:

class LRUCache {
public:
    list<int> keyList; 
    unordered_map<int, int> keyToValue; 
    unordered_map<int, list<int>::iterator> keyToList; 
    int maxSize; 
    LRUCache(int capacity) {
        maxSize = capacity; 
    }

    int get(int key) {

        if(keyToValue.count(key))
        {
            auto it= keyToList[key]; 
            keyList.erase(it); 
            keyList.push_front(key); 
            keyToList[key] =  keyList.begin();
            return keyToValue[key]; 
        }
        else
        {
            return -1; 
        }

    }

    void put(int key, int value) {

        // first check if has key. yes. Then remove old and change to latest. 
        if(keyToValue.count(key))
        {
            auto it = keyToList[key]; 
            keyList.erase(it); 
            keyList.push_front(key); 
            keyToList[key] = keyList.begin(); 
            keyToValue[key] = value; 
        }
        // if size < maxSize. Then put it. 
        else if(keyList.size()<maxSize)
        {
            keyList.push_front(key); 
            keyToValue[key] = value; 
            keyToList[key] = keyList.begin(); 
        }
        // if size == maxSize. we remove the oldest one and insert it. 
        else
        {
            // remove the first key. 
            keyToValue.erase(keyList.back()); 
            keyToList.erase(keyList.back());  
            keyList.pop_back(); 

            keyList.push_front(key); 
            keyToList[key] = keyList.begin(); 
            keyToValue[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);
 */

[LannyX]

思路

双向链表+哈希表

代码

class Node{
    public int key, val;
    public Node prev, next;
    public Node(int k, int v){
        this.key = k;
        this.val = v;
    }
}    
class DoubleList{
    private Node head, tail;
    private int size;
    public DoubleList(){
        head = new Node(0,0);
        tail = new Node(0,0);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }
    public void addLast(Node x){
        x.prev = tail.prev;
        x.next = tail;
        tail.prev.next = x;
        tail.prev = x;
        size++;
    }
    public void remove(Node x){
        x.prev.next = x.next;
        x.next.prev = x.prev;
        size--;
    }
    public Node removeFirst(){
        if(head.next == tail) return null;
        Node first = head.next;
        remove(first);
        return first;
    }
    public int size(){
        return size;
    }

}
class LRUCache {
    private HashMap<Integer, Node> map;
    private DoubleList cache;
    private int cap;

    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }

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

    public void put(int key, int value) {
        if(map.containsKey(key)){
            deleteKey(key);
            addRecent(key, value);
            return;
        }
        if(cap == cache.size()){
            deleteLeastRecent();
        }
        addRecent(key,value);
    }

    private void makeRecent(int key){
        Node x = map.get(key);
        cache.remove(x);
        cache.addLast(x);
    }
    private void addRecent(int key, int val){
        Node x = new Node(key, val);
        cache.addLast(x);
        map.put(key, x);
    }
    private void deleteKey(int key){
        Node x = map.get(key);
        cache.remove(x);
        map.remove(key);
    }
    private void deleteLeastRecent(){
        Node deletedNode = cache.removeFirst();
        int deletedKey = deletedNode.key;
        map.remove(deletedKey);
    }

}

/**
 * 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);
 */

复杂度分析

• 时间复杂度：O(1)
• 空间复杂度：O(N)