ARTS(10)

1 Algorithm

设计一个 LRU 缓存机制，使它支持 put 和 get 操作，缓存大小是由一定限制的，如果缓存数量超出范围，则删除最近最少使用的 key ，如果 key 不存在，返回 -1 （所有的 value 值大于0），时间复杂度为$O(1)$。

为了保证时间复杂度为$O(1)$，就需要用空间换时间，为了保证更新 Key 和删除 Key 在常数时间内完成，所以采用双向链表完成，查询 Key 在常数时间内完成，则使用 字典 保存每一个 Key ，而且 Value 指向双向链表的每一个元素。依次 Put(1,1), Put(2,2), Put(3,3) 后，示意图如下:

Front 节点为最近最少使用的 key , Back 节点为最近最多使用的节点。一旦 Get 命中，则将该节点中列表中摘除出来，并且添加到最后。

type Element struct {
    key  int
    value int
    prev  *Element
    next  *Element
}

type List struct {
    head *Element
    tail *Element
}

func NewList() *List {
    l := &List{
        head:∈{},
        tail:∈{},
    }
    l.head.next = l.tail
    l.tail.prev = l.head
    return l
}

func (l *List) Remove(e *Element) {
    pre, next := e.prev, e.next
    pre.next = next
    next.prev = pre
}

func (l *List) Push(e *Element) {
    e.prev = l.tail.prev
    e.prev.next = e
    e.next = l.tail
    l.tail.prev = e
}

func (l *List) Pop() *Element {
    if l.head.next == l.tail {
        return nil
    }
    e := l.head.next
    l.Remove(e)
    return e
}

type LRUCache struct {
    l        *List
    capacity int
    table    map[int]*Element
}

func Constructor(capacity int) LRUCache {
    return LRUCache{
        l:        NewList(),
        capacity: capacity,
        table:    make(map[int]*Element),
    }
}

func (this *LRUCache) Get(key int) int {
    if val, ok := this.table[key]; ok {
        this.l.Remove(val)
        this.l.Push(val)
        return val.value
    }
    return -1
}

func (this *LRUCache) Put(key int, value int) {
    if val, ok := this.table[key]; ok {
        this.l.Remove(val)
        val.value = value
        this.l.Push(val)
    }else{
        e := ∈{key:key, value:value}
        if len(this.table) < this.capacity {
            this.l.Push(e)
            this.table[key] = e
        }else{
            n:=this.l.Pop()
            delete(this.table, n.key)
            n = nil
            this.l.Push(e)
            this.table[key] = e
        }
    }
}

2 Review

3 Tips

3.1 github 更新 fork 的仓库

在 github 上参与开源项目， fork 一份代码仓库后，如果原仓库有更新，那么如果更新自己 fork 出来的一份呢？

• 添加 remote 源: git remote add upstream https://github.com/whoever/whatever.git ;
• 拉取源： git fetch upstream ;
• 切换到 master 分支： git checkout master
• rebase 分支： git reabse upstream/master

4 Share

单元测试一定要充分，现实往往是那些疏忽的单元测试出问题。