题目力扣
请你设计并实现一个满足 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)的平均时间复杂度运行。
我们可以直接继承Java中的双向列表来实现相关功能：
1. class LRUCache extends LinkedHashMap<Integer, Integer>{ 2. private int capacity; 3. 4. public LRUCache(int capacity) { 5. super(capacity, 0.75F, true); 6. this.capacity = capacity; 7. } 8. 9. public int get(int key) { 10. return super.getOrDefault(key, -1); 11. } 12. 13. public void put(int key, int value) { 14. super.put(key, value); 15. } 16. 17. @Override 18. protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { 19. return size() > capacity; 20. } 21. } 22.
其中LRUCache(int capacity) 函数为构造函数，我们这里设置负载因子为0.75，当容量达到初始量的0.75时就进行扩容处理；设置accessOrder为true，把访问过的元素放在链表后面；重写removeEldestEntry方法，当容器中的数量大于capacity时移除最旧的元素。
但是这道题的本意应该是让我们去自己实现一个双向列表，所以我们要自己使用哈希表和双向列表实现相关功能
代码：
1. class LRUCache { 2. class Node { 3. int key; 4. int value; 5. Node prev; 6. Node next; 7. public Node() {} 8. public Node(int _key,int _value) { 9. this.key=_key; 10. this.value=_value; 11. } 12. } 13. 14. private Map<Integer,Node> cache = new HashMap<Integer,Node>(); 15. private int size; 16. private int capacity; 17. private Node head,tail; 18. 19. public LRUCache(int capacity) { 20. this.size=0; 21. this.capacity=capacity; 22. head=new Node(); 23. tail=new Node(); 24. head.next=tail; 25. tail.prev=head; 26. } 27. 28. public int get(int key) { 29. Node node = cache.get(key); 30. if(node==null){ 31. return -1; 32. } 33. movetoHead(node); 34. return node.value; 35. } 36. 37. public void put(int key, int value) { 38. Node node =cache.get(key); 39. if(node==null){ 40. Node newnode=new Node(key,value); 41. addToHead(newnode); 42. size++; 43. cache.put(key,newnode); 44. if(size>capacity){ 45. size--; 46. Node tail = removetail(); 47. cache.remove(tail.key); 48. } 49. }else{ 50. node.value=value; 51. movetoHead(node); 52. } 53. 54. } 55. 56. private void addToHead(Node node){ 57. node.prev=head; 58. node.next=head.next; 59. head.next.prev=node; 60. head.next=node; 61. } 62. 63. private void removeNode(Node node){ 64. node.prev.next=node.next; 65. node.next.prev=node.prev; 66. 67. } 68. 69. private void movetoHead(Node node){ 70. removeNode(node); 71. addToHead(node); 72. } 73. 74. private Node removetail(){ 75. Node node=tail.prev; 76. removeNode(node); 77. return node; 78. } 79. 80. 81. 82. } 83. 84. /** 85. * Your LRUCache object will be instantiated and called as such: 86. * LRUCache obj = new LRUCache(capacity); 87. * int param_1 = obj.get(key); 88. * obj.put(key,value); 89. */
