[关闭]
@yexiaoqi 2022-05-12T10:46:51.000000Z 字数 2631 阅读 403

146. LRU 缓存

刷题 leetcode


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

示例

输入
["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

链接https://leetcode.cn/problems/lru-cache


方法一:借用 LinkedHashMap 实现

  1. public class LRUCache extends LinkedHashMap<Integer,Integer> {
  2. private int capacity;
  3. public LRUCache(int capacity){
  4. super(capacity, 0.75F, true);//true:访问顺序 false:插入顺序
  5. this.capacity = capacity;
  6. }
  7. public int get(int key) {
  8. return super.getOrDefault(key, -1);
  9. }
  10. public void put(int key, int value) {
  11. super.put(key, value);
  12. }
  13. @Override
  14. protected boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest) {
  15. return super.size() > capacity;
  16. }
  17. }

方法二:老老实实写,使用双向链表+哈希表

  1. public class LRUCache {
  2. public class DLinkedNode {
  3. int key;
  4. int value;
  5. DLinkedNode prev;
  6. DLinkedNode next;
  7. public DLinkedNode(){}
  8. public DLinkedNode(int key, int value) {
  9. this.key = key;
  10. this.value = value;
  11. }
  12. }
  13. private Map<Integer, DLinkedNode> cache = new HashMap<>();
  14. private int size;
  15. private int capacity;
  16. private DLinkedNode head, tail;
  17. public LRUCache(int capacity) {
  18. this.size = 0;
  19. this.capacity = capacity;
  20. head = new DLinkedNode();//head和tail作为默认头尾,方便节点操作
  21. tail = new DLinkedNode();
  22. head.next = tail;
  23. tail.prev = head;
  24. }
  25. public int get(int key) {
  26. DLinkedNode node = cache.get(key);
  27. if(node == null) {
  28. return -1;
  29. }
  30. moveToHead(node);
  31. return node.value;
  32. }
  33. public void put(int key, int value) {
  34. DLinkedNode node = cache.get(key);
  35. if(node == null) {
  36. //如果key不存在,创建一个节点把key-value放进去
  37. DLinkedNode newNode = new DLinkedNode(key, value);
  38. cache.put(key, newNode);
  39. //访问完后将节点加到链表头部
  40. addToHead(newNode);
  41. size++;
  42. if(size > capacity) {
  43. DLinkedNode tail = removeTail();
  44. cache.remove(tail.key);//删除哈希表中对应的项
  45. size--;
  46. }
  47. } else {
  48. //如果key存在,使用新的值并移动到头部
  49. node.value = value;
  50. moveToHead(node);
  51. }
  52. }
  53. //将指定节点移动到头节点
  54. private void moveToHead(DLinkedNode node) {
  55. removeNode(node);
  56. addToHead(node);
  57. }
  58. //将指定节点添加到头节点
  59. private void addToHead(DLinkedNode node) {
  60. node.prev = head;
  61. node.next = head.next;
  62. head.next.prev = node;
  63. head.next = node;
  64. }
  65. //移除尾部节点
  66. private DLinkedNode removeTail() {
  67. DLinkedNode node = tail.prev;
  68. removeNode(node);
  69. return node;
  70. }
  71. //移除指定节点
  72. private void removeNode(DLinkedNode node) {
  73. node.prev.next = node.next;
  74. node.next.prev = node.prev;
  75. }
  76. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注