題目

運用你所掌握的數據結構，設計和實現一個? LRU (最近最少使用) 緩存機制。它應該支持以下操作： 獲取數據 get 和 寫入數據 put 。

獲取數據 get(key) - 如果密鑰 (key) 存在于緩存中，則獲取密鑰的值（總是正數），否則返回 -1。
寫入數據 put(key, value) - 如果密鑰不存在，則寫入其數據值。當緩存容量達到上限時，它應該在寫入新數據之前刪除最近最少使用的數據值，從而為新的數據值留出空間。

進階:

你是否可以在?O(1) 時間復雜度內完成這兩種操作？

示例:

LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 該操作會使得密鑰 2 作廢
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 該操作會使得密鑰 1 作廢
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

思路：hash+雙鏈表

//get和put操作需要在0(1)復雜度完成type LRUCache struct {size int //大小capacity int //容量cache map[int]*DLinkedNode //哈希表head, tail *DLinkedNode //雙鏈表 }type DLinkedNode struct {key, value int //key和value 是put傳過來，就相當于緩存key-valueprev, next *DLinkedNode }//初始化一個節點 func initDLinkedNode(key, value int) *DLinkedNode {return &DLinkedNode{key: key,value: value,} }//初始化一個雙向鏈表 func Constructor(capacity int) LRUCache {l := LRUCache{cache: map[int]*DLinkedNode{},head: initDLinkedNode(0, 0),tail: initDLinkedNode(0, 0),capacity: capacity,}l.head.next = l.taill.tail.prev = l.headreturn l }//獲取數據 func (this *LRUCache) Get(key int) int {if _, ok := this.cache[key]; !ok {return -1}//cache是哈希表node := this.cache[key]//鏈表記錄順序 this.moveToHead(node)return node.value }//寫入數據 func (this *LRUCache) Put(key int, value int) {if _, ok := this.cache[key]; !ok {//不存在node := initDLinkedNode(key, value)this.cache[key] = nodethis.addToHead(node)this.size++if this.size > this.capacity {removed := this.removeTail()delete(this.cache, removed.key)this.size--}} else {//存在 node := this.cache[key]node.value = valuethis.moveToHead(node)} }//頭部增加節點 func (this *LRUCache) addToHead(node *DLinkedNode) {node.prev = this.headnode.next = this.head.nextthis.head.next.prev = nodethis.head.next = node }//刪除節點 func (this *LRUCache) removeNode(node *DLinkedNode) {node.prev.next = node.nextnode.next.prev = node.prev }//將該節點移到頭部 func (this *LRUCache) moveToHead(node *DLinkedNode) {this.removeNode(node)this.addToHead(node) }//移除尾部節點 func (this *LRUCache) removeTail() *DLinkedNode {node := this.tail.prevthis.removeNode(node)return node }

hash訪問key，value快，鏈表保存順序。每次新增節點，將節點放到鏈表首部，還要判斷LRU的容量確定是否刪除隊尾節點。

?

參考地址：https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-

?

總結

以上是生活随笔為你收集整理的面试高频题： LRU缓存机制实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。