Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

设计一个近期最少使用页面置换缓存LRU(Least Recently Used)，实现get(key), set(key, value)功能。

get(key)：取值(key恒为正), 不存在时返回-1。如果存在，返回值，并且delete此key，在从新写入cache，因为要最近刚使用过，要把它放到队尾。
set(key, value)：缓存已满，删除近期最久未被使用的节点，添加新节点进缓存。缓存未满，节点存在，修改value；节点不存在，添加新节点进缓存；最后更新此节点到队尾。

解法1: 双向链表(Doubly-Linked List) + HashMap

双向链表：维护缓存节点CacheNode，凡是被访问（新建/修改命中/访问命中）过的节点，一律在访问完成后移动到双向链表尾部，保证链表尾部始终为最新节点；保证链表头部始终为最旧节点，LRU策略删除时表现为删除双向链表头部；由于链表不支持随机访问，使用HashMap+双向链表实现LRU缓存，HashMap中键值对：<key, CacheNode>。

解法2: OrderedDict有序字典

Time: Get O(1) Set O(1), Space: O(N)

Java：

import java.util.HashMap;

class Solution {

    private HashMap<Integer, CacheNode> map;

    private int capacity;

    // head.next和tail.next指向链表头尾，包起来防止null

    private CacheNode head = new CacheNode(-1, -1);

    private CacheNode tail = new CacheNode(-1, -1);

    private class CacheNode {

        int key, value;

        CacheNode pre, next;

        CacheNode(int key, int value) {

            this.key = key;

            this.value = value;

            this.pre = null;

            this.next = null;

        }

    }

    public Solution(int capacity) {

        this.map = new HashMap<>();

        this.capacity = capacity;

    }

    // 将已有节点或新建节点移动到链表尾部

    private void moveToTail(CacheNode target, boolean isNew) {

        // 尾部节点显然不需要移动

        if (target != tail.next) {

            if (!isNew) {

                // 修改旧节点的双向链表指针

                target.pre.next = target.next;

                target.next.pre = target.pre;

            }

            // 添加节点到链表尾部

            tail.next.next = target;

            target.pre = tail.next;

            tail.next = target;

        }

    }

    // 命中节点添加到链表尾部，未命中返回-1

    public int get(int key) {

        if (map.containsKey(key)) {

            CacheNode target = map.get(key);

            // 将已有节点移动到链表尾部

            moveToTail(target, false);

            // 此时链表尾部tail.next = target，更新next指向null，防止出现环

            tail.next.next = null;

            return target.value;

        }

        return -1;

    }

    public void set(int key, int value) {

        if (map.containsKey(key)) {

            CacheNode target = map.get(key);

            target.value = value;

            map.put(key, target);

            // 将访问过的已有节点移动到链表尾部

            moveToTail(target, false);

        } else if(map.size() < capacity) {    // cache未满，添加节点

            CacheNode newNode = new CacheNode(key, value);

            map.put(key, newNode);

            if (head.next == null) {

                head.next = newNode;

                newNode.pre = head;

                tail.next = newNode;

            } else {

                // 将新建节点移动到链表尾部

                moveToTail(newNode, true);

            }

        } else {    // cache已满，淘汰链表链表头部节点，新节点加入到链表尾部

            CacheNode newNode = new CacheNode(key, value);

            map.remove(head.next.key);

            map.put(key, newNode);

            // cache中只有一个元素

            if (head.next == tail.next) {

                head.next = newNode;

                tail.next = newNode;

            } else {    // cache中不止一个元素，删除头部

                head.next.next.pre = head; // 更新新头部.pre = head

                head.next = head.next.next;// 更新新头部

                // 将新建节点移动到链表尾部

                moveToTail(newNode, true);

            }

        }

    }

}

Python:

class Node:

    def __init__(self, key, val):

        self.key = key

        self.val = val

        self.prev = None

        self.next = None

class LRUCache:

    # @param capacity, an integer

    def __init__(self, capacity):

        self.capacity = capacity

        self.size = 0

        self.dummyNode = Node(-1, -1)

        self.tail = self.dummyNode

        self.entryFinder = {}

    # @return an integer

    def get(self, key):

        entry = self.entryFinder.get(key)

        if entry is None:

            return -1

        else:

            self.renew(entry)

            return entry.val

    # @param key, an integer

    # @param value, an integer

    # @return nothing

    def set(self, key, value):

        entry = self.entryFinder.get(key)

        if entry is None:

            entry = Node(key, value)

            self.entryFinder[key] = entry

            self.tail.next = entry

            entry.prev = self.tail

            self.tail = entry

            if self.size < self.capacity:

                self.size += 1

            else:

                headNode = self.dummyNode.next

                if headNode is not None:

                    self.dummyNode.next = headNode.next

                    headNode.next.prev = self.dummyNode

                del self.entryFinder[headNode.key]

        else:

            entry.val = value

            self.renew(entry)

    def renew(self, entry):

        if self.tail != entry:

            prevNode = entry.prev

            nextNode = entry.next

            prevNode.next = nextNode

            nextNode.prev = prevNode

            entry.next = None

            self.tail.next = entry

            entry.prev = self.tail

            self.tail = entry

Python:

class ListNode(object):

    def __init__(self, key, val):

        self.val = val

        self.key = key

        self.next = None

        self.prev = None

class LinkedList(object):

    def __init__(self):

        self.head = None

        self.tail = None

    def insert(self, node):

        node.next, node.prev = None, None  # avoid dirty node

        if self.head is None:

            self.head = node

        else:

            self.tail.next = node

            node.prev = self.tail

        self.tail = node

    def delete(self, node):

        if node.prev:

            node.prev.next = node.next

        else:

            self.head = node.next

        if node.next:

            node.next.prev = node.prev

        else:

            self.tail = node.prev

        node.next, node.prev = None, None  # make node clean

class LRUCache(object):

    def __init__(self, capacity):

        self.list = LinkedList()

        self.dict = {}

        self.capacity = capacity

    def _insert(self, key, val):

        node = ListNode(key, val)

        self.list.insert(node)

        self.dict[key] = node

    def get(self, key):

        if key in self.dict:

            val = self.dict[key].val

            self.list.delete(self.dict[key])

            self._insert(key, val)

            return val

        return -1

    def set(self, key, val):

        if key in self.dict:

            self.list.delete(self.dict[key])

        elif len(self.dict) == self.capacity:

            del self.dict[self.list.head.key]

            self.list.delete(self.list.head)

        self._insert(key, val)

Python:

class LRUCache:

    def __init__(self, capacity):

        self.capacity = capacity

        self.cache = collections.OrderedDict()

    def get(self, key):

        if not key in self.cache:

            return -1

        value = self.cache.pop(key)

        self.cache[key] = value

        return value

    def set(self, key, value):

        if key in self.cache:

            self.cache.pop(key)

        elif len(self.cache) == self.capacity:

            self.cache.popitem(last=False)

        self.cache[key] = value

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);

        }

    }

private:

    int cap;

    list<pair<int, int> > l;

    unordered_map<int, list<pair<int, int> >::iterator> m;

};

All LeetCode Questions List 题目汇总

　　

最新文章

  1. Bootstrap 模态框 + iframe &gt; 打开子页面 &gt; 数据传输/关闭模态框
  2. KlayGE 4.4中渲染的改进（二）：DR的其他改进
  3. mysql int(3)与int(11)的区别
  4. 如何让WordPress支持上传更多文件类型
  5. ShortcutMapper – 热门应用程序的可视化快捷键
  6. MyEclipse------execute()使用方法
  7. 分布式一致性原理—CAP
  8. MYSQL数据库性能调优之七：其他（读写分离、分表等）
  9. PLSQL Developer 常用设置及快捷键
  10. C/C++遍历目录下的所有文件（Windows/Linux篇，超详细）
  11. POJ 2007 Scrambled Polygon [凸包 极角排序]
  12. visual studio vode 汉化
  13. JavaScript 笔记（一）
  14. python2与python3中除法的区别
  15. 集合List和ArrayList的示例
  16. 牛客国庆集训派对Day4 J-寻找复读机
  17. Python3 - DBUtils 和 pymysql 整合
  18. 【Go命令教程】5. go clean
  19. SAP SD 顾问面试问题 consultant interview questionnaire
  20. phpstorm之自定义代码碎片（tab键自动填充代码）

热门文章

  1. 【学英语~磨耳朵】2013年以来看过的所有美剧&amp;电影&amp;纪录片等等
  2. Django的Form另类实现SelectMultiple
  3. 异常检测(Anomaly detection): 高斯分布（正态分布）
  4. 从输入URL到页面返回的过程详解
  5. B君的历史——复数乘法&amp;&amp;爆搜
  6. python - django 控制台输出 sql 语句
  7. 11、 Hadoop 2.x各个服务组件如何配置在那台服务器运行并测试
  8. 002_Visual Studio （gnuplot）显示数组波形
  9. 事件类型（onfocus和onblur）
  10. 自用 goodsdetail