一、LRU 缓存（中）

题目

请你设计并实现一个满足LRU (最近最少使用) 缓存约束的数据结构。
实现LRUCache类：

  • LRUCache(int capacity) 以正整数作为容量capacity初始化 LRU 缓存
  • int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。
  • void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该逐出最久未使用的关键字。
    函数get和put必须以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  

提示：



最多调用 次get和put

题解1

题目要求实现一个可以存储key-value形式数据的数据结构，并且可以记录最近访问的key值。首先想到的就是用字典来存储key-value结构，这样对于查找操作时间复杂度就是。

但是因为字典本身是无序的，所以我们还需要一个类似于队列的结构来记录访问的先后顺序，这个队列需要支持如下几种操作：

  • 在末尾加入一项
  • 删除头部一项
  • 将队列中某一项移到末尾

所以我们可以想到链表。链表有顺序之分，插入删除快，但是查找慢。
那是用单向链表还是双向链表呢？

对于单向链表，哈希表的结构类似于{key: ListNode(value)}，即键所对应的是一个节点地址，节点的值是value。对于单向链表，可以在常数的时间内找到对应的节点，但是如果想删除节点或者将它移到尾部，则需要从头遍历整个链表，对于这种情况需要的时间复杂度也是。
而对于双向链表，可以在常数时间内在任何位置插入或删除节点，而且可以方便地维护头尾节点的指针。

因此，这道题就用一种新的数据结构：哈希链表。
双向链表可以用来维护缓存中数据的访问顺序，链表头部是最近访问过的数据，链表尾部是最久没有访问过的数据。同时哈希表用来快速查找键对应的链表节点，以及在链表中删除或移动节点。

双向链表可以直接用list<pair<int, int>>表示，它是C++标准库中的一个容器，可以在任何位置进行常数时间的插入和删除。
哈希表直接用unordered_map<int, list<pair<int, int>>::iterator>即可。

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
class LRUCache {
 public:
  // 构造函数，初始化缓存容量
  LRUCache(int capacity) : cap(capacity) {}

  // 获取键为key的值
  int get(int key) {
    // 如果哈希表中不存在该键，返回-1
    if (hash_map.find(key) == hash_map.end())
      return -1;
    // 否则，将该键值对移到链表头部（表示最近使用）
    auto it = hash_map[key];
    link_list.splice(link_list.begin(), link_list, it);
    // 返回值
    return it->second;
  }

  // 插入或更新键值对
  void put(int key, int value) {
    // 如果哈希表中已经存在该键
    if (hash_map.find(key) != hash_map.end()) {
      // 更新值
      auto it = hash_map[key];
      it->second = value;
      // 将该键值对移到链表头部（表示最近使用）
      link_list.splice(link_list.begin(), link_list, it);
      return;
    }
    // 如果缓存已满
    if (link_list.size() == cap) {
      // 删除最近最少使用的键值对（即链表尾部的键值对）
      auto last = link_list.back();
      hash_map.erase(last.first);
      link_list.pop_back();
    }
    // 在链表头部插入新的键值对
    link_list.push_front({key, value});
    // 在哈希表中添加映射关系
    hash_map[key] = link_list.begin();
  }

 private:
  int cap;                         // 缓存容量
  list<pair<int, int>> link_list;  // 双向链表，用来维护最近最少使用的顺序
  unordered_map<int, list<pair<int, int>>::iterator>
      hash_map;  // 哈希表，用来快速查找键值对
};

题解2

上面的双向链表是直接用标准库list<pair<int, int>>实现的，当然我们也可以建立Node、实现双链表。
首先定义一个Node结构，然后创建一个头节点和一个尾节点，分别指向链表的第一个和最后一个节点。你还需要定义一些函数来在链表中插入、删除和查找节点。
下面是一个简单的例子：

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
89
90
91
92
93
94
95
// 定义双向链表节点
struct Node {
  int data;    // 数据域
  Node* prev;  // 指向前一个节点的指针
  Node* next;  // 指向后一个节点的指针
  Node(int x) : data(x), prev(nullptr), next(nullptr) {}
};

class DoublyLinkedList {
 private:
  Node* head;  // 头指针，指向链表的第一个节点
  Node* tail;  // 尾指针，指向链表的最后一个节点

 public:
  DoublyLinkedList() : head(nullptr), tail(nullptr) {}

  // 在双向链表头部插入新节点
  void insertAtHead(int data) {
    Node* newNode = new Node(data);  // 创建新节点
    newNode->next = head;  // 将新节点的next指针指向原来的头节点

    if (head != nullptr) {   // 如果原来的头节点不为空
      head->prev = newNode;  // 将原来头节点的prev指针指向新节点
    }

    head = newNode;  // 更新头指针为新创建的节点

    if (tail == nullptr) {  // 如果尾指针为空，说明链表为空
      tail = newNode;       // 更新尾指针为新创建的节点
    }
  }

  // 在双向链表尾部插入新节点
  void insertAtTail(int data) {
    if (head == nullptr) {  // 如果链表为空，直接在头部插入新节点即可
      insertAtHead(data);
      return;
    }

    Node* newNode = new Node(data);  // 创建新节点
    tail->next = newNode;            // 将尾节点的next指针指向新节点
    newNode->prev = tail;  // 将新节点的prev指针指向原来的尾节点
    tail = newNode;        // 更新尾指针为新创建的节点
  }

  // 在双向链表中查找给定值为val的节点
  Node* search(int val) {
    Node* temp = head;
    while (temp != nullptr) {   // 遍历链表
      if (temp->data == val) {  // 如果找到了给定值为val的节点
        return temp;            // 返回该节点的指针
      }
      temp = temp->next;  // 继续遍历下一个节点
    }
    return nullptr;  // 没有找到给定值为val的节点，返回空指针
  }

  // 在双向链表中删除给定值为val的所有节点
  void deleteAll(int val) {
    Node* temp = head;
    while (temp != nullptr) {      // 遍历链表
      if (temp->data == val) {     // 如果找到了给定值为val的节点
        if (temp == head) {        // 如果要删除的是头节点
          head = head->next;       // 更新头指针为下一个节点
          if (head != nullptr) {   // 如果新的头节点不为空
            head->prev = nullptr;  // 将新头节点的prev指针设为nullptr
          }
        } else if (temp == tail) {  // 如果要删除的是尾节点
          tail = tail->prev;        // 更新尾指针为前一个节点
          tail->next = nullptr;     // 将新尾节点的next指针设为nullptr
        } else {                    // 如果要删除的是中间节点
          temp->prev->next =
              temp->next;  // 将前一个节点的next指针指向后一个节点
          temp->next->prev =
              temp->prev;  // 将后一个节点的prev指针指向前一个节点
        }
        Node* delNode = temp;  // 记录要删除的节点
        temp = temp->next;     // 继续遍历下一个节点
        delete delNode;        // 删除节点
      } else {
        temp = temp->next;  // 继续遍历下一个节点
      }
    }
  }

  // 打印双向链表中的所有元素
  void printList() {
    Node* temp = head;
    while (temp != nullptr) {  // 遍历链表
      std::cout << temp->data << " ";
      temp = temp->next;
    }
    std::cout << std::endl;
  }
};

完整代码如下：

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
struct Node {
  int key;
  int value;
  Node* prev;
  Node* next;
  Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};

class LRUCache {
 private:
  unordered_map<int, Node*> cache;  // 哈希表
  Node* head;                       // 头节点
  Node* tail;                       // 尾节点
  int size;                         // 当前大小
  int capacity;                     // 最大容量

 public:
  LRUCache(int capacity) {
    this->capacity = capacity;
    size = 0;
    head = new Node(0, 0);
    tail = new Node(0, 0);
    head->next = tail;
    tail->prev = head;
  }

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

    // 如果key存在，先通过哈希表定位，再移到头部
    Node* node = cache[key];
    moveToHead(node);
    return node->value;
  }

  void put(int key, int value) {
    if (cache.count(key) == 0) {
      // 如果key不存在，创建一个新的节点
      Node* node = new Node(key, value);
      // 添加进哈希表
      cache[key] = node;
      // 添加至双向链表的头部
      addToHead(node);
      ++size;

      if (size > capacity) {
        // 如果超出容量，删除双向链表的尾部节点，并删除哈希表中对应项
        Node* removed = removeTail();
        cache.erase(removed->key);
        delete removed;
        --size;
      }
    } else {
      // 如果key存在，先通过哈希表定位，再修改value，并移到头部
      Node* node = cache[key];
      node->value = value;
      moveToHead(node);
    }
  }

 private:
  void addToHead(Node* node) {
    node->prev = head;
    node->next = head->next;

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

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

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

  Node* removeTail() {
    Node* node = tail->prev;
    removeNode(node);
    return node;
  }
};
License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

Share

快来参与讨论吧~

BlogCategoriesTagsArchives
ProjectIMU_PreintegrationLeGO_LOAM
SocialFriendCircleCommentsTravelling
MoreHomePageAbout
©2018 - Felicx 使用 Stellar 创建
总访问 113701 次 | 本页访问 326 次
共发表 83 篇Blog · 总计 127.5k 字