题解 | #设计LRU缓存结构#

package main

import (
    "container/list"
)

type Solution struct {
 // write code here
    maxCacheSize int
    nBytes       int
    m            map[int]*list.Element
    root         *list.List
}

type Entry struct {
    Key int
    Val int
}

func Constructor(capacity int) Solution {
 // write code here
 return Solution {
    maxCacheSize: capacity,
    m: make(map[int]*list.Element),
    root: list.New(),
 }
}

func NewEntry(key, val int) *Entry {
    return &Entry{Key: key, Val: val}
}

func (this *Solution) get(key int) int {
 // write code here
 if ele, ok := this.m[key]; ok {
    this.root.MoveToFront(ele)
    return ele.Value.(*Entry).Val
 }
 return -1
}


func (this *Solution) set(key int, value int) {
 // write code here
 if ele, ok := this.m[key]; ok {
    this.root.MoveToFront(ele)
    ele.Value.(*Entry).Val = value
 } else {
    newEntry := NewEntry(key, value)
    ele = this.root.PushFront(newEntry)
    this.m[key] = ele
    this.nBytes++
 }
 if this.nBytes > this.maxCacheSize {
    this.RemoveOldest()
 }
}

func (this *Solution) RemoveOldest() {
    for this.nBytes > this.maxCacheSize {
        entryInterface := this.root.Remove(this.root.Back())
        delete(this.m, entryInterface.(*Entry).Key)
        this.nBytes--
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * solution := Constructor(capacity);
 * output := solution.get(key);
 * solution.set(key,value);
 */