题解 | #LRU Cache#

Go版本LRU （ACM）,双向链表+哈希表

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

type MyNode struct {
	Next, Prev *MyNode
	Key, Val   int
}

type LRUCache struct {
	Capacity  int
	Hash       map[int]*MyNode
	Head, Tail *MyNode
}

func initNode(key, val int) *MyNode {
	return &MyNode{
		Key: key,
		Val: val,
	}
}

func newCache(capacity int) *LRUCache {
	this := &LRUCache{
		Capacity: capacity,
		Hash:     make(map[int]*MyNode),
		Head:     initNode(0, 0),
		Tail:     initNode(0, 0),
	}
    this.Head.Next=this.Tail
    this.Tail.Prev=this.Head
    return this
}

func (this *LRUCache) put(key, val int) {
	if exist, ok := this.Hash[key]; ok {
		exist.Val = val
	} else {
		if this.Capacity <=0 {
			this.removeHead()
		}
		node := &MyNode{
			Val: val,
			Key: key,
		}
        this.Hash[key]=node
		this.addToTail(node)
	}
}
func (this *LRUCache) get(key int) int {
	if exist, ok := this.Hash[key]; ok {
		this.moveToTail(exist)
		return exist.Val
	} else {
		return -1
	}

}

func (this *LRUCache) addToTail(node *MyNode) {
	this.Tail.Prev.Next = node
    node.Prev=this.Tail.Prev
	this.Tail.Prev = node
    node.Next=this.Tail
    this.Capacity--
}

func (this *LRUCache) moveToTail(node *MyNode) {
	node.Prev.Next = node.Next
	node.Next.Prev = node.Prev
    node.Next=this.Tail
    node.Prev=this.Tail.Prev
	this.Tail.Prev.Next = node
	this.Tail.Prev = node
}
func (this *LRUCache) removeHead() {
    delete(this.Hash, this.Head.Next.Key)
    node:=this.Head.Next
    this.Head.Next = node.Next
    node.Next.Prev=this.Head
    
	this.Capacity++
}

func main() {
	input := bufio.NewScanner(os.Stdin)
	input.Scan()
	capacity, _ := strconv.Atoi(input.Text())
	l := newCache(capacity)
	for {
		input.Scan()
		str := strings.Split(input.Text(), " ")
        if str[0]==""{break}
		switch str[0] {
		case "p":
            if capacity<=0{continue}
			key, _ := strconv.Atoi(str[1])
			val, _ := strconv.Atoi(str[2])
			l.put(key, val)
		case "g":
            if capacity<=0{fmt.Println(-1);continue}
			key, _ := strconv.Atoi(str[1])
			val := l.get(key)
			fmt.Println(val)
		}

	}
}