Go 刷 LeetCode 系列:經(jīng)典(1) LRU緩存機制

設(shè)計和實現(xiàn)一個? LRU (最近最少使用) 緩存機制。它應(yīng)該支持以下操作：獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 。

獲取數(shù)據(jù) get(key) - 如果密鑰 (key) 存在于緩存中，則獲取密鑰的值（總是正數(shù)），否則返回 -1。

寫入數(shù)據(jù) put(key, value) - 如果密鑰不存在，則寫入其數(shù)據(jù)值。當(dāng)緩存容量達到上限時，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最近最少使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

進階:

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

示例:

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，存儲和查找

看到題目要我們實現(xiàn)一個可以存儲 key-value 形式數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，并且可以記錄最近訪問的 key 值。首先想到的就是用字典來存儲 key-value 結(jié)構(gòu)，這樣對于查找操作時間復(fù)雜度就是 O(1)O(1)。

但是因為字典本身是無序的，所以我們還需要一個類似于隊列的結(jié)構(gòu)來記錄訪問的先后順序，這個隊列需要支持如下幾種操作：

在末尾加入一項

去除最前端一項

將隊列中某一項移到末尾

首先考慮列表結(jié)構(gòu)。

2，LRU的實現(xiàn)

利用雙向鏈表實現(xiàn)

雙向鏈表有一個特點就是它的鏈表是雙路的，我們定義好頭節(jié)點和尾節(jié)點，然后利用先進先出（FIFO），最近被放入的數(shù)據(jù)會最早被獲取。其中主要涉及到添加、訪問、修改、刪除操作。首先是添加，如果是新元素，直接放在鏈表頭上面，其他的元素順序往下移動；訪問的話，在頭節(jié)點的可以不用管，如果是在中間位置或者尾巴，就要將數(shù)據(jù)移動到頭節(jié)點；修改操作也一樣，修改原值之后，再將數(shù)據(jù)移動到頭部；刪除的話，直接刪除，其他元素順序移動；

type LRUCache struct {    capacity int    len int    hashMap map[int]*Node    head  *Node    tail  *Node}
type Node struct{    Prev *Node    Next *Node    Val int    Key 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.tail    lru.tail.Prev=lru.head    return lru}

func (this *LRUCache) Get(key int) int {    if v,ok:=this.hashMap[key];ok{       v.Prev.Next=v.Next       v.Next.Prev=v.Prev       n:=this.head.Next       this.head.Next=v       v.Prev=this.head       n.Prev=v       v.Next=n       return v.Val    }    return -1}

func (this *LRUCache) Put(key int, value int)  {    if v,ok:=this.hashMap[key];ok{       v.Prev.Next=v.Next       v.Next.Prev=v.Prev       n:=this.head.Next       this.head.Next=v       v.Prev=this.head       n.Prev=v       v.Next=n        v.Val=value       return      }    if this.len<this.capacity{       this.len++       node:=&Node{           Val:value,           Key:key,       }       this.hashMap[key]=node       n:=this.head.Next       this.head.Next=node       node.Prev=this.head       node.Next=n       n.Prev=node    }else{        t:=this.tail.Prev        this.tail.Prev.Prev.Next=this.tail        this.tail.Prev= this.tail.Prev.Prev        t.Val=value        delete(this.hashMap,t.Key)        t.Key=key        this.hashMap[key]=t        hn:=this.head.Next        this.head.Next=t        t.Prev=this.head        t.Next=hn        hn.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); */

推薦閱讀

• Go 刷 LeetCode 系列：滑動窗口（9） 顏色分類
  

喜歡本文的朋友，歡迎關(guān)注“Go語言中文網(wǎng)”：

Go語言中文網(wǎng)啟用微信學(xué)習(xí)交流群，歡迎加微信：274768166，投稿亦歡迎