Fork me on GitHub

1.1.4 LRU缓存机制.md

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

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

参考答案

python版本的:

  1. class LRUCache(object):
  2. def __init__(self, capacity):
  3. """
  4. :type capacity: int
  5. """
  6. self.cache = {}
  7. self.keys = []
  8. self.capacity = capacity
  9. def visit_key(self, key):
  10. if key in self.keys:
  11. self.keys.remove(key)
  12. self.keys.append(key)
  13. def elim_key(self):
  14. key = self.keys[0]
  15. self.keys = self.keys[1:]
  16. del self.cache[key]
  17. def get(self, key):
  18. """
  19. :type key: int
  20. :rtype: int
  21. """
  22. if not key in self.cache:
  23. return -1
  24. self.visit_key(key)
  25. return self.cache[key]
  26. def put(self, key, value):
  27. """
  28. :type key: int
  29. :type value: int
  30. :rtype: void
  31. """
  32. if not key in self.cache:
  33. if len(self.keys) == self.capacity:
  34. self.elim_key()
  35. self.cache[key] = value
  36. self.visit_key(key)
  37. def main():
  38. s =
  39. [["put","put","get","put","get","put","get","get","get"],[[1,1],[2,2],[1],[3,3],[2],[
  40. 4,4],[1],[3],[4]]]
  41. obj = LRUCache(2)
  42. l=[]
  43. for i,c in enumerate(s[0]):
  44. if(c == "get"):
  45. l.append(obj.get(s[1][i][0]))
  46. else:
  47. obj.put(s[1][i][0], s[1][i][1])
  48. print(l)
  49. if __name__ == "__main__":
  50. main()

c++版本的:

  1. class LRUCache{
  2. public:
  3. LRUCache(int capacity) {
  4. cap = capacity;
  5. }
  6. int get(int key) {
  7. auto it = m.find(key);
  8. if (it == m.end()) return -1;
  9. l.splice(l.begin(), l, it->second);
  10. return it->second->second;
  11. }
  12. void set(int key, int value) {
  13. auto it = m.find(key);
  14. if (it != m.end()) l.erase(it->second);
  15. l.push_front(make_pair(key, value));
  16. m[key] = l.begin();
  17. if (m.size() > cap) {
  18. int k = l.rbegin()->first;
  19. l.pop_back();
  20. m.erase(k);
  21. }
  22. }
  23. }
2020-03-07 16:32:09  LeeChan 阅读(58) 评论(0) 标签:面试,01.阿里篇 分类:阿里篇