LRU缓存题目链接https://leetcode.cn/problems/lru-cache/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答无分析自己没什么思路。看了官方题解后的解答//哈希表双向链表 //时间复杂度对于get和put时间复杂度均为O(1) //空间复杂度O(capacity)哈希表和双向链表最多存储capacity3个元素 class ListNode{ int key; int value; ListNode last; ListNode next; ListNode(){}; ListNode(int key, int value, ListNode last, ListNode next){ this.key key; this.value value; this.last last; this.next next; } } int capacity; int size; MapInteger,ListNode map; ListNode dummyHead; ListNode dummyTail; public LRUCache(int capacity) { this.capacity capacity; this.size 0; map new HashMapInteger,ListNode(capacity); dummyHead new ListNode(); dummyTail new ListNode(); dummyHead.next dummyTail; dummyTail.last dummyHead; } public int get(int key) { if(!map.containsKey(key)){ return -1; } ListNode node map.get(key); //移动至头部 removeToHead(node); return node.value; } public void put(int key, int value) { if(map.containsKey(key)){ ListNode node map.get(key); node.value value; //移动至头部 removeToHead(node); } else{ ListNode node new ListNode(key,value,dummyHead,dummyHead.next); dummyHead.next node; node.next.last node; map.put(key,node); size; if(sizecapacity){ map.remove(dummyTail.last.key); removeTail(); size--; } } } //将节点移动至链表头部 public void removeToHead(ListNode node){ node.last.next node.next; node.next.last node.last; node.next dummyHead.next; node.last dummyHead; dummyHead.next node; node.next.last node; } //删除尾节点 public void removeTail(){ dummyTail.last dummyTail.last.last; dummyTail.last.next dummyTail; }分析​ 1、本题采用哈希表双向链表哈希表存储key与双向链表之间的映射关系双向链表维护了访问顺序靠近链表头部的键值对是最近使用的靠近尾部的键值对是最久未使用的双向链表在头部引入了一个虚拟头节点在尾部引入了一个虚拟尾节点可以避免边界情况的判断。​ 2、解题思路在Java中存在一种已经包装好的数据结构可以实现题目要求这种数据结构就是LinkedHashMap即哈希表双向链表。​ 3、注意第一当超出容量时我们不仅需要移除链表尾节点还需同步删除哈希表对应的键值对第二每次的get操作也要同时更新链表之间的顺序关系。总结本题主要是模拟Java中的LinkedHashMap即采用哈希表双向链表实现编码。靠近链表头部的键值对是最近使用的靠近尾部的键值对是最久未使用的哈希表维护了key与链表节点之间的映射关系可以通过哈希表快速定位对应的节点位置从而在O(1)的时间复杂度下实现LRU最近最少使用缓存。