边工作边刷题：70天一遍leetcode: day 98

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 = keyself.val = valself.next = Noneself.prev = Nonedef __init__(self, capacity):""":type capacity: int"""self.capacity = capacityself.size = 0self.hmap = {}self.dummy = self.ListNode(0,0)self.tail = self.dummydef get(self, key):""":rtype: int"""hmap=self.hmapif key not in hmap:return -1val = hmap[key].valself.deleteNode(hmap[key])self.addNode(hmap[key])return valdef set(self, key, value):""":type key: int:type value: int:rtype: nothing"""hmap=self.hmapif key not in hmap:print self.size,self.capacityif self.size==self.capacity:print self.tail.keyhmap.pop(self.tail.key)self.deleteNode(self.tail)self.size-=1hmap[key]=self.ListNode(key,value)self.addNode(hmap[key])self.size+=1else:hmap[key].val=valueself.deleteNode(hmap[key])self.addNode(hmap[key])def deleteNode(self, node):# print self.hmap, node.val, self.tail.valif self.tail==node:self.tail = self.tail.prevself.tail.next = Noneelse:node.prev.next = node.nextnode.next.prev = node.prevdef addNode(self, node):dummy = self.dummyif dummy.next:dummy.next.prev = nodeelse:self.tail = nodenode.prev = dummynode.next = dummy.nextdummy.next = node

转载于:https://www.cnblogs.com/absolute/p/5983282.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！