当前位置:   article > 正文

LeetCode Hot100 LRU缓存

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

思路

        双向链表维护头尾节点,用哈希表键值对寻找节点。

代码

  1. class lrulist
  2. {
  3. public:
  4. int val;
  5. int key;
  6. lrulist* next;
  7. lrulist* last;
  8. lrulist(int value, int k) : val(value), key(k), next(nullptr), last(nullptr){}
  9. };
  10. class LRUCache {
  11. public:
  12. unordered_map<int, lrulist*> hashmap;
  13. lrulist* back;
  14. lrulist* front;
  15. int size;
  16. int cap;
  17. void push_front(int value, int key)
  18. {
  19. lrulist* newnode = new lrulist(value, key);
  20. hashmap[key] = newnode;
  21. if(front)
  22. {
  23. newnode->next = front;
  24. front->last = newnode;
  25. }
  26. else
  27. back = newnode;
  28. front = newnode;
  29. ++size;
  30. }
  31. void move(lrulist* node)
  32. {
  33. if(node == front)
  34. return;
  35. if(back == node)
  36. {
  37. back = back->last;
  38. if(back)
  39. back->next = nullptr;
  40. }
  41. else
  42. {
  43. node->last->next = node->next;
  44. node->next->last = node->last;
  45. }
  46. node->next = front;
  47. if(front)
  48. front->last = node;
  49. front = node;
  50. }
  51. void del_node(lrulist* node)
  52. {
  53. if(front == node)
  54. {
  55. front = front->next;
  56. if(front)
  57. front->last = nullptr;
  58. }
  59. else if(back == node)
  60. {
  61. back = back->last;
  62. if(back)
  63. back->next = nullptr;
  64. }
  65. hashmap.erase(node->key);
  66. --size;
  67. delete node;
  68. }
  69. LRUCache(int capacity) : size(0), cap(capacity), front(nullptr), back(nullptr){
  70. }
  71. int get(int key) {
  72. if(hashmap.find(key) != hashmap.end())
  73. {
  74. move(hashmap[key]);
  75. return hashmap[key]->val;
  76. }
  77. else
  78. return -1;
  79. }
  80. void put(int key, int value) {
  81. if(hashmap.find(key) == hashmap.end())
  82. {
  83. if(size == cap)
  84. del_node(back);
  85. push_front(value, key);
  86. }
  87. else
  88. {
  89. hashmap[key]->val = value;
  90. move(hashmap[key]);
  91. }
  92. }
  93. };

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/代码探险家/article/detail/991865
推荐阅读
相关标签
  

闽ICP备14008679号