题解 | LRU Cache

package main

import (
	"container/list"
	"fmt"
)

type Solution struct {
    cap int
    dict map[int] *list.Element
    list *list.List
}

type Pair struct {
    key, value int
}

func Construct(cap int) Solution{
    return Solution{
        cap,
        make(map[int]*list.Element),
        &list.List{},
    }
}

func (this * Solution) Get(key int) int {
    if this.dict[key] == nil {
        return -1
    }
    this.list.MoveToFront(this.dict[key])
    return this.dict[key].Value.(Pair).value
}

func (this * Solution) Set(key, value int) {
    if this.dict[key] != nil {
        this.dict[key].Value = Pair{key, value}
    } else {
        if this.cap > 0 {
            if this.list.Len() == this.cap {
                delete(this.dict, this.list.Back().Value.(Pair).key)
                this.list.Remove(this.list.Back())
            }
            this.dict[key] = this.list.PushFront(Pair{key,value})
        }
    }
}

func main() {
    var cap int
    fmt.Scan(&cap)
    LRU := Construct(cap)
    for {
        var op string
        _, err := fmt.Scan(&op)
        if err != nil {
            break
        }
        if op == "p" {
            var key,value int
            fmt.Scan(&key, &value)
            LRU.Set(key, value)
        } else if op == "g"{
            var key int
            fmt.Scan(&key)
            res := LRU.Get(key)
            fmt.Println(res)
        }
        // tmp := LRU.list.Front()
        // for tmp != nil {
        //     fmt.Println(tmp.Value.(Pair).key, tmp.Value.(Pair).value)
        //     tmp = tmp.Next()
        // }
        // fmt.Println("- - -")
    }
}