溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要為大家展示了“leetcode中LRU緩存機制的示例分析”，內容簡而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領大家一起研究并學習一下“leetcode中LRU緩存機制的示例分析”這篇文章吧。
設計和實現一個 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); // 返回 1cache.put(3, 3); // 該操作會使得密鑰 2 作廢cache.get(2); // 返回 -1 (未找到)cache.put(4, 4); // 該操作會使得密鑰 1 作廢cache.get(1); // 返回 -1 (未找到)cache.get(3); // 返回 3cache.get(4); // 返回 4
解題思路：
1，存儲和查找
看到題目要我們實現一個可以存儲 key-value 形式數據的數據結構，并且可以記錄最近訪問的 key 值。首先想到的就是用字典來存儲 key-value 結構，這樣對于查找操作時間復雜度就是 O(1)O(1)。
但是因為字典本身是無序的，所以我們還需要一個類似于隊列的結構來記錄訪問的先后順序，這個隊列需要支持如下幾種操作：
在末尾加入一項
去除最前端一項
將隊列中某一項移到末尾
首先考慮列表結構。
2，LRU的實現
利用雙向鏈表實現
雙向鏈表有一個特點就是它的鏈表是雙路的，我們定義好頭節點和尾節點，然后利用先進先出（FIFO），最近被放入的數據會最早被獲取。其中主要涉及到添加、訪問、修改、刪除操作。首先是添加，如果是新元素，直接放在鏈表頭上面，其他的元素順序往下移動；訪問的話，在頭節點的可以不用管，如果是在中間位置或者尾巴，就要將數據移動到頭節點；修改操作也一樣，修改原值之后，再將數據移動到頭部；刪除的話，直接刪除，其他元素順序移動；
type LRUCache struct {capacity intlen inthashMap map[int]*Nodehead *Nodetail *Node}type Node struct{Prev *NodeNext *NodeVal intKey int}func Constructor(capacity int) LRUCache {m:=make(map[int]*Node)lru:= LRUCache{capacity:capacity,hashMap:m,head:&Node{},tail:&Node{}}lru.head.Next=lru.taillru.tail.Prev=lru.headreturn lru}func (this *LRUCache) Get(key int) int {if v,ok:=this.hashMap[key];ok{v.Prev.Next=v.Nextv.Next.Prev=v.Prevn:=this.head.Nextthis.head.Next=vv.Prev=this.headn.Prev=vv.Next=nreturn v.Val}return -1}func (this *LRUCache) Put(key int, value int) {if v,ok:=this.hashMap[key];ok{v.Prev.Next=v.Nextv.Next.Prev=v.Prevn:=this.head.Nextthis.head.Next=vv.Prev=this.headn.Prev=vv.Next=nv.Val=valuereturn}if this.len<this.capacity{this.len++node:=&Node{Val:value,Key:key,}this.hashMap[key]=noden:=this.head.Nextthis.head.Next=nodenode.Prev=this.headnode.Next=nn.Prev=node}else{t:=this.tail.Prevthis.tail.Prev.Prev.Next=this.tailthis.tail.Prev= this.tail.Prev.Prevt.Val=valuedelete(this.hashMap,t.Key)t.Key=keythis.hashMap[key]=thn:=this.head.Nextthis.head.Next=tt.Prev=this.headt.Next=hnhn.Prev=t}return}/*** Your LRUCache object will be instantiated and called as such:* obj := Constructor(capacity);* param_1 := obj.Get(key);* obj.Put(key,value);*/
以上是“leetcode中LRU緩存機制的示例分析”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
