LeetCode146. LRU Cache思路及python解法

. It should support the following operations:??get??and??put.

getkey?? Get the value will always be positive of the key if the key exists in the cache, otherwise return 1.putkey, 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.

The cache is initialized with a??positive??capacity.

Follow up:Could you do both operations in??O1??time complexity?

Example:

LRUCache cache = new LRUCache 2 /* capacity */ ;cache.put1, 1;cache.put2, 2;cache.get1; // returns 1cache.put3, 3; // evicts key 2cache.get2; // returns 1 not foundcache.put4, 4; // evicts key 1cache.get1; // returns 1 not foundcache.get3; // returns 3cache.get4; // returns 4

完成一个添加、查找的过程。难点在于有限定长度，如果超了需要删除最久没用过的键值对。（有点类似于内存占用算法）

用collection.OrderedDict真是很方便。

即有顺序，又能根据key进行popkey，又能根据位置popitemi。

注意get的时候相当于调用了，所以pop出来重新加到字典尾部。也可以用self.dic.move to endkey来执行，很方便。

class LRUCache: def init self, capacity: int: self.maxl=capacity self.dic = collections.OrderedDict def getself, key: int int: if key in self.dic.keys: temp=self.dic.popkey self.dic[key]=temp return temp return 1 def putself, key: int, value: int None: if key in self.dic.keys: self.dic.popkey self.dic[key]=value if lenself.dic self.maxl: self.dic.popitem0

??