Leetcode 146. LRU caching mechanism

Question 2 is the same as question 1

D) data structure design To implement put and GET operations within O(1)O(1)O(1) O(1) time complexity, LRUCache is implemented based on a hash table (MAP) and a bidirectional linked list. The time complexity of insert, query and delete of hash table is O(1)O(1)O(1) O, and the time complexity of insert and delete of bidirectional linked list is O(1)O(1)O(1) O. Together, the time complexity of GET and PUT operations is O(1)O(1)O. See the code details. The specific answers are as follows. On this basis, the solution of the problem can be slightly modified.

Bidirectional linked lists based on customization (submitted for approval)

type LRUCache struct {
	m map[int]*Item
	list *DoublyLinkedList
}


func Constructor(capacity int) LRUCache {
	if capacity < 1 {
		panic("capacity < 1")}return LRUCache{
		m: make(map[int]*Item, capacity),
		list: NewDoublyLinkedList(capacity),
	}
}


func (this *LRUCache) Get(key int) int {
	item, ok := this.m[key]
	if! ok {return - 1
	}
	this.list.Move2Head(item) // Set to the most "hot" data
	return item.Val
}


func (this *LRUCache) Put(key int, value int)  {
	item, ok := this.m[key]
	if ok { / / has been in existence
		item.Val = value / / update the value
		this.list.Move2Head(item) // Set to "hottest" data
	} else {
                // Insert new data
		item, removed := this.list.AddToHead(key, value)
                this.m[key] = item
		ifremoved ! =nil {
                        // A list node was deleted. Data in the map needs to be deleted simultaneously
			delete(this.m, removed.Key)
		}
	}
}


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

// Two-way linked list node
type Item struct {
	Key int / / key
	Val int / / value
	Prev *Item // point to a direct precursor
	Next *Item // point to direct successor
}

// Two-way linked list
type DoublyLinkedList struct {
	head *Item / / head node
	tail *Item / / end nodes
	size int // Number of current nodes
	capacity int // Maximum number of nodes
}

func NewDoublyLinkedList(capacity int) *DoublyLinkedList {
	return &DoublyLinkedList{
		capacity: capacity,
	}
}

func (o *DoublyLinkedList) AddToHead(key int, val int) (item, removed *Item) {
	item = &Item{
		Key: key,
		Val: val,
	}
	ifo.head ! =nil {
		item.Next = o.head
		o.head.Prev = item
		o.head = item
	} else {
		o.head = item
		o.tail = item
	}
	o.size++
	if o.size > o.capacity {
		removed = o.removeTail()
	}
	return
}

func (o *DoublyLinkedList) removeTail(a) *Item {
        // here O. Read and O. Mail are definitely not nil
	tail := o.tail
	ifo.head ! = o.tail { prev := o.tail.Prev// Prev is definitely not nil
		prev.Next = nil // Set nil
		o.tail = prev
	} else {
		o.head = nil
		o.tail = nil
	}
	o.size--
	return tail
}

func (o *DoublyLinkedList) Move2Head(item *Item) {
	if item == o.head {
		return
	}

        // here item.prev is definitely not nil
	item.Prev.Next = item.Next
	ifitem ! = o.tail { item.Next.Prev = item.Prev// item.Next is definitely not nil
	} else {
		o.tail = item.Prev
	}

	item.Prev = nil // Set nil
	item.Next = o.head
	o.head.Prev = item
	o.head = item
}
Copy the code

Based on thecontainer/list(Submitted for approval)

import "container/list"

type LRUCache struct {
	m map[int]*list.Element
	list *list.List
        capacity int
}


func Constructor(capacity int) LRUCache {
	if capacity < 1 {
		panic("capacity < 1")}return LRUCache{
		m: make(map[int]*list.Element, capacity),
		list: list.New(),
                capacity: capacity,
	}
}


func (this *LRUCache) Get(key int) int {
	e, ok := this.m[key]
	if! ok {return - 1
	}
	this.list.MoveToFront(e) // Set to the most "hot" data
	return e.Value.(*Pair).Value
}


func (this *LRUCache) Put(key int, value int)  {
	e, ok := this.m[key]
	if ok { / / has been in existence
		e.Value.(*Pair).Value = value / / update the value
		this.list.MoveToFront(e) // Set to "hottest" data
	} else {
                if this.list.Len() == this.capacity {
                        e = this.list.Back()
                        delete(this.m, e.Value.(*Pair).Key)
                        this.list.Remove(e)
                }
                // Insert new data
                this.m[key] = this.list.PushFront(&Pair{
                        Key: key,
                        Value: value,
                })
	}
}

type Pair struct {
        Key int
        Value int
}

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