Sui Xin's Blog

[LeetCode] 146.LRU缓存机制（LRU Cache）

Posted on In Disqus:

题目描述

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 / 缓存容量 / );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

解题思路

通过哈希表和双向链表来实现。哈希表用于存储目前还在缓存中的数据，双向链表用于存储数据被访问的顺序。若某数据被访问，则将该数据对应的节点移动至链表头部，若超过了缓存容量，则将链表尾部的节点以及哈希表中的数据删除。

代码

OrderedDict

在 Python 语言中，有一种结合了哈希表与双向链表的数据结构 OrderedDict，只需要短短的几行代码就可以完成本题。

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class LRUCache:

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

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

    def put(self, key: int, value: int) -> None:
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value
        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)

执行用时：268 ms

内存消耗：22 MB

哈希表和双向链表自实现

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class LinkedNode():
    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.data = dict()
        self.head = LinkedNode()
        self.tail = LinkedNode()
        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.data:
            return -1
        node = self.data[key]
        self.moveToHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.data:
            node = LinkedNode(key, value)
            self.data[key] = node
            self.addToHead(node)
            self.size += 1
            if self.size > self.capacity:
                removed = self.removeEnd()
                self.data.pop(removed.key)
                self.size -= 1
        else:
            node = self.data[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 moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)

    def removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def removeEnd(self):
        removed = self.tail.prev
        self.removeNode(removed)
        return removed



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

执行用时：272 ms

内存消耗：22.5 MB

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class LinkedNode {
    friend class LRUCache;
public:
    LinkedNode() = default;
    LinkedNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) { }

private:
    int key = 0;
    int value = 0;
    LinkedNode* prev = nullptr;
    LinkedNode* next = nullptr;
};


class LRUCache {
public:
    LRUCache(int _capacity) : capacity(_capacity), size(0) {
        head = new LinkedNode();
        tail = new LinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (data.count(key) == 0) {
            return -1;
        } else {
            LinkedNode* node = data[key];
            moveToHead(node);
            return node->value;
        }
    }
    
    void put(int key, int value) {
        if (data.count(key) == 0) {
            LinkedNode* node = new LinkedNode(key, value);
            data[key] = node;
            addToHead(node);
            ++size;
            if (size > capacity) {
                LinkedNode* removed = removeEnd();
                data.erase(removed->key);
                --size;
            }
        } else {
            LinkedNode* node = data[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void addToHead(LinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

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

    void removeNode(LinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    LinkedNode* removeEnd() {
        LinkedNode* removed = tail->prev;
        removeNode(removed);
        return removed;
    }

private:
    unordered_map<int, LinkedNode*> data;
    LinkedNode* head;
    LinkedNode* tail;
    int size = 0;
    int 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);
 */

执行用时：196 ms

内存消耗：37.2 MB

参考

https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/

Related Posts