每日一道面试题 - 04

末蓝、 2021-07-31 23:43 355阅读 0赞

![640?wx\_fmt=png][640_wx_fmt_png]

**每日一题：**从阿里，腾讯，百度，美团，头条等大厂技术题目中选取有价值得题目，对题目考察目标进行分析，并给出参考答案。**每日一题，在不知不觉中进步，欢迎留言区打卡 ！**

**问题：**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);	
                }	
            }	
    }

**历史题****目**

今日一题选自热门GitHub项目interview\_internal\_reference。点击「阅读原文」即可 此star 项目。同样关注订阅号「Web项目聚集地」获得每日面试题更新。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

▲扫码关注获取更新

[640_wx_fmt_png]: /images/20210731/b328750d0af3450e910eb01a1e2c19e2.png?wx_fmt=png
[640_wx_fmt_jpeg]: /images/20210731/b6b4cb2d1e97460093ef71abc27e408c.png?wx_fmt=jpeg