LRU Cache
这是一道leetcode的难题，这种题往往是算法结构很复杂，涉及一个或多个考点算法和数据结构的组合，同时又有很多corner cases要考虑。所以一定要找到合适memorize的结构，这样很容易推导出整个题目的解。否则会不断的记了忘忘了记。
这题分成大面上有两个考点，一个是LRU算法本身，另一个是hash table和doubly list的操作。LRU算法围绕两个接口get() and put()。这题的internal data structure之所以是hash table和list的结合是因为接口支持基于key的操作，而进出则是基于顺序，所以hash table用来支持key query，而list可以跟踪访问顺序。用到doubly list是因为其支持list上单node的reference的所有操作，不需要同时保存prev或者next的reference。
high-level操作
- get()：从hash table查询key value返回值，同时移动key对应的node到队列头
- put()：考虑两种情况：key已经在cache中存在或者不存在。
- 如果存在，与get的操作类似。
- 如果不存在，因为LRU cache的capacity有限，进一步考虑是否当前cache中的key已经等于当前capacity
- 如果等于，需要删除list的最后node，然后插入新的到hash table和队头
- 如果小于，直接插入新的到hash table和队头
low-level细节
- 根据high-level算法，无论是更新存在的key或者加入新key，对list只有两个基本操作removeNode()和addNodeToHead()，核心都是更新prev和next reference。无论是删除还是添加，都有可能对队头node，所以需要一个dummy node作为sentinel head
- corner cases：对于删除操作，一般的操作是更新next node的prev，所以对于tail，其next node为null，需要忽略这步。类似，对于添加到队头操作，需要更新当前队头node的prev，所以如果是空list，也要忽略这步。
class LRUCache(object):
class ListNode(object):
def __init__(self, key, val):
self.key = key
self.val = val
self.next = None
self.prev = None
def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity = capacity
self.size = 0
self.hmap = {}
self.dummy = self.ListNode(0,0)
self.tail = self.dummy
def get(self, key):
"""
:rtype: int
"""
hmap=self.hmap
if key not in hmap:
return -1
val = hmap[key].val
self.deleteNode(hmap[key])
self.addNode(hmap[key])
return val
def set(self, key, value):
"""
:type key: int
:type value: int
:rtype: nothing
"""
hmap=self.hmap
if key not in hmap:
print self.size,self.capacity
if self.size==self.capacity:
print self.tail.key
hmap.pop(self.tail.key)
self.deleteNode(self.tail)
self.size-=1
hmap[key]=self.ListNode(key,value)
self.addNode(hmap[key])
self.size+=1
else:
hmap[key].val=value
self.deleteNode(hmap[key])
self.addNode(hmap[key])
def deleteNode(self, node):
# print self.hmap, node.val, self.tail.val
if self.tail==node:
self.tail = self.tail.prev
self.tail.next = None
else:
node.prev.next = node.next
node.next.prev = node.prev
def addNode(self, node):
dummy = self.dummy
if dummy.next:
dummy.next.prev = node
else:
self.tail = node
node.prev = dummy
node.next = dummy.next
dummy.next = node