LRU 缓存机制 收藏 阅读:16
2020-10-27 11:31:55

题目:LRU 缓存机制设计和实现一个 LRU(最近最少使用)缓存数据结构,使它应该支持一下操作:get 和 put。get(key) - 如果 key 存在于缓存中,则获取 key 的 value(总是正数),否则返回 -1。put(key,value) - 如果 key 不存在,请设置或插入 value。当缓存达到其容量时,它应该在插入新项目之前使最近最少使用的项目作废。

出题人:文景/阿里云 CDN 资深技术专家

参考答案

python版本的:

class LRUCache(object):
  def __init__(self, capacity):
  """
  :type capacity: int
  """
  self.cache = {}
  self.keys = []
  self.capacity = capacity
   
  def visit_key(self, key):
      if key in self.keys:
          self.keys.remove(key)
      self.keys.append(key)
   
  def elim_key(self):
      key = self.keys[0]
      self.keys = self.keys[1:]
      del self.cache[key]
       
  def get(self, key):
      """
      :type key: int
      :rtype: int
      """
      if not key in self.cache:
          return -1
      self.visit_key(key)
      return self.cache[key]
   
  def put(self, key, value):
      """
      :type key: int
      :type value: int
      :rtype: void
      """
      if not key in self.cache:
      if len(self.keys) == self.capacity:
      self.elim_key()
      self.cache[key] = value
      self.visit_key(key)

def main():
  s =
  [["put","put","get","put","get","put","get","get","get"],[[1,1],[2,2],[1],[3,3],[2],[
  4,4],[1],[3],[4]]]
  obj = LRUCache(2)
  l=[]
  for i,c in enumerate(s[0]):
      if(c == "get"):
          l.append(obj.get(s[1][i][0]))
      else:
          obj.put(s[1][i][0], s[1][i][1])
  print(l)

if __name__ == "__main__":
  main()

c++版本的:

class LRUCache{
  public:
      LRUCache(int capacity) {
          cap = capacity;
      }
       
      int get(int key) {
          auto it = m.find(key);
          if (it == m.end()) return -1;
          l.splice(l.begin(), l, it->second);
          return it->second->second;
      }
       
      void set(int key, int value) {
          auto it = m.find(key);
          if (it != m.end()) l.erase(it->second);
          l.push_front(make_pair(key, value));
          m[key] = l.begin();
          if (m.size() > cap) {
              int k = l.rbegin()->first;
              l.pop_back();
              m.erase(k);
          }
      }
}

读后有收获,请作者喝杯咖啡


全部评论

发表评论