Golang 288ms (beats 100%), single map O(1)


  • 2
    A
    type cacheVal struct {
    	value          int
    	younger, older int // These are the keys of the next younger, next older entries in the map, -1 if none
    }
    
    type LRUCache struct {
    	m                          map[int]*cacheVal
    	youngest, oldest, capacity int
    }
    
    func Constructor(capacity int) LRUCache {
    	return LRUCache{
    		m:        make(map[int]*cacheVal),
    		capacity: capacity,
    		youngest: -1,
    		oldest:   -1,
    	}
    }
    
    func (this *LRUCache) Get(key int) int {
    	if c, ok := this.m[key]; ok {
    		if this.youngest != key { // If this is not the youngest entry, move it to be the youngest
    			this.m[this.youngest].younger = key // Current youngest now points to key as the youngest
    			if c.older != -1 {                  // If we have an older key in the current position of the get node
    				this.m[c.older].younger = c.younger // link the next older node to the get-node's younger
    			} else if c.younger != -1 { // If the get-node is the current oldest, and we aren't adding a new value in Put
    				this.oldest = c.younger // The new oldest is the get-node's younger sibling
    			}
    			if c.younger != -1 { // If we have a younger node (always true, except on a new put)
    				this.m[c.younger].older = c.older // Set the younger's older sibling to be the get-node's older sibiling
    			}
    			c.younger = -1          // The get-node is now the youngest
    			c.older = this.youngest // The get-node's older sibling is the previous youngest
    			this.youngest = key     // The global youngest is the get-node
    		}
    		return c.value
    	}
    	return -1
    }
    
    func (this *LRUCache) Put(key int, value int) {
    	if len(this.m) == 0 { // This happens just once, on a new map
    		this.youngest, this.oldest = key, key
    	}
    	if this.Get(key) == -1 { // If the value doesn't exist (side-effect: move the put-node to the front of the LRU if it does exist)
    		this.m[key] = &cacheVal{ // Add a brand new value
    			value:   value,
    			younger: -1,
    			older:   -1,
    		}
    		this.Get(key) // Use get to place it at the front of the LRU linked list
    	} else {
    		this.m[key].value = value // update the value
    	}
    
    	if len(this.m) > this.capacity { // Check for over-capacity and remove
    		c := this.m[this.oldest]     // Get the oldest node
    		this.m[c.younger].older = -1 // The younger node is now the oldest, so clear the older key
    		oldOldest := this.oldest
    		this.oldest = c.younger   // The younger sibling is now the oldest globally
    		delete(this.m, oldOldest) // delete the oldest node from the map
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.