LRU Cache

复盘

LeetCode LRU Cache

人生第三道 hard 题 , 不容易啊

第一次为了一道题重写和优化伪代码 , 感觉清晰了许多

排查问题的时候花了一点时间 , 应该要写一个打印链表的 helper 函数 , 做 tree 的题的时候也要一个打印 tree 的函数

错误先截图下来 , 明天再复盘 , 睡觉啦!!

LeetCode LRU Cache LeetCode LRU Cache LeetCode LRU Cache

图片来源:https://zhuanlan.zhihu.com/p/34133067

LeetCode LRU Cache LeetCode LRU Cache

第二版伪代码

DLinkedNode {
    val
    post 
    pre
}

LRUCache {
    map[key]node
    count
    capacity
    head
    tail
}

init {
    head.post=tail
    tail.pre=head

    count=0
    capacity=capacity
}

get(k) {
    if key in map
        node=map[key]
        if not at list head
            moveToHead(node)

    else
        return -1
}

put(k,v) {
    if in map
        node = map[k]
        node.val=v
        moveToHead(node)
    else
        if list full
            removeNode(tail.pre)
            delete(map,k)

            new=Node{v}
            addNode(new)
            map[k]=new
        else
            new=Node{v}
            newNode = addNode(new)
            map[k]=new
            count++
}


// move node right after head
moveToHead(node) {
    removeNode(node)
    addNode(node)
}

// remove from list
removeNode(node) {
    post=node.post
    pre=node.pre

    pre.post=post
    post.pre=pre
}

// add node after head
addNode(node) {
    
    head.post=node
    node.pre=head
    node.post=tail
    tail.pre=node
}

go 实现

type DLinkedNode struct {
   Key int
   Val int
   Next *DLinkedNode
   Last *DLinkedNode
}

type LRUCache struct {
   DMap map[int]*DLinkedNode
   Count int
   Capacity int
   Head *DLinkedNode //dummy head
   Tail *DLinkedNode //dummy tail
}


func Constructor(capacity int) LRUCache {
   head:=DLinkedNode{}
   tail:=DLinkedNode{}
   head.Next=&tail
   tail.Last=&head

   return LRUCache{DMap:make(map[int]*DLinkedNode),Count:0,Capacity:capacity,Head:&head,Tail:&tail}
}


func (this *LRUCache) Get(key int) int {
   if _,ok:=this.DMap[key];ok {
       node:=this.DMap[key]
       this.moveToHead(node)
       return node.Val
   } else {
       return -1
   }
}


func (this *LRUCache) Put(key int, value int)  {
   if _,ok:=this.DMap[key];ok {
       node:=this.DMap[key]
       node.Val=value
       this.moveToHead(node)
   } else {
       if this.Count>=this.Capacity {
           delete(this.DMap,this.Tail.Last.Key)
           this.removeNode(this.Tail.Last)

           new:=DLinkedNode{Val:value,Key:key}
           this.addNode(&new)
           this.DMap[key]=&new
       } else {
           new:=DLinkedNode{Val:value,Key:key}
           this.addNode(&new)
           this.DMap[key]=&new
           this.Count++
       }
   }

}

func (t *LRUCache) moveToHead(node *DLinkedNode) {
   t.removeNode(node)
   t.addNode(node)
}

func (t *LRUCache) removeNode(node *DLinkedNode) {
   next:=node.Next
   last:=node.Last

   last.Next=next
   next.Last=last
}

func (t *LRUCache) addNode(node *DLinkedNode) {
   headNext:=t.Head.Next
   t.Head.Next=node
   node.Last=t.Head
   node.Next=headNext
   headNext.Last=node
}

第一版伪代码:

type LRUCache struct {
   NodeMap map[]
   DataLinkedList DLList
}


func Constructor(capacity int) LRUCache {
    
}


func (this *LRUCache) Get(key int) int {
    if key in map 
        if not in list head
            del from list
            insert into list top
            
        return map[key].val
    else
        return -1
}


func (this *LRUCache) Put(key int, value int)  {

if not in map
    if list is not full
        insert into list top   // add node
        insert into map

    if list is full
        remove tail data from list  // remove node
        remove tail data from map
        insert into list top //add node
        insert into map

if in map
    delete node
    insert into head
}




/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

definition:
lru 关键在于引入了一个高效的缓存淘汰机制
using a hashmap to store node in double linked list
a limit variable to constraint len of list

a double linked list


two key operation :



LRU initial :

hashmap make(map[int]Node)

count=0 // len of exist val

capacity=capicity // capacity of list

head node = new Node , head.pre=null  // 

tail node = new Node , tail.post=null

head.post=tail
tail=pre=head

pesudo code for Double Linked List:

DoubleLinkedNode Design

int key
int val
pre Node
post Node

addNode(node)
    headPost = head.post

    head.post=node
    node.pre=head

    node.post=headpost
    headpost.pre=node


removeNode(node)
    pre=node.pre
    post=node.post

    pre.post=post
    post.pre=pre


moveToHead(node)
    removeNode(node)
    addNode(node)