剑指Offer全部题目Go语言版题解

package main

import (
	"container/list"
	"fmt"
)

/*
 * @lc app=leetcode.cn id=146 lang=golang
 *
 * [146] LRU 缓存
 */

// @lc code=start
type LRUCache struct {
	capacity int
	cache    map[int]*list.Element
	lrulist  *list.List
}

type entry struct {
	key   int
	value int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		capacity: capacity, // 容量
		cache:    make(map[int]*list.Element),
		lrulist:  list.New(),
	}
}

func (this *LRUCache) Get(key int) int {
	if elem, ok := this.cache[key]; ok {
		this.lrulist.MoveToFront(elem)
		return elem.Value.(*entry).value
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if elem, ok := this.cache[key]; ok {
		elem.Value.(*entry).value = value
		this.lrulist.MoveToFront(elem)
		return
	}

	if this.lrulist.Len() == this.capacity {
		back := this.lrulist.Back()
		if back != nil {
			delete(this.cache, back.Value.(*entry).key)
			this.lrulist.Remove(back)
		}
	}

	newEntry := &entry{key, value}
	elem := this.lrulist.PushFront(newEntry)
	this.cache[key] = elem
}

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

func main() {
	lru := Constructor(2)
	lru.Put(1, 1)
	lru.Put(2, 2)
	fmt.Println(lru.Get(1)) // 输出 1
	lru.Put(3, 3)
	fmt.Println(lru.Get(2)) // 输出 -1
	lru.Put(4, 4)
	fmt.Println(lru.Get(1)) // 输出 -1
	fmt.Println(lru.Get(3)) // 输出 3
	fmt.Println(lru.Get(4)) // 输出 4
}