leetcode-pp / 91alg-5-daily-check

91 天学算法第五期打卡

55 stars 14 forks source link

【Day 12 】2021-09-21 - 146. LRU 缓存机制 #27

Open azl397985856 opened 3 years ago

azl397985856 commented 3 years ago

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

FullStackH commented 3 years ago

Java class LRUCache { int capacity; LinkedHashMap<Integer, Integer> cache;

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

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

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

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

yanglr commented 3 years ago

思路

哈希表 + 双向链表

理解题意:

随机访问一个key的时间复杂度为O(1): 需用到哈希表, 用来创建mapping。

删除该缓存中最后一个entry的复杂度为O(1): 双向链表list/vector。

插入/移动一个entry到cache的第一个位置的时间复杂度为O(1): 双向链表list

于是我们需要使用哈希表+链表，对应 C++中的unordered_map和list。

代码

实现语言: C++

class LRUCache {
public:
    LRUCache(int capacity) {
        cap = capacity;
    }

    int get(int key) {
        const auto it = map.find(key);
        if (it == map.cend()) return -1;

        // 使用splice函数将这个entry移到缓存的最前面
        caches.splice(caches.begin(), caches, it->second);
        return it->second->second;
    }

    void put(int key, int value) {        
        const auto it = map.find(key);

        if (it != map.cend()) {   // 如果key已经存在于map中
            // 更新kv pair中的value
            it->second->second = value;
            // 使用splice函数将这个entry移到缓存的最前面
            caches.splice(caches.begin(), caches, it->second);
            return;
        }

        // 如果(key不存在，且)容量到上限时，则删除最早的entry
        if (caches.size() == cap) {
            const auto& oldestPair = caches.back();
            map.erase(oldestPair.first); // 从map中删除最早的entry的key
            caches.pop_back();
        }

        // 使用list容器的emplace_front函数将entry插入到cache的第一个位置并更新mapping.
        caches.emplace_front(key, value);
        map[key] = caches.begin();
    }

private:
    int cap;
    list<pair<int,int>> caches;
    unordered_map<int, list<pair<int,int>>::iterator> map; // list<pair<int,int>>::iterator是迭代器位置，类似于"指针"
};

代码已上传到: leetcode-ac/91algo daily - github.com

复杂度分析

时间复杂度：O(1)
空间复杂度：O(N), 其中N是链表长度

yachtcoder commented 3 years ago

Use OerderedDict to manipulate the cache. OrderedDict.move_to_end(key) moves an entry to the right end. OrderedDict.popitem(False) pops the left most entry.

class LRUCache:

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

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

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

shixinlovey1314 commented 3 years ago

Title:146. LRU Cache

Question Reference LeetCode

Solution

In order to have O(1) time complexity for get and put, we should utilize hash map to store data. To maintain a Least Recently Used cache, we can use a double linked list to sort the keys based on usage.

Algo: Define a struct ListNode, which contains key, value, pre pointer and next pointer. Define a hashmap to store ListNodes. Build a doulbe linked list with head points to the most recently used listnode and tail points to the least recently used listnode During put, check if the key has been in the map: if so, update the ListNode and move the ListNode to the head. otherwise, add a new node to the the head of the list, if currently reach the capacity, remove the tail node from the list and erase it from the map.

During get, check if the key has been in the map, return -1 if not, otherwise, return the value and move the list node to the head.

Code

class LRUCache {
public:
    typedef struct ListNode{
        int key;
        int val;
        ListNode* pre;
        ListNode* next;
        ListNode(): pre(NULL), next(NULL) {}
        ListNode(int k, int v): key(k), val(v), pre(NULL), next(NULL) {}
    } ListNode;

    void moveToHead(ListNode* node) {
        if (node->pre)
            node->pre->next = node->next;

        if (node->next)
            node->next->pre = node->pre;

        node->next = head->next;
        head->next = node;

        node->next->pre = node;
        node->pre = head;
    }

    LRUCache(int capacity) {
        cap = capacity;
        size = 0;
        head = new ListNode();
        tail = new ListNode();

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

    int get(int key) {
        if (!lookupTable.count(key))
            return -1;

        ListNode* node = lookupTable[key];
        moveToHead(node);
        return node->val;
    }

    void eraseTailNode() {
        ListNode* lastNode = tail->pre;

        tail->pre = lastNode->pre;
        tail->pre->next = tail;

        lookupTable.erase(lastNode->key);

        delete lastNode;
    }

    void put(int key, int value) {
        ListNode* node = NULL;

        if (!lookupTable.count(key)) {
            node = new ListNode(key, value);
            lookupTable[key] = node;

            if (++size > cap) {
                eraseTailNode();
                size--;
            }
        } else {
            node = lookupTable[key];
            node->val = value;
        }

        moveToHead(node);
    }

private:
    ListNode* head;
    ListNode* tail;
    int size;
    int cap;
    std::unordered_map<int, ListNode*> lookupTable;
};

Complexity

Time Complexity and Explaination

O(1)

Space Complexity and Explaination

O(n)

wangzehan123 commented 3 years ago

题目地址(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

 

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

前置知识

公司

暂无

思路

关键点

代码

语言支持：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;
    }
}

复杂度分析

令 n 为数组长度。

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

xj-yan commented 3 years ago

class LRUCache {
    class Node{
        int key, val;
        Node prev, next;
        Node(int key, int val){
            this.key = key;
            this.val = val;
        }
    }
    private Node head, tail;
    private Map<Integer, Node> nodeMap;
    private int capacity, count;

    public LRUCache(int capacity) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;

        nodeMap = new HashMap<>();
        this.capacity = capacity;
        count = 0;
    }

    private void addToHead(Node n){
        Node next = head.next;
        head.next = n;
        n.next = next;
        next.prev = n;
        n.prev = head;
        count++;
    }

    private void remove(Node n){
        n.prev.next = n.next;
        n.next.prev = n.prev;
        count--;
    }

    private void update(Node n){
        remove(n);
        addToHead(n);
    }

    public int get(int key) {
        if (!nodeMap.containsKey(key)) return -1;
        Node n = nodeMap.get(key);
        update(n);
        return n.val;
    }

    public void put(int key, int value) {
        Node n = nodeMap.get(key);
        if (n == null){
            n = new Node(key, value);
            addToHead(n);
            nodeMap.put(key, n);
            if (count > capacity){
                Node toRemove = tail.prev;
                remove(toRemove);
                nodeMap.remove(toRemove.key);
            }
        }else {
            n.val = value;
            update(n);
        }
    }
}

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

Time Complexity: O(n) Space Complexity: O(n)

leungogogo commented 3 years ago

LC146. LRU Cache

Method. Map + Linked List

Main Idea

We can use a linked list to simulate the cache queue, but if we just use a linked list, then the time complexity of get() and remove() will be O(n).

To make the get() and remove() operations more efficient, we can use a map to store (key, ListNode) pairs. Given a key, we can get its node immediately from the map instead of going through the linked list.

Code

class LRUCache {
    private class DBListNode {
        private DBListNode prev;
        private DBListNode next;
        private int key;
        private int val;

        private DBListNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private DBListNode head;
    private DBListNode tail;
    private int cap;
    private int size;
    private Map<Integer, DBListNode> map;

    public LRUCache(int capacity) {
        head = new DBListNode(-1, -1);
        tail = new DBListNode(-1, -1);
        map = new HashMap<>();
        head.next = tail;
        tail.prev = head;
        cap = capacity;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        DBListNode node = map.get(key);
        node.prev.next = node.next;
        node.next.prev = node.prev;

        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        return node.val;
    }

    public void put(int key, int value) {
        DBListNode node;
        if (map.containsKey(key)) {
            node = map.get(key);
            node.val = value;
            node.prev.next = node.next;
            node.next.prev = node.prev;
        } else {
            if (size < cap) {
                ++size;
            } else {
                DBListNode remove = tail.prev;
                remove.prev.next = tail;
                tail.prev = remove.prev;
                map.remove(remove.key);
            }
            node = new DBListNode(key, value);
        }

        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        map.put(key, node);
    }
}

Complexity Analysis

Time: O(1) for all operations.

Space: O(cap)

falconruo commented 3 years ago

思路:

LRU(least recently used) Cache:

利用双向链表来作为cache存放结点,规则如下：
- 定义两个头尾结点head, tail
- 尾部添加结点，evict头部结点,中间结点移动(move to tail)
- 最近被访问的结点(get, put)放在尾部
- 总的结点数 = capacity时, 对于新增加的结点, 首先删除head->next指向的结点, 然后将新结点添加在尾部(tail->prev->next = node)
利用hashmap的特性定位对应于链表中的位置，实现get和put在O(1)的时间复杂度，hashmap定义如下:
- key是给定的key
- value是指向双向链表的对应结点的指针

复杂度分析:

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

代码(C++):

class LRUCache {
public:
    struct DList {
        int key;
        int val;
        DList* prev;
        DList* next;
        DList (int k, int v) : key(k), val(v), prev(NULL), next(NULL) {}
    };

    LRUCache(int capacity) {
        head = new DList(-1, -1);
        tail = new DList(-2, -2);

        head->next = tail;
        tail->prev = head;

        size = capacity;
    }

    int get(int key) {
        if (dict.empty() || !dict.count(key)) return -1;

        DList* node = dict[key];

        if (dict.size() > 1) {
            delnode(node);
            add2tail(node);
        }
        return node->val;
    }

    void put(int key, int value) {
        // the least used node is in the head
        // the most used node is in the tail
        DList* node = NULL;

        if (!dict.empty() && dict.count(key)) {
            node = dict[key];
            node->val = value;

            if (dict.size() > 1) {
                delnode(node);
                add2tail(node);
            }
        } else {
            node = new DList(key, value);
            if (dict.size() >= size) {
                int k = head->next->key;
                delnode(head->next);
                dict.erase(k);
            }
            dict[key] = node;
            add2tail(node);
        }
    }
private:
    unordered_map<int, DList*> dict;
    int size;
    DList* head;
    DList* tail;

    void add2tail(DList* node) {
        tail->prev->next = node;

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

    void delnode(DList* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
};

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

ruohai0925 commented 3 years ago

题目地址()

题目描述

前置知识

公司

暂无

思路

关键点

代码

语言支持：Python3

Python3 Code:


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 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

    # removeTail的意思是先找到最后一个节点，然后remove它
    def removeTail(self):
        node = self.tail.prev
        self.removeNode(node)
        return node

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

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

复杂度分析

令 n 为数组长度。

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

BlueRui commented 3 years ago

Problem 146. LRU Cache

Algorithm

To be able to get and put data with O(1) time and maintain the most recent visited sequence, we need to use a combination of doubly-linked list and hash map.
The doubly-linked list allows us to insert or remove a node with O(1) time.
The map uses key and node as key and value, and allows us to query a node from a key in O(1) time.
Whenever a key is used, we find its node. Remove it from the list and add it back again to the head to maintain the sequence.
When a new key is added, we need to check for capacity.

Complexity

Time Complexity: O(1) for get and put.
Space Complexity: O(N) where N is capacity.

Code

Language: Java

class LRUCache {
    private class DLinkedNode {
        int key;
        int val;
        DLinkedNode next;
        DLinkedNode prev;
    }

    private int capacity;
    private final DLinkedNode head = new DLinkedNode();
    private final DLinkedNode tail = new DLinkedNode();
    private Map<Integer, DLinkedNode> nodeMap;

    private void addNode(DLinkedNode node) {
        // Add node to head
        DLinkedNode next = head.next;
        head.next = node;
        node.next = next;

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

    private void removeNode(DLinkedNode node) {
        DLinkedNode prev = node.prev;
        DLinkedNode next = node.next;
        prev.next = next;
        next.prev = prev;
    }

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

    public int get(int key) {
        if (!nodeMap.containsKey(key)) {
            return -1;
        }
        DLinkedNode node = nodeMap.get(key);
        removeNode(node);
        addNode(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (nodeMap.containsKey(key)) {
            DLinkedNode temp = nodeMap.get(key);
            temp.val = value;
            removeNode(temp);
            addNode(temp);
            return;
        }
        if (nodeMap.size() == capacity) {
            DLinkedNode oldNode = tail.prev;
            removeNode(oldNode);
            nodeMap.remove(oldNode.key);
        }
        DLinkedNode newNode = new DLinkedNode();
        newNode.key = key;
        newNode.val = value;
        addNode(newNode);
        nodeMap.put(key, newNode);
    }
}

yingliucreates commented 3 years ago

link:

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

代码 Javascript

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

  get(key) {
    let val = this.map.get(key);
    if (typeof val === "undefined") {
      return -1;
    }
    this.map.delete(key);
    this.map.set(key, val);
    return val;
  }

  put(key, value) {
    if (this.map.has(key)) {
      this.map.delete(key);
    }
    this.map.set(key, value);
    let keys = this.map.keys();
    if (this.map.size > this.capacity) {
      this.map.delete(keys.next().value);
    }
  }
}

复杂度分析

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

Menglin-l commented 3 years ago

思路：

1.看见key和value想到hashmap。

2.每一次put和get都更新一次取和存，保证least recently used在最上面，实现O(1)复杂度。这里数据结构选用linkedHashMap，底层由doubly-linked list实现可以做到。

代码部分：

class LRUCache {

    LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) { 
        if (map.containsKey(key)) {
            int tmp = map.get(key);
            map.remove(key);
            put(key, tmp);
            return tmp;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.remove(key);
        } else if (map.size() == capacity) {
            int lruKey = map.entrySet().iterator().next().getKey();
            map.remove(lruKey);
        } 

        map.put(key, value);
    }
}

复杂度：

Time: put和get均为O(1)

Space: O(N)

kidexp commented 3 years ago

thoughts

double linked list + hashmap

linked list需要存key

然后put的时候如果已经在里面就要先decouple 再加到前面

怎么加到前面需要好好写

code

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

    def decouple(self):
        self.next.prev, self.prev.next = self.prev, self.next
        self.next, self.prev = None, None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.head, self.tail = DoubleListNode(0, 0), DoubleListNode(-1, -1)
        self.head.prev, self.head.next = self.tail, self.tail
        self.tail.prev, self.tail.next = self.head, self.head
        self.hash_map = {}

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

    def get(self, key: int) -> int:
        if key not in self.hash_map:
            return -1
        node = self.hash_map[key]
        # remove node
        node.decouple()
        # add to next of head
        self.add_node_to_head(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key not in self.hash_map:
            if len(self.hash_map) == self.capacity:
                # remove last element
                remove_node = self.tail.prev
                remove_node.decouple()
                self.hash_map.pop(remove_node.key)
            node = DoubleListNode(key, value)
            self.hash_map[key] = node
        else:
            node = self.hash_map[key]
            node.val = value
            node.decouple()
        # add to next of head
        self.add_node_to_head(node)

complexity

时间复杂度O(1)

空间复杂度O(1)

a244629128 commented 3 years ago


class doubleLinkedListNode {
     constructor(key = null,val = null, prev = null, next =null){
         this.key = key;
         this.val = val;
         this.prev = prev;
         this.next = next;
    }
}
class LRUCache {
    constructor(capacity){
        this.capacity = capacity;
        this.size = 0;
        this.map = {};
        this.dummyHead = new doubleLinkedListNode();
        this.dummyTail = new doubleLinkedListNode();
        this.dummyHead.next = this.dummyTail;
        this.dummyTail.prev = this.dummyHead;
    }
    removeNode(targetNode){
        let targetPrev = targetNode.prev;
        let targetNext = targetNode.next;
        targetPrev.next = targetNext;
        targetNext.prev = targetPrev;
    }
    addToHead(newNode){
        let oldHead = this.dummyHead.next;
        newNode.next = oldHead;
        oldHead.prev = newNode;
        newNode.prev = this.dummyHead;
        this.dummyHead.next = newNode;
    }
    get(key){
        if(this.map[key] !== undefined){
            let node = this.map[key];
            this.removeNode(node);
            this.addToHead(node);
            return node.val;
        }else{
            return -1;
        }
    }
    put(key,value){
        let node;
         if(this.map[key] !== undefined){
            node = this.map[key];
             this.removeNode(node);
             node.val = value;
         }else{
             if(this.size >= this.capacity){
                node = this.dummyTail.prev;
                delete this.map[node.key];
                this.removeNode(node);
             }
            node = new doubleLinkedListNode(key, value);
            this.map[key] = node;
            this.size++;
         }
         this.addToHead(node);
    }
}
//time O(1)
//space O(N)

thinkfurther commented 3 years ago

思路

用linked list存放实际数据，用dict存放key对应的node地址

代码

class CacheNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.pre = None
        self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cacheDict = {}
        self.dummyHead = CacheNode(None, None)
        self.dummyTail = CacheNode(None, None)
        self.dummyHead.next = self.dummyTail
        self.dummyTail.pre = self.dummyHead

    def get(self, key: int) -> int:
        if(key in self.cacheDict):
            foundNode = self.cacheDict[key]
            self.addNodeToHead(self.removeNode(foundNode))    
            return foundNode.value
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cacheDict:
            foundNode = self.cacheDict[key]
            foundNode.value = value
            self.addNodeToHead(self.removeNode(foundNode))
            return

        if len(self.cacheDict) == self.capacity:
            del self.cacheDict[self.dummyTail.pre.key]
            self.removeNode(self.dummyTail.pre)

        node = CacheNode(key, value)
        self.cacheDict[key] = node;
        self.addNodeToHead(node)

    def removeNode(self, node: CacheNode) -> CacheNode:
        node.pre.next = node.next
        node.next.pre = node.pre
        node.next = None
        node.pre = None 
        return node

    def addNodeToHead(self, node: CacheNode) -> None:
        node.next = self.dummyHead.next
        node.next.pre = node

        node.pre = self.dummyHead
        node.pre.next = node

复杂度

时间复杂度：O(1)

空间复杂度：O(n)

nonevsnull commented 3 years ago

思路

拿到题的直觉解法
- 第一遍审题错误。以为value就代表了频率，因此误认为默认要删除value高的值，用的heap去做。仔细看了下解释。
- 题目的关键在于，优先删除的条件：一直没有操作的最早的那个元素；操作包括put和get，因此每个元素可以严格按时间排序。
- get操作的目的很容易达到，维护一个hashmap，按照kv pair就可以，难点在于在默认capacity已满载的情况下，如何按照优先顺序删除，且时间要求O(1)；
- hashmap可以保证查询get时间O(1)；需要一个数据结构使得优先列表的也可以在O(1)找到最靠前的元素；
- 如果仅仅用List存储，没法随机找到key。理想状态是用额外的一个可以保证顺序的map来实现，<key, ...>，且这个结构可以将队内任意位置放到队尾且O(1);
- 想到了linkedlist，但挪动的操作特别复杂；
failed to implement
看答案思路，使用Doubled Linked List，自己实现
- 同时拥有prev和next指针
- 同时维护head和tail
- 基于以上两点，随即挪动元素到末尾，只需要常数级别的操作了
- 将<key, node>放入map，这样可以访问链表的node
- 每次get，将对应node移到链表尾部
- 每次put
  - 如果存在node，则更新map并挪动node到尾部
  - 如果不存在node
    - 如果超过capacity，删除链表头部元素，并删除map内对应key. 这里容易忘记
    - 建<key, node>，put入map，将node放入链表尾部. 这里容易忘记
AC bug-free
- 容易出问题的地方很多，边界用dummy来处理，但是上述思路需要先写清楚再写代码；

代码


class LRUCache {
    int capacity;
    DLLNode dummyHead;
    DLLNode dummyTail;
    HashMap<Integer, DLLNode> map;

    private class DLLNode{
        int key;
        int value;

        DLLNode next;
        DLLNode prev;

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

    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.dummyHead = new DLLNode(-100, -100);
        this.dummyTail = new DLLNode(-100, -100);
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
        this.map = new HashMap<>();
    }

    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        } else {
            DLLNode node = map.get(key);
            node.prev.next = node.next;
            node.next.prev = node.prev;
            moveToTail(dummyTail, node);
            return node.value;
        }

    }

    public void moveToTail(DLLNode tail, DLLNode node){
        node.prev = tail.prev;
        node.next = tail;
        tail.prev = node;
        node.prev.next = node;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){
            DLLNode node = map.get(key);
            node.value = value;
            node.prev.next = node.next;
            node.next.prev = node.prev;
            moveToTail(dummyTail, node);
            map.put(key, node);
        } else {
            if(map.size() >= capacity){
                DLLNode head = dummyHead.next;
                dummyHead.next = head.next;
                head.next.prev = dummyHead;
                map.remove(head.key);

            }
            DLLNode node = new DLLNode(key, value);
            moveToTail(dummyTail, node);
            map.put(key, node);
        }
    }
}

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

复杂

get和put的时间复杂度: O(1) 整个解法的空间复杂度: O(N)，维护一个HashMap。

JiangyanLiNEU commented 3 years ago

Idea

use dictionary as cache to store valid key-value pair
use doubly linked list to store the order of most frequently used key

use dictionary to store the pointer address of key

Implement (Runtime = O(1) Space = O(n))

class Node(object):
def __init__(self, value=None, pre=None, nexT=None):
    self.value = value
    self.next = nexT
    self.pre = pre
class LRUCache(object):
def __init__(self, capacity):
    self.cap = capacity
    self.cache = defaultdict(int)
    self.head, self.tail = Node(), Node()
    self.head.next = self.tail
    self.tail.pre = self.head
    self.pointer = {}

def updateOrder(self, key):
    # print(key)
    cur = self.pointer[key]
    cur.pre.next = cur.next
    cur.next.pre = cur.pre
    cur.next = self.head.next
    self.head.next.pre = cur
    cur.pre = self.head
    self.head.next = cur

    self.pointer[key] = self.head.next

def replace(self, key,value):
    lastOne = self.tail.pre
    de = lastOne.value
    del self.pointer[de]
    # print(de)
    del self.cache[de]
    self.cache[key] = value
    lastOne.pre.next = self.tail
    self.tail.pre = lastOne.pre
    newNode = Node(key)
    self.head.next.pre = newNode
    newNode.next = self.head.next
    newNode.pre = self.head
    self.head.next = newNode
    self.pointer[key] = self.head.next
def get(self, key):
    """
    :type key: int
    :rtype: int
    """
    if key in self.cache:
        self.updateOrder(key)
        return self.cache[key]
    return -1

def put(self, key, value):
    """
    :type key: int
    :type value: int
    :rtype: None
    """
    if key in self.cache:
        self.cache[key] = value
        self.updateOrder(key)
    else:
        if self.cap > 0:
            self.cache[key] = value
            self.cap -= 1
            newNode = Node(key)
            self.head.next.pre = newNode
            newNode.next = self.head.next
            self.head.next = newNode
            newNode.pre = self.head
            self.pointer[key] = self.head.next
        else:
            self.replace(key,value)

heyqz commented 3 years ago

代码

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

class LRUCache:

    def __init__(self, capacity: int):
        self.dummyhead = DlinkedListNode(0, 0)
        self.dummytail = DlinkedListNode(0, 0)
        self.dummyhead.next = self.dummytail
        self.dummytail.prev = self.dummyhead

        self.capacity = capacity
        self.hashmap = {}

    def __remove_node(self, node: DlinkedListNode) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev
        return

    def __insert_to_front(self, node: DlinkedListNode) -> None:
        prev = self.dummyhead
        nxt = self.dummyhead.next
        prev.next = node
        node.prev = prev
        node.next = nxt
        nxt.prev = node
        return

    def __move_to_front(self, node: DlinkedListNode) -> None:
        self.__remove_node(node)
        self.__insert_to_front(node)
        return

    def get(self, key: int) -> int:
        if key not in self.hashmap:
            return -1
        res = self.hashmap[key].value
        self.__move_to_front(self.hashmap[key])
        return res

    def put(self, key: int, value: int) -> None:
        if key in self.hashmap:
            node = self.hashmap[key]
            node.value = value
            self.__move_to_front(node)
        else:
            node = DlinkedListNode(key, value)
            self.hashmap[key] = node
            self.__insert_to_front(node)
            if len(self.hashmap) > self.capacity:
                del self.hashmap[self.dummytail.prev.key]
                self.__remove_node(self.dummytail.prev)

Complexity

time: O(1) space: O(n)

zhangzz2015 commented 3 years ago

思路

分析题目，需要O(1)操作get 和 put。因为设置增删查找，同时保证O(1)，单独的链表或者数组都没办法实现，可采用结合hash table + 链表的方式，hash table方便查找操作，链表方便增加和删除操作。链表采用双向链表，链表从头到尾表示时间顺序放入的data。头部表面最早的数据，尾部表明最新的数据。同时记录链表的大小，当put操作，如果链表的大小已经达到最大，则需要从链表头部删除一个数据，再在尾部添加一个数据，如果没有达到最大，直接在尾部添加。当get操作，通过hash查找，如果没有，返回-1，如果有，则需要先把该节点移动到最尾部。hashmap 记录key --> ListNode关系，ListNode中包括前驱和后继节点。增加三个基础函数，包括删除节点，增加节点，移动节点到最后。空间复杂度为O(N)，时间复杂度为O(1)

关键点

代码

语言支持：C++

C++ Code:


class LRUCache {
struct ListNode
{
    int key;
    int value; 
    ListNode* prev;
    ListNode* next; 
    ListNode() : key(0), value(0), next(NULL), prev(NULL) {}
    ListNode(int ikey, int val) : key(ikey), value(val), next(NULL), prev(NULL) {}
};
public:
    ListNode head;
    ListNode tail; 
    int iSize;
    int cap;
    map<int, ListNode*> recordKey;
    LRUCache(int capacity) {
        iSize =0; 
        cap = capacity; 
        head.next = &tail;
        tail.prev = &head; 
    }

    int get(int key) {

        if(recordKey.find(key)==recordKey.end())
            return -1;
        else
        {
            ListNode* current = recordKey[key];
            moveNodeToEnd(current);
            return current->value; 
        }
    }

    void put(int key, int value) {
        if(recordKey.find(key) ==recordKey.end()) // can't find it. 
        {
            if(iSize==cap)
            {
                ///  
              deleteNode(head.next);
            }        
        }
        else
        {
            // delete this key node. and create a new key.             
            ListNode* current = recordKey[key]; 
            deleteNode(current);                     
        }
            createNewNode(key, value);        
    }
private: 

    void deleteNode(ListNode* current)
    {            
        ListNode* prevNode = current->prev; 
        ListNode* nextNode = current->next; 

        prevNode->next =  nextNode; 
        nextNode->prev = prevNode; 

        /// erase this current node; 
        recordKey.erase(current->key); 
        delete current;    
        iSize--;
    }

    void createNewNode(int key, int value)
    {
        ListNode* current = new ListNode(key, value); 
        ListNode* tmp = tail.prev; 
        tmp->next = current; 
        current->next = &tail;             
        tail.prev = current; 
        current->prev = tmp;   

        recordKey[key] = current; 

        iSize++;         
    }

    void moveNodeToEnd(ListNode* current)
    {
        ListNode* prevNode = current->prev; 
        ListNode* nextNode= current->next; 
        prevNode -> next = nextNode; 
        nextNode -> prev = prevNode; 

        nextNode = & tail ;
        prevNode = tail.prev; 

        prevNode->next = current; 
        current->next = nextNode; 

        nextNode->prev = current; 
        current->prev = prevNode;         
    }    
};

ivalkshfoeif commented 3 years ago

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

    private DListNode head,tail;
    private int capacity;
    private int size;
    private HashMap<Integer, DListNode> map;

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

    }

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

        remove(temp);
        insertBack(temp);

        return temp.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)){
            DListNode temp = map.get(key);
            temp.value = value;
            remove(temp);
            insertBack(temp); 
        }else{
            DListNode temp = new DListNode(key,value);
            if (size < capacity){
            insertBack(temp);
            map.put(key,temp);
            size++;
            }else{
                int keyNeedDelete = removeFront().key;
                insertBack(temp);
                map.remove(keyNeedDelete);
                map.put(key,temp);
            }
        }

    }

    public void insertBack(DListNode node){
        tail.prev.next = node;
        node.prev = tail.prev;
        node.next = tail;
        tail.prev = node;
    }

    public DListNode removeFront(){
        DListNode temp = head.next;
        head.next.next.prev = head;
        head.next = head.next.next;
        return temp;
    }

    public void remove(DListNode node){
        if (node == head || node == tail){
            return;
        }
        node.prev.next.next.prev = node.prev;
        node.prev.next = node.prev.next.next;
        node.prev = null;
        node.next = null;
    }
}

初见手撕，感谢cs61b的负重训练

pangjiadai commented 3 years ago

思路

double linked list + hashmap

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):
        self.capacity = capacity
        self.size = 0
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.hashmap = {}

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

    def put(self, key, value):
        if key not in self.hashmap:
            # 创建一个新的ListNode
            node = ListNode(key, value)
            self.hashmap[key] = node #储存的是node，不是value
            self.size += 1
            self.addToHead(node)
            if self.size > self.capacity:
                # 删除双向链表的尾部节点
                removed = self.removeTail()
                # 删除hashmap：用node.key来对应
                self.hashmap.pop(removed.key)
                self.size -= 1
        else:
            node = self.hashmap[key]
            node.val = 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
        #self.head.next = node 这个时候self.head.next已经改变了

    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

bingyingchu commented 3 years ago


from collections import OrderedDict
class LRUCache:

    def __init__(self, capacity: int):
        self.size = capacity
        self.cache = OrderedDict()

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

    def put(self, key: int, value: int) -> None:
        # update the value when the key already exits 
        if key in self.cache:
            self.cache[key] = value
            self.cache.move_to_end(key)
        else:
            if self.size == len(self.cache):
                # delete the least recently used key-value pair
                self.cache.popitem(last=False)
            self.cache[key] = value

Time: O(1)
Space: O(n)

MonkofEast commented 3 years ago

146. LRU Cache

Click Me

Algo

Memory

Code

# OK, double link
class DLNode:
    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):
        # size
        self.cap = capacity
        self.size = 0

        # hash for remembering loc
        self.cache = {}

        # head & tail
        self.head = DLNode()
        self.tail = DLNode()        
        self.head.next = self.tail
        self.tail.prev = self.head

    """ helper funcs """
    # remove a specific node
    def remove(self, node):
        # remove: need to remember the loc
        prevNode = node.prev
        nextNode = node.next
        prevNode.next = nextNode
        nextNode.prev = prevNode    
    def add(self, node):
        # add a node to the 1st loc, which is head.next
        node.next = self.head.next
        node.prev = self.head        
        node.next.prev = node
        self.head.next = node
    def moveToHead(self, node):
        # move a node to head
        self.remove(node)
        self.add(node)
    def popLast(self):
        # pop the last node in cache
        res = self.tail.prev
        self.remove(res)
        return res

    """ Functional Funcs """
    def get(self, key: int) -> int:
        # get target
        node = self.cache.get(key, None)

        # if not exist
        if not node: return -1

        # if exist, move to head
        self.moveToHead(node)
        return node.val

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

        # if already exists
        if node:
            self.cache[key].val = value
            self.moveToHead(node)
            return

        # check capacity
        if self.size + 1 > self.cap:
            # evict
            prevLastNode = self.popLast()
            del self.cache[prevLastNode.key]
        else:
            self.size += 1

        # we will add this node no matter what
        addNode = DLNode(key, value)
        self.add(addNode)
        self.cache[key] = addNode

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

Comp

T: O(1)

S: O(N)

chakochako commented 3 years ago

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

Zz10044 commented 3 years ago

LRU 缓存机制

思路

哈希表表记录前节点。
单向链表的节点，key，value两个值，就不用另一个hash表记录了
代码

public class LRUCache {
    class ListNode{
    public int key, val; //22
    public ListNode next;
        public ListNode(int key, int val){
        this.key = key;
        this.val = val;
        this.next = null;
        }
    }
    /*
    * @param capacity: An integer
    */
    private Map<Integer, ListNode> keyToPrev ;///cc
    private ListNode dummy = new ListNode(0, 0);
    private ListNode tail = dummy;

    private int capacity, size;

    public LRUCache(int capacity) {
        // do intialization if necessary
        this.capacity = capacity; 
        this.keyToPrev = new HashMap<>();
    }
    /*
     * @param key: An integer
     * @return: An integer
     */

    public void moveToTail(int key){
        ListNode prev = keyToPrev.get(key);
        ListNode cur = prev.next;
        if(cur == tail){
            return;
        }
        prev.next = prev.next.next;//必须第一步；

        tail.next = cur; //tail 一开始？链表怎么相连的？
        cur.next = null;

        if (prev.next != null) { //zheli
            keyToPrev.put(prev.next.key, prev);
        }
        keyToPrev.put(cur.key, tail);
        tail = cur;
    }

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

        moveToTail(key);

        // the key has been moved to the end
        return tail.val;
    }

    /*
     * @param key: An integer
     * @param value: An integer
     * @return: nothing
     */
    public void set(int key, int value) {
        // get method will move the key to the end of the linked list
        if (get(key) != -1) {
            ListNode prev = keyToPrev.get(key);
            prev.next.val = value;
            return;
        }

        if (size < capacity) {
            size++;
            ListNode curt = new ListNode(key, value);
            tail.next = curt;
            keyToPrev.put(key, tail);

            tail = curt;
            return;
        }

        // replace the first node with new key, value
        ListNode first = dummy.next;
        keyToPrev.remove(first.key);

        first.key = key;
        first.val = value;
        keyToPrev.put(key, dummy);

        moveToTail(key);
    }
}
```

**复杂度分析**
- 时间复杂度：O(1)
- 空间复杂度：链表占用空间 O(N)O(N)，哈希表占用空间也是 O(N)O(N)，因此总的空间复杂度为 O(N)O(N)，其中 N 为容量大小，也就是题目中的 capacity。

Daniel-Zheng commented 3 years ago

思路

DoubleLinkedList + HashMap。

代码(C++)

// Definition for double-linked list.
struct DoubleLinkedNode {
    int key, value;
    DoubleLinkedNode* pre;
    DoubleLinkedNode* next;
    DoubleLinkedNode(): key(0), value(0), pre(nullptr), next(nullptr) {}
    DoubleLinkedNode(int k, int v): key(k), value(v), pre(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, DoubleLinkedNode*> cache;
    DoubleLinkedNode* dummyHead;
    DoubleLinkedNode* dummyTail;
    int currentSize;
    int maxCapacity;

public:
    LRUCache(int capacity) {
        maxCapacity = capacity;
        currentSize = 0;
        dummyHead = new DoubleLinkedNode();
        dummyTail = new DoubleLinkedNode();
        dummyHead->next = dummyTail;
        dummyTail->pre = dummyHead;
    }

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

    void put(int key, int value) {
        if (!cache.count(key)) {
            DoubleLinkedNode* node = new DoubleLinkedNode(key, value);
            cache[key] = node;
            addToHead(node);
            currentSize += 1;
            if (currentSize > maxCapacity) {
                DoubleLinkedNode* removed = removeTail();
                cache.erase(removed->key);
                currentSize -= 1;
            }
        } else {
            DoubleLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void addToHead(DoubleLinkedNode* node) {
        node->pre = dummyHead;
        node->next = dummyHead->next;
        dummyHead->next->pre = node;
        dummyHead->next = node;
    }

    void removeNode(DoubleLinkedNode* node) {
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }

    void moveToHead(DoubleLinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }

    DoubleLinkedNode* removeTail() {
        DoubleLinkedNode* node = dummyTail->pre;
        removeNode(node);
        return node;
    }
};

复杂度分析

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

RocJeMaintiendrai commented 3 years ago

题目

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

思路

HashMap + DoublyLinkedList 创建dummy head和tail来减少NPE的问题，head.next永远指向最新的，tail.pre永远指向最应该被删除的，get操作时如果存在，就从list中删除并加在head.next; put操作时如果存在就从list中删除并加到head.next,如果不存在要看是否capacity满了，满了的话就删掉tail.pre再加新node到head.next，不满的话直接加即。

代码

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) additional HashMap

Jding0 commented 3 years ago

思路

HashMap

代码

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hashmap = {}

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

    def put(self, key: int, value: int) -> None:
        if key in self.hashmap:
            self.hashmap.pop(key)
            self.capacity += 1
        if self.capacity:
            self.hashmap[key] = value
            self.capacity -= 1
        else:
            self.hashmap.pop(list(self.hashmap.keys())[0])
            self.hashmap[key] = value

tongxw commented 3 years ago

思路

为了实现O(1)复杂度，LRUCache的实现方式是哈希表和双头链表哈希表存储的是key -> ListNode get/put的时候都需要更新链表，把最新访问的节点挪到链表头节点之后，put时如果容量已经满了，还需要考虑删除尾节点前面那个节点。所以创建两个helper functions，删除当前节点unlink()和将当前节点挪到头节点之后movetoHead()

代码

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

class LRUCache {
  constructor(capacity) {
    this.head = new ListNode(-1, -1);
    this.tail = new ListNode(-1, -1);
    this.head.next = this.tail;
    this.tail.prev = this.head;

    this.cap = capacity;
    this.data = {};
  }

  get(key) {
    if (!(key in this.data)) {
      return -1;
    }

    // move list node to head
    let node = this.data[key];
    this.unlink(node);
    this.moveToHead(node);

    return node.val;
  };

  put(key, value) {
    if (key in this.data) {
      // update
      let node = this.data[key];
      node.val = value;
      this.unlink(node);
      this.moveToHead(node);
    } else {
      let node = new ListNode(key, value);
      if (this.cap > 0) {
        this.cap--;
      } else {
        delete this.data[this.tail.prev.key];
        this.unlink(this.tail.prev);
      }

      this.data[key] = node;
      this.moveToHead(node);
    }
  }

  unlink(node) {
    let prev = node.prev;
    let next = node.next;
    prev.next = next;
    next.prev = prev;
  }

  moveToHead(node) {
    let first = this.head.next;
    this.head.next = node;
    node.prev = this.head;

    node.next = first;
    first.prev = node;
  }
};

chen445 commented 3 years ago

思路

Using hashmap and doubly linked list

代码

class LRUCache:
    def __init__(self, capacity: int):
        self.capcity=capacity
        self.cache=dict()
        self.head=DoublyLinkedList(0,0)
        self.tail=DoublyLinkedList(-1,-1)
        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.remove_from_list(node)
            self.append_to_head(node)
            return node.value
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node=self.cache[key]
            self.remove_from_list(node)
            self.append_to_head(node)
            node.value=value
        else:
            if len(self.cache) >= self.capcity:
                self.remove_from_tail()
            node=DoublyLinkedList(key,value)
            self.cache[key]=node
            self.append_to_head(node)       
    def remove_from_list(self,node):
        node.prev.next =node.next
        node.next.prev=node.prev
    def remove_from_tail(self):
        lru=self.tail.prev
        del self.cache[lru.key]
        self.remove_from_list(lru)
    def append_to_head(self,node):
        self.head.next.prev=node
        node.next=self.head.next
        self.head.next=node
        node.prev=self.head
class DoublyLinkedList():
    def __init__(self,key,value):
        self.key=key
        self.value=value
        self.prev=None
        self.next=None

复杂度

Time: O(1)

Space: O(n)

pzl233 commented 3 years ago

思路

用HashMap来判断元素是否存在和查找，用DoublyLinkedList来实现O(1)的增删

代码

import java.util.Hashtable;

public class LRUCache {

class DLinkedNode {
  int key;
  int value;
  DLinkedNode pre;
  DLinkedNode post;
}

/**
 * Always add the new node right after head;
 */
private void addNode(DLinkedNode node) {

  node.pre = head;
  node.post = head.post;

  head.post.pre = node;
  head.post = node;
}

/**
 * Remove an existing node from the linked list.
 */
private void removeNode(DLinkedNode node){
  DLinkedNode pre = node.pre;
  DLinkedNode post = node.post;

  pre.post = post;
  post.pre = pre;
}

/**
 * Move certain node in between to the head.
 */
private void moveToHead(DLinkedNode node){
  this.removeNode(node);
  this.addNode(node);
}

// pop the current tail. 
private DLinkedNode popTail(){
  DLinkedNode res = tail.pre;
  this.removeNode(res);
  return res;
}

private Hashtable<Integer, DLinkedNode> 
  cache = new Hashtable<Integer, DLinkedNode>();
private int count;
private int capacity;
private DLinkedNode head, tail;

public LRUCache(int capacity) {
  this.count = 0;
  this.capacity = capacity;

  head = new DLinkedNode();
  head.pre = null;

  tail = new DLinkedNode();
  tail.post = null;

  head.post = tail;
  tail.pre = head;
}

public int get(int key) {

  DLinkedNode node = cache.get(key);
  if(node == null){
    return -1; // should raise exception here.
  }

  // move the accessed node to the head;
  this.moveToHead(node);

  return node.value;
}

public void put(int key, int value) {
  DLinkedNode node = cache.get(key);

  if(node == null){

    DLinkedNode newNode = new DLinkedNode();
    newNode.key = key;
    newNode.value = value;

    this.cache.put(key, newNode);
    this.addNode(newNode);

    ++count;

    if(count > capacity){
      // pop the tail
      DLinkedNode tail = this.popTail();
      this.cache.remove(tail.key);
      --count;
    }
  }else{
    // update the value.
    node.value = value;
    this.moveToHead(node);
  }
}

}

复杂度分析

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

laofuWF commented 3 years ago

💻Code:

# move slow and fast pointer until they meet
# put fast back to head and move 1 step along with slow pointer 
# the meeting point is the res
# time: O(N)
# space: O(1)
class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if not head: return head
        if not head.next: return None

        slow = fast = head
        res = None

        while fast and fast.next: 
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                res = fast
                break;

        if not res: return None

        slow = head
        while slow != res:
            slow = slow.next
            res = res.next

        return res

SunStrongChina commented 3 years ago

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

LRU参考官方解法，其实LRU这个东西是字典快速访问任意一个双链表节点的结构，给一个键值，字典可以随机访问链表节点，然后返回链表节点的值，同时呢，将访问的链表节点移到末尾，对于put操作呢，则是将链表节点的值要么更新，要么就将新的节点插入到末尾，这儿要严格区分插入以及移动，移动是拆开再插入

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.hashmap={}
        self.capacity=capacity
        self.head=ListNode()
        self.tail=ListNode()
        self.head.next=self.tail
        self.tail.prev=self.head
    def move_to_tail(self,key):
        node1=self.hashmap[key]
        #先拆开，然后再移动
        node1.prev.next=node1.next
        node1.next.prev=node1.prev
        #再插入到尾节点
        self.tail.prev.next=node1
        node1.next=self.tail
        node1.prev=self.tail.prev
        self.tail.prev=node1

    def put(self,key,value):
        if key in self.hashmap:
            self.hashmap[key].value=value
            self.move_to_tail(key)
        else:
            if len(self.hashmap)==self.capacity:
                #弹出首部元素
                self.hashmap.pop(self.head.next.key)#字典也要维护
                node2=self.head.next.next 
                self.head.next=node2
                node2.prev=self.head

            #链表中加入新元素
            newNode=ListNode(key,value)
            self.hashmap[key]=newNode
            newNode.prev=self.tail.prev
            newNode.next=self.tail
            self.tail.prev.next=newNode
            self.tail.prev=newNode

    def get(self,key):
        if key in self.hashmap:
            self.move_to_tail(key)
            return self.hashmap[key].value

        return -1

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

minuet-red commented 3 years ago

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

class LRUCache { constructor(capacity) { this.head = new ListNode(-1, -1); this.tail = new ListNode(-1, -1); this.head.next = this.tail; this.tail.prev = this.head;

this.cap = capacity;
this.data = {};

}

get(key) { if (!(key in this.data)) { return -1; }

// move list node to head
let node = this.data[key];
this.unlink(node);
this.moveToHead(node);

return node.val;

};

put(key, value) { if (key in this.data) { // update let node = this.data[key]; node.val = value; this.unlink(node); this.moveToHead(node); } else { let node = new ListNode(key, value); if (this.cap > 0) { this.cap--; } else { delete this.data[this.tail.prev.key]; this.unlink(this.tail.prev); }

  this.data[key] = node;
  this.moveToHead(node);
}

}

unlink(node) { let prev = node.prev; let next = node.next; prev.next = next; next.prev = prev; }

moveToHead(node) { let first = this.head.next; this.head.next = node; node.prev = this.head;

node.next = first;
first.prev = node;

} };

zol013 commented 3 years ago

Python 3 code:

class DLinkedNode():
    def __init__(self):
        self.key = 0
        self.value = 0
        self.prev = None
        self.nexr = 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: int):
        self.capacity = capacity
        self.cache = {}
        self.size = 0
        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
        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:
                tail = self.pop_tail()
                del self.cache[tail.key]
                self.size -= 1
        else:
            node.value = value
            self.move_to_head(node)

Time Complexity: O(1) for get and put Space Complexity: O(capacity)

xieyj17 commented 3 years ago

from collections import deque
class LRUCache:

    def __init__(self, capacity: int):
        self.cache = {}
        self.capacity = capacity
        self.recent = deque()

    def get(self, key: int) -> int:
        if key in self.cache:
            self.recent.remove(key)
            self.recent.append(key)
            return self.cache[key]
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key] = value
            self.recent.remove(key)
            self.recent.append(key)
        else:
            if len(self.cache) < self.capacity:
                self.cache[key] = value
                self.recent.append(key)
            else:
                self.cache.pop(self.recent.popleft())
                self.cache[key] = value
                self.recent.append(key)

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

用一个dict 和一个deque 解决了

Space: O(N)

Time: O(N)

BpointA commented 3 years ago

思路

初始思路是靠哈希表+数组，勉强能过，但是达不到进阶要求。看了讲义之后学习双向链表+哈希表的思路。具体实现是之前看过题解，按照其中一份比较好理解的题解学习的。初始思路的代码放在附录里。

Python3代码

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

class LRUCache:
    def __init__(self, capacity: int):
        self.head=Node()
        self.tail=Node()
        self.head.next=self.tail
        self.tail.pre=self.head
        self.d={}
        self.capacity=capacity
    def add_point(self,node):
        self.tail.pre.next=node
        node.pre=self.tail.pre
        node.next=self.tail
        self.tail.pre=node
    def remove_point(self,node):
        node.pre.next=node.next
        node.next.pre=node.pre
    def move_point(self,node):
        self.remove_point(node)
        self.add_point(node)                       

    def get(self, key: int) -> int:
        if key in self.d:
            self.move_point(self.d[key])
            return self.d[key].value
        return -1
    def put(self, key: int, value: int) -> None:
        if key in self.d:
            self.d[key].value=value
            self.move_point(self.d[key])
        else:
            if len(self.d)==self.capacity:
                nd=self.head.next
                del self.d[nd.key]
                self.remove_point(nd)                                   
            n=Node(key,value)
            self.d[key]=n
            self.add_point(n)

复杂度

时间复杂度：O(1) 只需增删改固定位置的结点，哈希表的查询时间也只为O(1)

空间复杂度：O(n) n为capacity，需要一个长期长度为capacity的哈希表和链表

附录

自己没看提示和讲义时写的第一个答案，真的过的很勉强，其实具体操作上差不多，但是用的是数组。空间复杂度还是O(capacity)，因为用的是数组，要遍历删除，时间复杂度达到了O(capacity)，还是双向链表好一些。

class LRUCache:

    def __init__(self, capacity: int):
        self.d={}
        self.keys=[]
        self.limit=capacity

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

        if key in self.d:
            self.keys.remove(key)
            self.keys.append(key)
            return self.d[key]
        return -1
    def put(self, key: int, value: int) -> None:

        if len(self.keys)==self.limit and key not in self.d:
            del self.d[self.keys[0]]
            self.keys.pop(0)

        self.d[key]=value

        if key in self.keys:
            self.keys.remove(key)
            self.keys.append(key)
        else:
             self.keys.append(key)      
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

sxr000511 commented 3 years ago

题目地址(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

 

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

前置知识

哈希表 + 双链表

思路

哈希表：存放存储位置，用来快速查找

双链表：链表用来首尾移动node，快。由于移除链表节点后还需要把该节点前后的两个节点连起来，因此我们需要的是双向链表而不是单向链表。

关键点

定义node 类
利用node类定义double linked类
通过map 和 double linked 形成 LRU类

对象都是node，有pre 和 next

查找get：
1. map里找不到直接-1返回
2. 找到则put提到最前，返回val
修改增加put
1. 有的话双链表先删除node，调用remove
2. 没有的话移除双链表最后一个
3. 然后把新node添加到头部

代码

语言支持：JavaScript

JavaScript Code:


// 链表节点
class Node{
    constructor(key,val){
        this.key = key;
        this.val = val;
    }
}
// 双链表
class DoubleList{
    // 初始化头、尾节点、链表最大容量
    constructor(){
        this.head = new Node(0,0);
        this.tail = new Node(0,0);
        this.size = 0;
        //双链表 头节点的下一个是尾 尾的下一个是头
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }
    // 在链表头部添加节点
    addFirst(node){
        node.next = this.head.next;
        node.prev = this.head;
        this.head.next.prev = node;
        this.head.next = node;
        this.size++;
    }
    // 删除链表中存在的node节点
    remove(node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
        this.size--;
    }
    // 删除链表中最后一个节点，并返回该节点
    removeLast(){
        // 链表为空
        if(this.tail.prev == this.head){
            return null;
        }
        let last = this.tail.prev;
        this.remove(last);
        return last;
    }
}
/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.cap = capacity;
    this.map = new Map();
    this.cache = new DoubleList();
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    let map = this.map;
    if(!map.has(key)){
        return -1;
    }
    let val = map.get(key).val;
    // 最近访问数据置前
    this.put(key,val);
    return val;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    let cache = this.cache;
    let map = this.map;
    let node = new Node(key,value);
    if(map.has(key)){
        // 删除旧的节点，新的插到头部
        cache.remove(map.get(key));
    }else{
        if(this.cap == cache.size){
            // 删除最后一个
            let last = cache.removeLast();
            map.delete(last.key);
        }
    }
    // 新增头部
    cache.addFirst(node);
    // 更新 map 映射
    map.set(key,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)，哈希表占用空间也是O(N)，因此总的空间复杂度为O(N)，其中 N 为容量大小，也就是题目中的 capacity。

mmboxmm commented 3 years ago

思路

LinkedHashMap

代码

class LRUCache(private val capacity: Int) {
  private val map = mutableMapOf<Int, Node>()
  private val head = Node()
  private val tail = Node()

  init {
    head.next = tail
    tail.prev = head
  }

  fun get(key: Int): Int {
    val node = map[key]?.also {
      remove(it)
      append(it)
    }
    return node?.value ?: -1
  }

  fun put(key: Int, value: Int) {
    if (get(key) == -1) {
      if (map.size >= capacity) head.next?.let {
        remove(it)
        map.remove(it.key)
      }
      map[key] = Node(key, value).also {
        append(it)
      }
    } else {
      map[key]?.value = value
    }
  }

  private fun remove(node: Node) {
    val prev = node.prev
    val next = node.next
    prev?.next = next
    next?.prev = prev
  }

  private fun append(node: Node) {
    val prev = tail.prev
    prev?.next = node
    node.prev = prev
    node.next = tail
    tail.prev = node
  }

  class Node(
    val key: Int = 0,
    var value: Int = 0,
    var prev: Node? = null,
    var next: Node? = null
  )
}

复杂度

Time: O(1)
Space: O(1)

wangyifan2018 commented 3 years ago

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) removeNode(node *DLinkedNode) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

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

func (this *LRUCache) removeTail() *DLinkedNode {
    node := this.tail.prev
    this.removeNode(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);
 */

xingkong1994 commented 3 years ago

思路

使用双向链表list和map。

代码

class LRUCache {
public:
    LRUCache(int capacity) {
        cap_ = capacity;
    }

    int get(int key) {
        if (mymap_.find(key) == mymap_.end())  return -1;
        std::pair<int, int> value_pair = *mymap_[key];
        mylist_.erase(mymap_[key]);
        mylist_.push_front(value_pair);
        mymap_[key] = mylist_.begin();
        return value_pair.second;
    }

    void put(int key, int value) {
        std::pair<int, int> newnode = std::make_pair(key, value);
        if (mymap_.find(key) != mymap_.end()) {
            mylist_.erase(mymap_[key]);
        } else {
            if (mymap_.size() == cap_) {
                mymap_.erase(mylist_.back().first);
                mylist_.pop_back();
            }
        }
        mylist_.push_front(newnode);
        mymap_[key] = mylist_.begin();
    }
    int cap_;
    list<std::pair<int, int>> mylist_;
    unordered_map<int, list<std::pair<int, int>>::iterator> mymap_;
};

复杂度：

时间复杂度：空间复杂度：

comst007 commented 3 years ago

146. LRU 缓存机制

思路

通过 哈希表实现 O(1)的访问。通过双向链表记录元素的最近访问。

代码


class LRUCache {
struct LinkNode{
    int _key;
    int _val;
    LinkNode* _pre;
    LinkNode* _next;

    LinkNode(){
        _pre = NULL;
        _next = NULL;
    }
} *_head, *_tail;
unordered_map<int, LinkNode*> _map;
int _capcity, _size;
public:
    LRUCache(int capacity) {
        _capcity = capacity;
        _size = 0;
        _head = new LinkNode();
        _tail = new LinkNode();
        _head ->_next = _tail;
        _tail ->_pre = _head;
    }
    void headInsert(LinkNode* tmp){
        LinkNode *pre, *succ;
        pre = _head;
        succ = _head -> _next;

        pre -> _next = tmp;
        tmp -> _pre = pre;

        tmp -> _next = succ;
        succ -> _pre = tmp;
    }

    LinkNode* remove(LinkNode* tmp){

        LinkNode* pre = tmp -> _pre;
        LinkNode* succ = tmp ->_next;
        pre ->_next = succ;
        succ ->_pre = pre;

        tmp ->_next = NULL;
        tmp ->_pre = NULL;

        return tmp;
    }
    void delAndInsert(LinkNode* tmp){
        if(_head -> _next == tmp){
            return;
        }
        tmp = remove(tmp);
        headInsert(tmp);
    }

    int get(int key) {
        if(_map.count(key) == 0){
            return -1;
        }

        LinkNode* tmp = _map[key];
        int ans = tmp -> _val;
        delAndInsert(tmp);

        return ans;

    }

    void put(int key, int value) {
        LinkNode *pre, *succ, *tmp, *pnew;
        if(_map.count(key) == 0){
            if(_size < _capcity){
                pnew = new LinkNode();
                _map[key] = pnew;
                ++ _size;

                pnew -> _key = key;
                pnew ->_val = value;

                headInsert(pnew);
                return;
            }
            int del_key = _tail ->_pre -> _key;
            pnew = _tail ->_pre;
            _map.erase(del_key);

            delAndInsert(pnew);
            pnew -> _key = key;
            pnew -> _val = value;
            _map[key] = pnew;
            return ;
        }
        tmp = _map[key];
        tmp -> _val = value;

        delAndInsert(tmp);
        return;

    }
};

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

user1689 commented 3 years ago

题目

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

思路

哈希表+双向链表

python

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

class LRUCache:

    # time 1
    # space n
    # 思路一
    # 哈希表+双向链表

    # map查的快但是, 无法记录最近最久使用
    # arr删除只能做到O(n)因为得移动后面部分
    # linkedlist结合map 链表插入删除+哈希表查 但是链表进行删除有些麻烦访问前个元素
    # 所以使用双向链表(可以直接访问前个元素进行删除)+map

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

    def get(self, key: int) -> int:
        # 如果key不存在哈希表中直接返回-1
        if key not in self.dic:
            return -1
        # 如果存在 返回值 + 更新最新访问对象
        # 通过哈希表定位然后移动到头部
        node = self.dic[key]
        self.moveToHead(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        # 如果不存在
        if key not in self.dic:
            node = DListNode(key, value)
            self.dic[key] = node
            self.addToHead(node)
            self.size += 1
            # 如果超出容量，删除双向链表的尾部节点
            if self.size > self.capacity:
                removed = self.removeTail()
                self.dic.pop(removed.key)
                self.size -= 1
        # 如果存在
        else:
            # 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node = self.dic[key]
            node.val = value
            self.moveToHead(node)

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

    def removeNode(self, node):
        # 以node为基准
        node.prev.next = node.next
        node.next.prev = node.prev

    def addToHead(self, node):
        # 以head为基准
        node.prev = self.head
        node.next = self.head.next
        # 此处注意连接顺序
        self.head.next.prev = node
        self.head.next = node

    def removeTail(self):
        # 获取末尾元素
        node = self.tail.prev
        # 移去末尾元素
        self.removeNode(node)
        return node

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

复杂度分析

time O(1)
space O(n)