Commitc447042

authored

Merge pull requestneetcode-gh#1309 from voski/patch-13

Create 0146-LRU-Cache.rb

2 parentsc8fd9a5 +587e108 commitc447042Copy full SHA for c447042

File tree

+74

-0

lines changed

+74

-0

lines changed

Lines changed: 74 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,74 @@`
	`1`	`+classLRUCache`
	`2`	`+`
	`3`	`+=begin`
	`4`	`+ :type capacity: Integer`
	`5`	`+=end`
	`6`	`+definitialize(capacity)`
	`7`	`+@capacity=capacity`
	`8`	`+@cache={}`
	`9`	`+@l=Node.new()`
	`10`	`+@r=Node.new()`
	`11`	`+@l.next=@r`
	`12`	`+@r.prev=@l`
	`13`	`+end`
	`14`	`+`
	`15`	`+`
	`16`	`+=begin`
	`17`	`+ :type key: Integer`
	`18`	`+ :rtype: Integer`
	`19`	`+=end`
	`20`	`+defget(key)`
	`21`	`+return -1unless@cache.key?(key)`
	`22`	`+`
	`23`	`+remove(@cache[key])`
	`24`	`+insert(@cache[key])`
	`25`	`+@cache[key].value`
	`26`	`+end`
	`27`	`+`
	`28`	`+`
	`29`	`+=begin`
	`30`	`+ :type key: Integer`
	`31`	`+ :type value: Integer`
	`32`	`+ :rtype: Void`
	`33`	`+=end`
	`34`	`+defput(key,value)`
	`35`	`+remove(@cache[key])if@cache.key?(key)`
	`36`	`+`
	`37`	`+@cache[key]=Node.new(key,value)`
	`38`	`+insert(@cache[key])`
	`39`	`+evictif@capacity <@cache.size`
	`40`	`+end`
	`41`	`+`
	`42`	`+private`
	`43`	`+defremove(node)`
	`44`	`+prev=node.prev`
	`45`	`+nxt=node.next`
	`46`	`+`
	`47`	`+prev.next=nxt`
	`48`	`+nxt.prev=prev`
	`49`	`+end`
	`50`	`+`
	`51`	`+definsert(node)`
	`52`	`+prev=@r.prev`
	`53`	`+prev.next=node`
	`54`	`+@r.prev=node`
	`55`	`+`
	`56`	`+node.prev=prev`
	`57`	`+node.next=@r`
	`58`	`+end`
	`59`	`+`
	`60`	`+defevict`
	`61`	`+lru=@l.next`
	`62`	`+remove(lru)`
	`63`	`+@cache.delete(lru.key)`
	`64`	`+end`
	`65`	`+`
	`66`	`+classNode`
	`67`	`+attr_accessor:value,:prev,:next,:key`
	`68`	`+`
	`69`	`+definitialize(key=0,val=nil)`
	`70`	`+self.value=val`
	`71`	`+self.key=key`
	`72`	`+end`
	`73`	`+end`
	`74`	`+end`

Comments

(0)