LRU Cache
这题调了好几天才pass
要点：用doubly linked list，
- deleteNode和addNode分开考虑，分开考虑，分开考虑，重要的事情说三遍
- 需要dummy node和tail，deleteNode考虑tail，addNode考虑dummy.next（因为addNode alway加头）
- set()：最外分支是是否key已经在map里（在表示update），没在always加头
错误点：
- 空间满了以后先size--，这样空间未满的情况统一处理，注意别忘了size++
- remove key from hmap顺序反了，固化：永远在改变结点之前。
- 这题错误大多在deleteNode和addNode里，而且很难debug，比如，忘了连接dummy.next
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