LRU 缓存机制-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

LRU 缓存机制

Runt 2020-04-14 16:47:15 396

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

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

缓存 CDN
分享到
取消 提交回答
全部回答(1)
  • Runt
    2020-04-14 16:52:36

    参考答案:

    python版本的:

        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++版本的:

        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);
                }
            }
    }
    
    
    0 0
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

推荐文章
相似问题
推荐课程