T1 LC146 LRU缓存机制

我的题解

  1. struct doubleLinkedNode {
  2.     int key, value;
  3.     doubleLinkedNode* prev;
  4.     doubleLinkedNode* next;
  5.     doubleLinkedNode() :key(0), value(0), prev(nullptr), next(nullptr) {};
  6.     doubleLinkedNode(int _key, int _value) :key(_key), value(_value), prev(nullptr), next(nullptr) {};
  7. };
  9. class LRUCache {
  10. private:
  11.     unordered_map<int, doubleLinkedNode*> cache;
  12.     doubleLinkedNode* head;
  13.     doubleLinkedNode* tail;
  14.     int size;
  15.     int capacity;
  16. public:
  17.     LRUCache(int _capacity) :capacity(_capacity), size(0) {
  18.         head = new doubleLinkedNode();
  19.         tail = new doubleLinkedNode();
  20.         head->next = tail;
  21.         tail->prev = head;
  22.     }
  24.     int get(int key) {
  25.         if (!cache.count(key)) { return -1; }
  26.         doubleLinkedNode* node = cache[key];
  27.         moveToHead(node);
  28.         return node->value;
  29.     }
  31.     void put(int key, int value) {
  32.         if (!cache.count(key)) {
  33.             doubleLinkedNode* node = new doubleLinkedNode(key, value);
  34.             cache[key] = node;
  35.             addToHead(node);
  36.             ++size;
  37.             if (size > capacity) {
  38.                 doubleLinkedNode* removed = removeTail();
  39.                 cache.erase(removed->key);
  40.                 --size;
  41.             }
  42.         }
  43.         else {
  44.             doubleLinkedNode* node = cache[key];
  45.             node->value = value;
  46.             moveToHead(node);
  47.         }
  48.     }
  49.     void addToHead(doubleLinkedNode* node) {
  50.         node->prev = head;
  51.         node->next = head->next;
  52.         head->next->prev = node;
  53.         head->next = node;
  54.     }
  55.     void removeNode(doubleLinkedNode* node) {
  56.         node->prev->next = node->next;
  57.         node->next->prev = node->prev;
  58.     }
  59.     void moveToHead(doubleLinkedNode* node) {
  60.         removeNode(node);
  61.         addToHead(node);
  62.     }
  63.     doubleLinkedNode* removeTail() {
  64.         doubleLinkedNode* node = tail->prev;
  65.         removeNode(node);
  66.         return node;
  67.     }
  68. };

今日学习总结

  • 认真上课
  • 数据挖掘起步
  • C++ OJ
  • 复习 class 基础
  • 区块链视频及笔记 - 11
  • 极客时间 - 计算机组成原理

今日英语

  • 托福单词打卡
  • 托福单词打卡*2
  • 阅读1000词书-完成

  • [ ] 单号：T 完成半套 TPO

  • [ ] 阅读至少一篇

  • 听力至少3篇
  • 口语全套
  • 写作一个

  • [ ] 双号：GRE 学习三小时

  • [ ] GRE 核心词汇助记 List*2

  • GRE 简单填空*1
  • GRE 阅读白皮书 Passage*2