Commit7aa79e5

applewjg

committed

LRU Cache

Change-Id: Ia0b8e682b36f8d5caace61da02757097da8111ec

1 parent38f20e1 commit7aa79e5Copy full SHA for 7aa79e5

File tree

+40

-0

lines changed

+40

-0

lines changed

Lines changed: 40 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,40 @@`
	`1`	`+/*`
	`2`	`+ Author: King, nkuwjg@gmail.com`
	`3`	`+ Date: March 12, 2014`
	`4`	`+ Problem: LRU Cache`
	`5`	`+ Difficulty: Hard`
	`6`	`+ Source: http://oj.leetcode.com/problems/lru-cache/`
	`7`	`+ Notes:`
	`8`	`+ Design and implement a data structure for Least Recently Used (LRU) cache.`
	`9`	`+ It should support the following operations: get and set.`
	`10`	`+ get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.`
	`11`	`+ set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.`
	`12`	`+`
	`13`	`+ Solution: Hash + list.`
	`14`	`+*/`
	`15`	`+`
	`16`	`+importjava.util.LinkedHashMap;`
	`17`	`+importjava.util.Map;`
	`18`	`+publicclassLRUCache {`
	`19`	`+privateMap<Integer,Integer>map;`
	`20`	`+privateintcapacity;`
	`21`	`+publicLRUCache(intcapacity) {`
	`22`	`+this.capacity =capacity;`
	`23`	`+map =newLinkedHashMap<Integer,Integer>(capacity);`
	`24`	`+ }`
	`25`	`+`
	`26`	`+publicintget(intkey) {`
	`27`	`+Integerval =map.get(key);`
	`28`	`+if (val ==null)return -1;`
	`29`	`+map.remove(key);`
	`30`	`+map.put(key,val);`
	`31`	`+returnval;`
	`32`	`+ }`
	`33`	`+`
	`34`	`+publicvoidset(intkey,intvalue) {`
	`35`	`+map.remove(key);`
	`36`	`+map.put(key,value);`
	`37`	`+if (map.size() >capacity)`
	`38`	`+map.remove(map.entrySet().iterator().next().getKey());`
	`39`	`+ }`
	`40`	`+}`

Comments

(0)