146. LRU Cache

题目链接：国际版，国内版
公司：Meta
解法：模拟

题目描述

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

思路

LRU Cache，一道非常经典的模拟题。具体来说就是使用代码模拟出一个 Cache Obejct，它采用 LRU 策略，就是最近最少使用。当 Cache 中元素达到最大容量需要移除一个的时候，把使用时间距离现在最远的一个元素给移除。再根据题意思考，Cache 中需要存储 k-v pair，因此肯定需要一个 HashMap。但与此同时，为了实现 LRU，我们还要保证 HashMap 中 item 的顺序是固定的。因此可以想到，我们应该使用 OrderedDict（如果是 Java 就是 LinkedHashMap）。

题目要求我们实现两个方法：get 和 put。get 方法的思路很简单，首先判断元素是否存在，不存在就返回 -1。如果存在，先要将这个 item 标记为最近使用过，之后再返回对应的 value。put 方法的实现稍微复杂一些，因为要考虑 Cache 容量不够要移除最近未被使用的元素。与此同时，如果 put 传入的 key 已经在 Cache 中存在了，那么在更新值的同时也要将该 item 标记为最近使用过。由于使用了 OrderedDict，这里的策略是越是最近使用过的元素顺序越排在后面。如果要移除最近未使用的元素，则直接弹出 Cache 中第一对元素即可。

代码参考

from collections import OrderedDict

class LRUCache:

    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.make_recent(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.make_recent(key)
        else:
            if len(self.cache) == self.capacity:
                self.cache.popitem(last=False)
        self.cache[key] = value

    def make_recent(self, key) -> None:
        # Helper function
        self.cache.move_to_end(key, last=True)
        
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)