题目：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);

            }

        }

}