leetcode中LRU緩存機(jī)制的示例分析

發(fā)布時(shí)間：2021-12-16 09:24:42 來(lái)源：億速云閱讀：147 作者：小新欄目：大數(shù)據(jù)

這篇文章主要為大家展示了“l(fā)eetcode中LRU緩存機(jī)制的示例分析”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“l(fā)eetcode中LRU緩存機(jī)制的示例分析”這篇文章吧。

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

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

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

進(jìn)階:

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

示例:

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

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

解題思路：

1，存儲(chǔ)和查找

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

但是因?yàn)樽值浔旧硎菬o(wú)序的，所以我們還需要一個(gè)類似于隊(duì)列的結(jié)構(gòu)來(lái)記錄訪問(wèn)的先后順序，這個(gè)隊(duì)列需要支持如下幾種操作：

在末尾加入一項(xiàng)

去除最前端一項(xiàng)

將隊(duì)列中某一項(xiàng)移到末尾

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

2，LRU的實(shí)現(xiàn)

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

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

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); */

以上是“l(fā)eetcode中LRU緩存機(jī)制的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！

向AI問(wèn)一下細(xì)節(jié)

leetcode中LRU緩存機(jī)制的示例分析

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽