146.md

LRU Cache

Description

link

---

Solution

See Code

Least Used means the fatherest one which not been used

---

Code

O(1)

class LRUCache:

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.size = capacity
        self.cache = collections.OrderedDict()

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self.cache: return -1
        value = self.cache[key]
        self.cache.move_to_end(key)
        return value

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if key in self.cache: del self.cache[key]
        self.cache[key] = value
        if len(self.cache) > self.size:
            self.cache.popitem(last=False)


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)