LintCode 134. LRU Cache 原创Java参考解答

LintCode 134. LRU Cache 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/lru-cache/

Implement a stack with min() function, which will return the smallest number in the stack.

It should support push, pop and min operation all in O(1) cost.

Notice

min operation will never be called if there is no number in the stack.

解题思路

经典的算法问题:LRU Cache,设计最近最少使用缓存。

最近最少使用缓存(LRU)需要两个操作:获取数据(get)和写入数据(set)。

  • 获取数据get(key):如果缓存中存在key,则获取其数据值,否则返回-1。
  • 写入数据set(key, value):如果key还没有在缓存中,则写入其数据值。当缓存达到容量上限,它应该在写入新数据之前,删除最近最少使用的过往数据来腾出空闲位置。
常见的LRU Cache实现方法:双向链表(Doubly Linked List) + HashMap
LRU的实质是按照节点访问时间顺序排列的双向链表。每个双向链表节点有prev和next指向其一前一后的节点。最近被访问的节点放置在链表头部。一旦链表达到容量,需要剔除元素的时候,踢出链表尾部的最老时间被访问过的元素。
HashMap则是用来根据key来找对应的链表节点。

参考代码

public class Solution { 
    private class Node { 
        int key; 
        int value; 
        Node prev; 
        Node next; 
         
        public Node(int key, int value) { 
            this.key = key; 
            this.value = value; 
            this.prev = null; 
            this.next = null; 
        } 
    } 
     
    private int capacity; 
    private HashMap<Integer, Node> map; 
    private Node head = new Node(-1, -1); 
    private Node tail = new Node(-1, -1); 
     
    // @param capacity, an integer 
    public Solution(int capacity) { 
        this.capacity = capacity; 
        this.map = new HashMap<Integer, Node>(); 
        tail.prev = head; 
        head.next = tail; 
    } 
 
    // @return an integer 
    public int get(int key) { 
        if (!map.containsKey(key)) { 
            return -1; 
        } else { 
            Node current = map.get(key); 
            remove(current); 
            setHead(current); 
            return map.get(key).value; 
        }         
    } 
 
    // @param key, an integer 
    // @param value, an integer 
    // @return nothing 
    public void set(int key, int value) { 
        if (get(key) != -1) { 
            map.get(key).value = value; 
            return; 
        } 
         
        // if reaches capacity, remove oldest cache 
        if (map.size() == capacity) { 
            map.remove(tail.prev.key); 
            remove(tail.prev); 
        } 
         
        // insert     
        Node insert = new Node(key, value); 
        map.put(key, insert); 
        setHead(insert); 
    } 
     
    private void remove(Node node) { 
        node.prev.next = node.next; 
        node.next.prev = node.prev; 
    } 
     
    private void setHead(Node node) { 
        node.next = head.next; 
        head.next.prev = node; 
        head.next = node; 
        node.prev = head; 
    } 
}

相关题目

LintCode All in One 原创题目讲解汇总

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注